VRP subtour problems

[Mats Blok]

Hi all,

Currently I am working on modeling a VRP in AIMSS. This went pretty fine so far but now I ran into an (for me) unsolvable problem. I have written a model which determines optimal routes given a fixed number of trucks which supply all customers. The only problem now is that when the optimal solution is calculated, various subtours are formed, which I can´t get rid off using constraints. What is the best way of get rid of this problem is such a way that these subtours are prohibited in the generated solutions? And how do I exactly model this in AIMMS? I have added my model to this email in a text file. Thank you in advance for your help!

Kind regards,

Mats

[Luis Pinto]

What comes to mind is using an approach that you insert new constraints as sub tours are selected.

Like an inverted "cutting stock" problem.

Check out the example for aimms index on cutting stock.

Something like:

-> Generate solution

-> Identify Sub tours

-> Add constraint

-> Re-solve

GMP has funcionality to help with this.

This could lead to bad performance, but thats my 50c's.

BR,

Luis Pinto

www.unisoma.com

--
You received this message because you are subscribed to the Google Groups "AIMMS - The Modeling System" group.
To unsubscribe from this group and stop receiving emails from it, send an email to aimms+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Marcel Hunting]

Hi,

You could use the approach as suggested by Luis, or use a different formulation. The Capacitated Vehicle Routing Problem formulation as proposed by Toth and Vigo (2002), and denoted by VRP4 on pp. 15-16, uses the Miller-Tucker-Zemlin subtour elimination constraints and is quite efficient.

Reference:

Toth, P., and D. Vigo, An Overview of Vehicle Routing Problems, In: The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002, pp. 1-26.

(As a side remark to Luis' suggestion. It might even be better to use the lazy constraint callback. Then you only have to solve one MIP. Inside the callback you then check whether the incumbent solution contains a subtour and if that is the case you add a lazy constraint that forbids that subtour.)

Best regards,

Marcel Hunting

AIMMS