multiple TSP with direct constraints

[andre...@googlemail.com]

Hi,

I'm trying to formulate the tsp from https://github.com/google/or-tools/blob/stable/examples/python/tsp_sat.py

as a multiple variant, like it is the case for multiple vehicle routing. (I'm aware of the routing library, but for exercise I would like to understand how to model it directly)

As far as I understand, when using multiple "travelers" I cannot simply use "AddCircuit" since flow constraints from that will be violated. (Especially, I would have differing costs for each traveler, similar to the routing library)

My first thoughts are:

1. Create all possible circuits for all "travelers" and choose the ones that are cheapest according to the objective. But that would blow up the combinations depending on the number of travelers.

2. Perhaps I need to adapt the "circuit" function from http://www.hakank.org/google_or_tools/cp_sat_utils.py

in order to account for subroutes for each "traveler". As such, I think, I would need to include additional constraints:

* all nodes must be visited once except depot node

* depot node is visited 1 + n_travelers

* travelers must visit disjunctive set of nodes

Is this the right approach? Do I then need to solve it in a similar fashion like the LP variant and eliminate subroutes?

Are there any other approaches?

I'm stuck and would appreciate if you can point me in the right direction.

Thanks!

[Laurent Perron]

1) you can browse ortools/constraint_solver/routing_sat.cc

2) you have 2 options:

  a) duplicate the depot such that the vrp is encoded as a large tsp using a sequence of smaller cycles going from and to these virtual depots

  b) have one circuit per vehicle, using optional nodes for visits, and making sure that each visit is performed by at_most/exactly one vehicle.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8325b539-3142-4f69-a852-5cebc6063e95n%40googlegroups.com.