Pick up and Delivery Order/Precedence Constraint

[Victor Mota]

I've been experimenting with or-tools for a university project - it's great!

Specifically, I'm looking at the pick up and delivery problem and was wondering if there is a way to enforce order (precedence constraint) on pick up and delivery nodes (ie. pick up nodes always coming before delivery nodes in the solution). I'm wondering if there's a way of using simple constraints rather than using a time dimension. In the docs for AddPickupAndDelivery (https://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/tsp/model_behind_scenes_overview.html#pick-up-and-delivery-constraints) it explicitly mentions that it doesn't specify order - is there a way to do this?

Thanks!

[Vincent Furnon]

Hi,

If you don't want to create a time dimension, you can create a rank dimension (all transit values being 1) and add an inequality constraint on the ranks.

Vincent

--
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.
For more options, visit https://groups.google.com/d/optout.

[Michael Powell]

Am I correct in saying that precedence can be modeled? i.e. variable a should solve before variable b ?

How might one go about it? I take it to mean somehow there would need to be a rank variable (or variables), in addition to the actual model itself.

I was able to do something similar in a custom variable chooser (i.e. callback). Basically ensuring that some variables should be chosen before others.

Thanks for any insights.

Cheers,

Michael Powell

[Amit Kumar]

Hey MIchael,

How did you do that? Some help with the code would be useful.

Thanks

[Michael Powell]

On Fri, Mar 11, 2016 at 3:35 PM, Amit Kumar <amit...@gmail.com> wrote:
> Hey MIchael,
>
> How did you do that? Some help with the code would be useful.

Feel free to have a look at
http://github.com/mwpowellhtx/Kingdom.ConstraintSolvers/, in
particular the VariableChooser Callbacks.

I can't promise you whether it needs updating with latest OR tools
developments. Recent reports seem to suggest that, possibly, I am due
for another round of keeping up with OR tools. That said, I have tried
to keep the NuGet package in sync with the OR tools packaging.

> Thanks

No problem. Contributions are welcome.

> On Friday, July 24, 2015 at 4:55:56 PM UTC+5:30, Michael Powell wrote:
>>
>> Am I correct in saying that precedence can be modeled? i.e. variable a
>> should solve before variable b ?
>>
>> How might one go about it? I take it to mean somehow there would need to
>> be a rank variable (or variables), in addition to the actual model itself.
>>
>> I was able to do something similar in a custom variable chooser (i.e.
>> callback). Basically ensuring that some variables should be chosen before
>> others.
>>
>> Thanks for any insights.
>>
>> Cheers,
>>
>> Michael Powell
>

> --
> You received this message because you are subscribed to a topic in the
> Google Groups "or-tools-discuss" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/or-tools-discuss/Nx_SNgM52-g/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to

[Amit Kumar]

I actually want to do this in python and really couldn't get that from the code. Can you elaborate it with some theory based on the documentation?

[Michael Powell]

On Fri, Mar 11, 2016 at 4:39 PM, Amit Kumar <amit...@gmail.com> wrote:
> I actually want to do this in python and really couldn't get that from the
> code. Can you elaborate it with some theory based on the documentation?

Just besides the documentation I called out in the code, the best I
can offer you is to forward you to the Google docs:

https://or-tools.googlecode.com/svn/trunk/documentation/user_manual/manual/search_primitives/basic_working_phases.html#callbacks-to-the-rescue

What I wanted was a more "natural" and less "functional" look and
feel. Instead of a "LongToLong" functional callback, if you will,
provided some naturally documenting code exposing OR tools into my
solvers.

I can't speak for the OR tools SWIG "py-CodeGeneration", per se, but I
imagine it is along similar lines.

Basically...

There are probably ways of modeling precedence semantics, per se; but
short of that, you can control the variable choices yourself, which is
what I ended up doing, based on intermediate variable state.

HTH

[Amit Kumar]

Hey, did you find the solution to this? I am stuck at this part.

[Amit Kumar]

Hi, Thank you very much for your response. I have a very basic question though. When we initialize RoutingModel like -

routing = pywrapcp.RoutingModel(numbers_customers * 2,numbers_vehicles,

                                        vehicles.origins,vehicles.destinations)

It automatically assigns the index to the nodes, say from 0 to range(numbers_customers * 2), right? So we'll need to put the loop here like -

for i in range(numbers_customers):

        solver.Add(routing.CumulVar(i, "pos") < routing.CumulVar(number_customers + i, "pos"))

OR like this -

for i in range(numbers_customers):

        node = routing.IndexToNode( i )

        next_node = routing.NextVar( node )

        solver.Add(routing.CumulVar(node, "pos") < routing.CumulVar(next_node, "pos"))

Which one is right? Second one makes more sense to me.

Regards,

On Mon, Mar 14, 2016 at 4:29 AM Greg Kerr <greg....@gmail.com> wrote:

Hi, I did manage to solve this. I added a dimension with "AddConstantDimension". The parameters are "value, capacity, fix_start_cumul_to_zero, name".
Setting value to 1, capacity to the number of nodes you have and fix_start to True, you essentially give each node a value of 1 in your new dimension (I named it "pos").

You can then add a constraint that requires a pick-up node's position to precede a corresponding drop off node. You do this by accumulating all the 1s in the "pos" dimension of the potential solution up until the node you're interested in.
I used python, so adding the constraint looked like this:

solver.Add(routing.CumulVar(d_index, "pos") < routing.CumulVar(s_index, "pos"))

