4
$\begingroup$

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
Improve this question
$\endgroup$
4
  • $\begingroup$ X-post: groups.google.com/forum/?hl=kn#!topic/or-tools-discuss/… $\endgroup$
    – Stradivari
    Feb 4, 2020 at 18:48
  • 1
    $\begingroup$ 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 $\endgroup$
    – sascha
    Feb 6, 2020 at 20:51
  • 1
    $\begingroup$ 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) $\endgroup$
    – sascha
    Feb 6, 2020 at 21:14
  • $\begingroup$ 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. $\endgroup$
    – Simon Roed
    Feb 13, 2020 at 9:15

1 Answer 1

Reset to default
3
$\begingroup$

So, this is a bit complex. You cannot use the routing library out of the box.

If the problem is not too big, you can use the CP-SAT solver with the circuit constraint. A good start is this example.

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).

The difficulty lies in the boundary constraints. How do you make sure these constraints are valid for the first 2 nodes?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your input Laurent! I will look into the example and give it a try myself. $\endgroup$
    – Simon Roed
    Feb 13, 2020 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.