Hello, I’m working on a VRP project and I would like to write this code related to the VRP problem. Does anyone have this code? Especially for constraint 4, I’m not sure how to create that subset S. Thanks in advance.
The difficulty with (4) is that it defines one constraint for each subset of a given set. This cannot be stated explicitly in AMPL, but a way to express it in AMPL is given by the following FAQ entry:
How can I get AMPL to index over the “power set” consisting of all subsets of a set?
Also, it is not clear how V and n are supposed to be related in (VRP1). I would guess that V is the same as 1,\ldots,n, and V-\{1\} is the same as 2,\ldots,n.
Your question has been moved to our new user forum at discuss.ampl.com, and a response has been posted. To see the response, use this link:
https://discuss.ampl.com/t/ampl-25030-formulation-vrp-code/1071/2
To reply, click the red “Reply” button that follows the response. (Do not send an email reply to this message.)
Hi Maria,
Those constraints are used to avoid subtours in any subset S of nodes. As it is not practical to add every constraint (4) to the model directly, it is better to insert them dynamically through solver callbacks (more efficient), or through ampl. In any case, you will need to solve the relaxed problem without the constraints, look for subtours in the solution, add the constraints related to the subtours so they disappear, and solve again. Repeat the process until there are no more subtours.
I highly recommend you to take a look at this model within a jupyter notebook that uses this idea, and the ampl api for python. You can model in ampl but pass data and analyze solutions through python.
An alternative to constraints (4) are the “MTZ variables”.