where d_index/s_index are the internal or-tools node indices returned by "NodeToIndex()".

I hope this helps, let me know if you need more explanation.

Greg

[Amit Kumar]

Hi,

So when we write routing.AddConstantDimension(1, self.users.numbers * 2, True, "Position"), we assign the value 1 to all the nodes initially but how it is increasing for the next nodes visited? Does the solver do that?

[Jonas Frank]

Hi Amid,

i did exactly what you said, but it seems not to make any difference to my output.

Here is my code:

static void SolveVRP()

        {

            //this is called node!

            int[,] costs =     {{0,     2451,   713,    1018,   1631,   1374,   2408,   213,    2571,   875,    1420,   2145,   1972},  // New York

                                {2451,  0,      1745,   1524,   831,    1240,   959,    2596,   403,    1589,   1374,   357,    579},   // Los Angeles

                                {713,   1745,   0,      355,    920,    803,    1737,   851,    1858,   262,    940,    1453,   1260},  // Chicago

                                {1018,  1524,   355,    0,      700,    862,    1395,   1123,   1584,   466,    1056,   1280,   987},   // Minneapolis

                                {1631,  831,    920,    700,    0,      663,    1021,   1769,   949,    796,    879,    586,    371},   // Denver

                                {1374,  1240,   803,    862,    663,    0,      1681,   1551,   1765,   547,    225,    887,    999},   // Dallas

                                {2408,  959,    1737,   1395,   1021,   1681,   0,      2493,   678,    1724,   1891,   1114,   701},   // Seattle

                                {213,   2596,   851,    1123,   1769,   1551,   2493,   0,      2699,   1038,   1605,   2300,   2099},  // Boston

                                {2571,  403,    1858,   1584,   949,    1765,   678,    2699,   0,      1744,   1645,   653,    600},   // San Francisco

                                {875,   1589,   262,    466,    796,    547,    1724,   1038,   1744,   0,      679,    1272,   1162},  // St. Louis

                                {1420,  1374,   940,    1056,   879,    225,    1891,   1605,   1645,   679,    0,      1017,   1200},  // Houston

                                {2145,  357,    1453,   1280,   586,    887,    1114,   2300,   653,    1272,   1017,   0,      504},   // Phoenix

                                {1972,  579,    1260,   987,    371,    999,    701,    2099,   600,    1162,   1200,   504,    0}};    // Salt Lake City

            string[] city_names = { "New York", "Los Angeles", "Chicago", "Minneapolis", "Denver", "Dallas", "Seattle", "Boston", "San Francisco", "St. Louis", "Houston", "Phoenix", "Salt Lake City" };

            int num_locations = city_names.Length;

            RoutingModel routingModel = new RoutingModel(num_locations, 1, 0);

            RoutingSearchParameters search_parameters = RoutingModel.DefaultSearchParameters();

            //optional: enables the solver to escape a local minimum

            //search_parameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch;

            //search_parameters.TimeLimitMs = 10000;

            NodeEvaluator2 cost_between_nodes = new Cost(costs);

            routingModel.SetArcCostEvaluatorOfAllVehicles(cost_between_nodes); //oder SetVehicleCost wenn Fahrzeuge unterschiedliche Kostenmatrix haben

            Solver solver = routingModel.solver();

            string rank_name = "rank";

            routingModel.AddConstantDimension(1, num_locations, true, rank_name);

            var highPriorityVarIndex = routingModel.NodeToIndex(3);//Minneapolis

            var lowPriorityVarIndex = routingModel.NodeToIndex(0);//New York

            //Constraint MinneapolisBeforeNewYork = solver.MakeLess(routingModel.CumulVar(highPriorityVarIndex, rank_name), routingModel.CumulVar(lowPriorityVarIndex, rank_name));

            Constraint MinneapolisBeforeNewYork = routingModel.CumulVar(highPriorityVarIndex, rank_name) < routingModel.CumulVar(lowPriorityVarIndex, rank_name);

            solver.Add(MinneapolisBeforeNewYork);

            RoutingDimension rank_dimension = routingModel.GetDimensionOrDie(rank_name);

            Assignment assignment = routingModel.SolveWithParameters(search_parameters);

            if (assignment != null)

            {

                Console.WriteLine("Total distance: " + assignment.ObjectiveValue().ToString() + "miles");

                //Ergebnis ansehen:

                //index is the index of the variable that represents the starting node of the route, called the depot. The index of a node variable is not always the same as the index of the node itself (its row number in the locations array). 

                //So, when we add nodes to the route displayed in the output, we convert the indices of node variable to node indices, using the method routing.IndexToNode()

                long index = routingModel.Start(0); //vehicle 0

                StringBuilder route = new StringBuilder();

                route.Append("Route: ");

                do

                {

                    route.Append(city_names[routingModel.IndexToNode(index)] + " (Time: " + assignment.Min(rank_dimension.CumulVar(index)) + ", " + assignment.Max(rank_dimension.CumulVar(index)) + ") -> ");

                    index = assignment.Value(routingModel.NextVar(index));

                } while (!routingModel.IsEnd(index));

                route.Append(city_names[routingModel.IndexToNode(index)] + " (Time: " + assignment.Min(rank_dimension.CumulVar(index)) + ", " + assignment.Max(rank_dimension.CumulVar(index)) + ")");

                Console.WriteLine(route.ToString());

            }

            else

            {

                Console.WriteLine("No solution found");

            }

        }

Can you please help me to fix this?