Vehicle specific precedence constraints

[Boyan Krastev]

Hello,

I am using OR Tools in C# to solve the Vehicle Routing Problem. So far I've managed to use successfully many of the available constraints, but I have difficulties dealing with one in particular. It is a kind of precedence constraint, which must be specific for each vehicle. Let's say I've got some nodes, some of which are high priority nodes and others are normal or low priority. The hight priority nodes must come first in each vehicle's list of nodes. 

I thought of using the CumulVar approach(with the time dimension), constrainting the CumulVar for each hight priority node to be less than the CumulVar for each normal or low priority node, but this would cause a vehicle, potentially able to continue with its normal priority nodes, to wait, because some other vehicle would not have taken all of its high priority orders yet. In short, it becomes a local(vehicle specific) precedence constraint, rather than a global one.

Any help or advise is highly appreciated,

Best regards - B. Krastev.

[Ken Alton]

You might try to set a CumulSoftUpperBound for the high priority nodes, to encourage them to be visited early.  This solution wouldn't have the issue that one vehicle would wait for another before starting it's low priority nodes.  However, depending on the size of the cost coefficient versus other time costs / constraints, a vehicle may still visit low priority nodes before high priority ones.  Also, the solver may put more high-priority nodes on vehicles with earlier available time ranges.

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

[Serg Levin]

Have you tried  to make your constraints on every high/low priority pair conditional , subject to both VehicleVars are in the same route, equal? 

понедельник, 3 июля 2017 г., 10:47:02 UTC+3 пользователь Boyan Krastev написал:

[Boyan Krastev]

Thanks for the response, unfortunately I think this solution will not work. RoutingModel.SetCumulVarSoftUpperBound() has the following signature: (int arg0, string arg1, long arg2, long arg3) which I suppose means "nodeIndex, dimensionName, valueOfTheUpperBound, penaltyCoefficient". The problem is that the value of the upper bound (CumulVar ( lowPriorityNodeIndex).Value() :: long ) is not known at the moment of the constraint setting, and therefore cannot be used in the method.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Boyan Krastev]

@Serg,

Thank you for the response, I have tried the following:

var sameVehicleConstraint = solver.MakeEquality(model.VehicleVar(highPriorityOrderIndex), model.VehicleVar(lowPriorityOrderIndex));
var priorityContraint = solver.MakeLessOrEqual(model.CumulVar(highPriorityOrderIndex, TimeDimensionName), model.CumulVar(lowPriorityOrderIndex, TimeDimensionName));
var expression = solver.MakeConditionalExpression(sameVehicleConstraint, priorityContraint, 1);
var constraint = solver.MakeGreaterOrEqual(expression, 1);


solver.Add(constraint);

but the precedence constraint is not satisfied. (The order is different than in the case when no constraints are added at all, but is not the correct order.) My guess is that I am missusing the methods. Can you give me some names of particular methods which have worked out for you?

[Vincent Furnon]

