Suggestions For TSP With Added Conditions

[fulton...@gmail.com]

Does anyone have any suggestions for how to formulate a Traveling Salesman Problem with the added constraint the you must visit City B before City C?

I would prefer a solution with binary integer programming.

Regards,

Fulton Loebel

[duanem...@gmail.com]

I recently used a 2002 paper by Lu & Dessouky: "Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem"
https://pdfs.semanticscholar.org/11ce/9b20528660618746ed25eac8313f4da02a83.pdf

that contains a binary constraint variable "bij" in their equations (3) & (4) that implies node i is immediately before node j.
I'm guessing that you could use this type of variable and add an additional constraint to constrain subsets of the variable to specific values.
They use this same variable to make sure you start and end at the depot.

Here's the link to the previous (Jun 15) post in this group about the CVRP using that paper.
https://groups.google.com/forum/#!topic/ampl/tqf4Rb04pgU

[Fulton Loebel]

Thank you for your response.  I reviewed the paper "Exact Algorithm for the Multiple Vehicle Pickup and Delivery Problem.  I like the "Bij" concept they discuss implying that node i is immedately before node j.  I also like the fact that the authors claim that subtour elimination has been implicitly included in the formulation.  I have tried SECs like TMZ and DL with very limited success.  Since SECs are not explicitly included, I like the concept.  I would like to find a paper similar to the one you provided that is specifically designed for the TSP.  The paper you provided has too many additional constraints for me to understand how to apply it to a TSP.  Thank you again for your thoughts.

Regards,

Fulton Loebel

[duanem...@gmail.com]

Yes, it took me several reading to fully understand all of the constraints....just takes some time.  But if you've already been through TMZ & DFJ, this should be that bad.  Page 10 & 11 of that reference are all you need to understand (not the proofs).

>added constraint the you must visit City B before City C?

You could view city B as a "pickup" and city C as a "drop off", then that portion of the problem becomes a vehicle routing problem with pickup and delivery, the same as discussed in the paper, and as I solved in my example.  The problem I solve is the single vehicle problem, which is more closely related to the TSP, and I also threw out som of the un-needed constraints.  Basically you would just have to eliminate the pickup before delivery constaints for those nodes that don't require it, and you don't need the capacity constrainst since you are not deliverying anything.

As an alternative, you might look at:
The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm, by Zakir Hussain Ahmed
https://www.hindawi.com/journals/tswj/2014/258207/