6
$\begingroup$

I used the Vehicle Routing Problem example that has the objective of minimizing total distance traveled for each vehicle.

Suppose that each order to pick up for each vehicle at each node has a priority list, i.e. expedited vs standard. How can I minimize the distance (main objective) but also "soft" respect the priority list if possible?

Note that the priority at each node can change depending on the type of the order that exists at each node.

An example would be let's say we have 3 vehicles to deliver 10 packages each where we have 10 expedited packages and 20 standard packages. The optimal solution given the objective value would perhaps be the following:

  • Vehicle 1: 5 expedited packages, 5 standard packages
  • Vehicle 2: 2 expedited packages, 8 standard packages
  • Vehicle 3: 3 expedited packages, 7 standard packages

Yes, we are prioritizing the expedited packages but if having 1 vehicle delivering all of the 10 expedited packages yield higher distance traveled then truly it is not optimal.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Does soft mean that a standard package could be delivered before an expedited package is delivered as long as some other value is met to honor "expedited"? If so, what makes an expedited package "expedited"? That could help answer the question. $\endgroup$
    – Wesley Dyk
    Jun 10, 2020 at 0:05
  • $\begingroup$ My use case is a modified version of VRP. Let's say out of 100 packages to deliver, we set 10 vehicles to deliver 10 packages each. When we think about the main objective which is to minimize the total distance traveled as well as the priority list, what is optimal given both? There are vehicles that might have a mixture of expedited and standard orders while other vehicles might have either expedited or standard orders. My thinking is that I would put a higher weight toward an expedited order but not necessarily enforce that it has to be delivered prior if that makes sense. $\endgroup$
    – Mario Huang
    Jun 10, 2020 at 3:47
  • $\begingroup$ Dear Mario. You definition of priority lists is messy and it is impossible to understand (at least for me). You should properly define what is a priority list, and when a given vehicle routing solution (set of routes) satisfies the given priority list and when does not. $\endgroup$
    – Ruslan Sadykov
    Jun 10, 2020 at 9:30
  • $\begingroup$ My apology for the unclear definition. See the answer by Luke. $\endgroup$
    – Mario Huang
    Jun 10, 2020 at 15:20

2 Answers 2

Reset to default
6
$\begingroup$

If I understand your problem correctly, you have a standard CVRP and a second (soft) objective.

You are therefore in the wonderful world of multi-objective optimization.

Typically what you do is try to turn this problem into a problem with a well defined optimal solution. There are some ways to do this: lexicographical ordering of objectives (Cplex calls this lexicographic objective),goal programming, using a linear combination of the objective functions (Cplex calls this blended objective), attainment levels or a combination of these techniques.

Depending on the context you might want to generate a list of good solutions and have someone pick the best one by hand. What you want your algorithm to do then is called listing the pareto efficient solutions.

If I understand your question correctly, you want the distance objective to be optimal and then among the optimal solutions you want the one with the best value for your secondary objective. You should therefore look into the lexicographical ordering of your objectives.

You might also be in the world of soft constraints/objectives:

Generally you want to allow the soft constraint to be allowed to be violated, add a variable that measures the violation, and add the minimization of that variable as objective. depending on your problem you then use the multi-objective optimizaion techniques to turn the problem well defined again.

I hope this helps, good luck and keep on solving problems!

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks a lot! The second option is definitely what I was thinking of but first option sounds interesting. Is there any example of similar implementation using or-tools or resources that you could share ? $\endgroup$
    – Mario Huang
    Jun 10, 2020 at 15:14
  • $\begingroup$ Not that I know of $\endgroup$
    – PSLP
    Jun 13, 2020 at 15:48
1
$\begingroup$

Given that we have expedited and standard packages to be delivered at the start of the planning, I am assuming that if you have limited capacity to fit all orders in a trucks, pick a solution where expedited orders are in the solution.

Example:100 packages to deliver, with 10 trucks with 50 standard and 50 expedited. Say in this case, we can have 2 solutions: Sol1 (50 standard, 45 expedited), Sol2 ( 45 standard , 50 expedited). Pick Sol 2.

In a way we do not want to miss planning any expedited orders but while doing so do minimize the distance traveled. For a typical CVRP MIP formulation, for all orders I will have a binary variable indicating whether I can fit this order in a truck. This binary variable will go in the constraint "all orders have to either in a truck or not planned" constraint. I will put a high penalty for all expedited orders binary variables in the objective function.

Improve this answer
$\endgroup$

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.