# TSP with constraints in OR Tools

I am completely new to OR Tools, but what I have tried so far seems very powerful. I have, however, run into a problem that I cannot seem to figure out how to solve. I am trying to model a TSP problem, which also includes constraints on the demand of connected nodes. It is not the capacity on the entire tour, but rather on rolling subsets of the tour.

E.g. the demand of 3 connected nodes has to be at least ($$\ge$$) 6. Or it could also be that the demand of 3 connected nodes at most ($$\le$$) could be 16.

Which would translate into for the min constraint:

demand[tour_index[0]] + demand[tour_index[1]] + demand[tour_index[0]] >= 6
demand[tour_index[1]] + demand[tour_index[2]] + demand[tour_index[3]] >= 6
demand[tour_index[2]] + demand[tour_index[3]] + demand[tour_index[4]] >= 6


and so on.

Say I have the following data, how could I model these kinds of constraints.

Thanks!

data['distance_matrix'] = [
[
0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,
468, 776, 662
],
[
548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
1016, 868, 1210
],
[
776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,
1130, 788, 1552, 754
],
[
696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
1164, 560, 1358
],
[
582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
1050, 674, 1244
],
[
274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,
514, 1050, 708
],
[
502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,
514, 1278, 480
],
[
194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,
662, 742, 856
],
[
308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,
320, 1084, 514
],
[
194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,
274, 810, 468
],
[
536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,
730, 388, 1152, 354
],
[
502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,
308, 650, 274, 844
],
[
388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,
536, 388, 730
],
[
354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,
342, 422, 536
],
[
468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,
342, 0, 764, 194
],
[
776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,
388, 422, 764, 0, 798
],
[
662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,
536, 194, 798, 0
],
]
data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
data['num_vehicles'] = 1
data['depot'] = 0

• Feb 4 '20 at 18:48
• The question lacks details and attempts. ortools is a portfolio of different technologies and you did not point to the part you are targeting (e.g. cp vs. cp-sat solvers). In general Constraint Programming, imho this could be formulated using a combination of circuit and nested element constraints.There are circuit and element constraints in ortools, but i'm too lazy to check their power (esp. because we don't know which solver is targeted). As someone who recently discovered this combination (for some ATSP-TW like prob) in a non-nested setting, i will warn you about some headaches induced Feb 6 '20 at 20:51
• As indicated, i don't think it's much fun and without some basic understanding of the tools available it surely will be non-trivial (gecode for example is much heavier on documentation). Imho the basic problem is to combine the edge-focused nature, which is the core of most approaches (circuit constraint; assignment-polytope of TSP LP) with the sequence-focused nature of accumulated transitions. A very basic explanation covering circuit and element: "Alternative filtering for the weighted circuit constraint: comparing lower bounds for the TSP and solving TSPTW." (Ducomman et al.; 2016) Feb 6 '20 at 21:14
• Thank you for your input sascha. As mentioned I am completely new to OR Tools and I naively thought that my question would be trivial for more experienced users of the suite. My apologies for also not being more specific about the targeted solver, etc. I will go ahead and try Laurent’s suggestion. Feb 13 '20 at 9:15

The idea is for each node to maintain a few int var (sum of the last 1, sum of the last 2, sum of the last 3). Then using the transition literal to constraint the same set of variables in the head node: transition_literal => sum_2(head_nodel) = sum_1(tail_node) + contrib(tail_node).