What are highPriorityOrderIndex and lowPriorityOrderIndex ? Do they correspond to nodes or variable indices (they're not necessarily the same) ?

--

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-discuss+unsubscribe@googlegroups.com.

[Boyan Krastev]

Hello Vincent,

In my tests I have a set of 26 nodes and 2 drivers, each having 2 depots (start and end). That makes a total of 26 + 2 + 2 = 30 nodes for the problem. in the RoutingModel c-tor I set starts[]  to be [26,28]  and ends[] to be [27,29] which means that the first 26 indices

(0 ~ 25) correspond to my order nodes. I sort the indices of the orders into groups according to their priority(i've got 4 priorities) and I iterate the groups two by two, setting the constraint as described in my previous response. 

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

[Vincent Furnon]

This means you need to get the variables indices from the nodes, calling model.NodeToIndex():

var highPriorityVarIndex = model.NodeToIndex(highPriorityOrderIndex);

var lowPriorityVarIndex = model.NodeToIndex(lowPriorityOrderIndex);

var sameVehicleConstraint = solver.MakeEquality(model.VehicleVar(highPriorityVarIndex), model.VehicleVar(lowPriorityVarIndex));

var priorityContraint = solver.MakeLessOrEqual(model.CumulVar(highPriorityVarIndex, TimeDimensionName), model.CumulVar(lowPriorityVarIndex, TimeDimensionName));

var expression = solver.MakeConditionalExpression(sameVehicleConstraint, priorityContraint, 1);

var constraint = solver.MakeGreaterOrEqual(expression, 1);

...

BTW I think there's maybe a more efficient way of modeling your constraint. If nodes in group A have a higher priority than nodes in group B, just forbid going from any node in B to a node in A. This can be done by removing all nodes from A (actually their respective variable index) from the NextVar of the nodes in B (or any lower priority group). This assumes all nodes have a priority.

Vincent

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

[Boyan Krastev]

Thank you, Vincent! 

I used the model.NextVar().RemoveValue() approach and it worked perfectly. If it matters for you, I'd mention that first I tried the CumulVar constraint approach, using the NodeToIndex method as you suggested, but it resulted in one correctly ordered route and one in all-wrong order, out of two in total. Anyway, thank you again for the second suggestion!

Boyan.

[Jander Alves]

Hello Boyan,
You can post here the solution that you used the model.NextVar (). RemoveValue ()? please.

[Jonas Frank]

Hello Vincent,

I hope you can help me. I'm trying out or-tools for a few days now. I get a simple tsp working, the only addition I need is to have some precedences for the locations.

This is my code for now (it's the example found under: https://developers.google.com/optimization/routing/tsp/tsp)

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" };

            RoutingModel routingModel = new RoutingModel(city_names.Length, 1, 0);

            RoutingSearchParameters search_parameters = RoutingModel.DefaultSearchParameters();

            Solver solver = routingModel.solver();

            //In this section I don't get any further...

            //Minneapolis before New York

            var highPriorityVarIndex = 4;//routingModel.NodeToIndex(highPriorityOrderIndex);

            var lowPriorityVarIndex = 0;//routingModel.NodeToIndex(lowPriorityOrderIndex);

            var priorityContraint = solver.MakeLessOrEqual(routingModel.CumulVar(highPriorityVarIndex, "precedence"), routingModel.CumulVar(lowPriorityVarIndex, "precedence"));

            solver.Add(priorityContraint);

            //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

            Assignment assignment = routingModel.SolveWithParameters(search_parameters);

            if (assignment != null)

            {

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

                //Ergebnis ansehen:

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

                StringBuilder route = new StringBuilder();

                route.Append("Route: ");

                do

                {

                    route.Append(city_names[routingModel.IndexToNode(index)] + " -> ");

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

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

                route.Append(city_names[routingModel.IndexToNode(index)]);

                Console.WriteLine(route.ToString());

            }

            else

            {

                Console.Write("No solution found");

            }

[Pritam Bhat]

I am trying to solve similar problem where I need to provide rank/priority to nodes to be visited.

It looks like lot of good discussion in this thread.

Can somebody summarize or share or guidance with some code blocks that would help.

Thanks

Pritam

[Louis Christopher]

The idea is to create a list of groups.
If this is your priority per node

[1, 1, 3, 1,1, 2, 2, 1]
This is your set of groups ordered by priority.
[ [0,1,3,4,7], [5,6], [2] ]

For node in a group, remove all the nodes from group 0 to current_index - 1
model.NextVar(5).RemoveValue(<0,1,3,4,7>)
model.NextVar(2).RemoveValue(<0,1,3,4,7,5,6>)

Just Ensure you don't run model.NextVar() on your depot mode or start/end nodes

[blind.lin...@gmail.com]

That's a nice hack. Thanks for sharing.

James

> >>>>>> the *correct* order.) My guess is that I am missusing the methods.

> >>>>>> Can you give me some names of particular methods which have worked out for
> >>>>>> you?
> >>>>>>
> >>>>>> On Friday, July 7, 2017 at 5:40:57 PM UTC+3, Serg Levin wrote:
> >>>>>>>
> >>>>>>> Have you tried to make your constraints on every high/low priority
> >>>>>>> pair conditional , subject to both VehicleVars are in the same route,
> >>>>>>> equal?
> >>>>>>>
> >>>>>>> понедельник, 3 июля 2017 г., 10:47:02 UTC+3 пользователь Boyan
> >>>>>>> Krastev написал:
> >>>>>>>>
> >>>>>>>> Hello,
> >>>>>>>> I am using OR Tools in C# to solve the Vehicle Routing Problem. So
> >>>>>>>> far I've managed to use successfully many of the available constraints, but

> >>>>>>>> I have difficulties dealing with one in particular. It is a kind of *precedence
> >>>>>>>> constraint*, which must be *specific for each vehicle*. Let's say
> >>>>>>>> I've got some nodes, some of which are *high priority* nodes and
> >>>>>>>> others are normal or low priority. *The hight priority nodes must
> >>>>>>>> come first in each vehicle's list of nodes*.

> >>>>>>>> I thought of using the CumulVar approach(with the time dimension),
> >>>>>>>> constrainting the CumulVar for each hight priority node to be less than the
> >>>>>>>> CumulVar for each normal or low priority node, but this would cause a
> >>>>>>>> vehicle, potentially able to continue with its normal priority nodes, to
> >>>>>>>> wait, because some other vehicle would not have taken all of its high
> >>>>>>>> priority orders yet. In short, it becomes a local(vehicle specific)
> >>>>>>>> precedence constraint, rather than a global one.
> >>>>>>>>
> >>>>>>>> Any help or advise is highly appreciated,
> >>>>>>>> Best regards - B. Krastev.
> >>>>>>>>
> >>>>>>> --
> >>>>>> 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.
> >>>>>>
> >>>>>
> >>>>> --
> >>>> 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.
> >>>>
> >>>
> >>>
>
> --
> 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/57efa9f9-25ef-4d2c-be1e-510936373adf%40googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.


--

James E. Marca

[Dheeraj Vasudeva Rao Velaga]

Hey guys , I am trying to solve similar type of problem but in python. After you group them based on priority, What would you do? Is there a way you can tell the solver to prioritize group 4 over group 3 etc..? I was trying to see if there is a way you can set this. Can someone help me?