Penalty size
578 views
Skip to first unread message
R2 D2
Jul 2, 2021, 7:53:02 AM7/2/21
to or-tools-discuss
My VRP is based on service time + driving time: serviceTime[node_from] + drivingTime[node_from][node_to]
Values vary from minutes to hours, expressed in seconds.
Customers are assigned importance values in the range between 0 and 100 (0 - the least important, 100 - the most important)
I want to allow the solver to drop some locations to make the solution feasible.
Significant criteria are customer value and driving time. Service times are not meaningful.
What penalty values should I use for the "addDisjunction" method?
Values vary from minutes to hours, expressed in seconds.
Customers are assigned importance values in the range between 0 and 100 (0 - the least important, 100 - the most important)
I want to allow the solver to drop some locations to make the solution feasible.
Significant criteria are customer value and driving time. Service times are not meaningful.
What penalty values should I use for the "addDisjunction" method?
igor r
Jul 2, 2021, 2:01:18 PM7/2/21
to or-tools-discuss
You probably can also add another dimension which will count "scores" when serving a customer and each customer will have another score and you will need to maximize the score
R2 D2
Jul 6, 2021, 5:27:05 AM7/6/21
to or-tools-discuss
Maybe, I dont'know. I want the solver to find a route that is a compromise between distance travelled and the value (importance) of visited customers.
I mean the route distance should be minimized, whereas customers value should be maximized, so there should be a tradeoff between the shortest possible distance and the greatest value of visited customers.
Using big penalty values (10.000 - 100.000) results in important customers being selected by the solver, but also significantly increases the total distance of the
route.
On the other hand, using low penalty values reduces the amount of visited customers below optimal level.
You probably can also add another dimension which will count "scores" when serving a customer and each customer will have another score and you will need to maximize the score
blind.line
Jul 10, 2021, 12:58:28 AM7/10/21
to or-tools...@googlegroups.com
Yes that is true, but there is no right answer for the solver to find. The point is to set things up so that the solver finds answers that *you* think look and feel right. The programmer must decide the trade off between the various facets. More distance but greater value, so what is the desired relationship between the two?
James
On Jul 6, 2021, at 02:27, R2 D2 <develo...@gmail.com> wrote:
--
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/37fd3f44-5665-4ae5-aecb-09bf6621bb1bn%40googlegroups.com.
R2 D2
Jul 12, 2021, 2:09:57 PM7/12/21
to or-tools-discuss
Can I have two dimensions simultaneously minimized by the solver?
Yes that is true, but there is no right answer for the solver to find. The point is to set things up so that the solver finds answers that *you* think look and feel right. The programmer must decide the trade off between the various facets. More distance but greater value, so what is the desired relationship between the two?James
Maybe, I dont'know. I want the solver to find a route that is a compromise between distance travelled and the value (importance) of visited customers.
blind.line
Jul 12, 2021, 2:36:53 PM7/12/21
to or-tools...@googlegroups.com
What does that even mean? If they are the same (time, distance, money, etc) then yes. But if one dimension is count-of-stops and the other is total-distance, minimizing stops and minimizing distance at the same time would be meaningless.
Economists like to convert everything to units of currency for exactly this reason. If one stop costs $500, and one mile costs $1, then you can combine and minimize together total cost, which is the sum of the dimensions stop-cost and travel-cost.
James
On Jul 12, 2021, at 11:10, R2 D2 <develo...@gmail.com> wrote:
--
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/1917e98a-23f3-4fb2-b8b0-a8ae74aca9b2n%40googlegroups.com.
R2 D2
Jul 12, 2021, 2:58:12 PM7/12/21
to or-tools-discuss
Maybe I am wrong, but as far as I know OR-Tools dimensions are independent from each other.
If just it was possible to minimize both travel time dimension and customer value dimension, then I think my problem could be solved by reversing customer values (assign 0 to the most important customers and 100 to the least important ones). All the examples I've seen so far use something like this:
for (int i = 0; i < data.num_vehicles; ++i) {
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)));
}
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)));
}
Perhaps I could just add:
routing.AddVariableMinimizedByFinalizer(customer_value_dimension.CumulVar(routing.Start(i)));
routing.AddVariableMinimizedByFinalizer(customer_value_dimension.CumulVar(routing.End(i)));
routing.AddVariableMinimizedByFinalizer(customer_value_dimension.CumulVar(routing.End(i)));
But I am not sure this should be done that way...
What does that even mean? If they are the same (time, distance, money, etc) then yes. But if one dimension is count-of-stops and the other is total-distance, minimizing stops and minimizing distance at the same time would be meaningless.
Economists like to convert everything to units of currency for exactly this reason. If one stop costs $500, and one mile costs $1, then you can combine and minimize together total cost, which is the sum of the dimensions stop-cost and travel-cost.James
Can I have two dimensions simultaneously minimized by the solver?
blind.lin...@gmail.com
Jul 12, 2021, 7:57:31 PM7/12/21
to or-tools...@googlegroups.com
Yes, dimensions are not related to each other in the code. That is
not what I am suggesting. What I am saying is that you, the modeler,
have to decide what it means to optimize both dimensions at once.
There are always tradeoffs, and you have to make that choice.
In the CP-SAT side of the fence, you have to make your own objective
function, so that is more obvious. In routing model land, the
objective is hidden behind API calls.
What I would do is to use maybe SetSpanCostCoefficientForVehicle
https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp#setspancostcoefficientforvehicle
To quote the docs,
"The cost for a vehicle is
span_cost = coefficient * (dimension end value - dimension start value)."
That gets lumped into the objective and minimized, so it is not useful
for maximizing (the coefficient can't be negative).
Since I think you want to maximize customer value, maybe you can do a
tricky hack with SetCumulVarSoft[Lower|Upper]Bound on
the end nodes for each vehicle
https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp#setcumulvarsoftlowerbound
(Set upper bound to zero to mimic minimizing, set lower bound to a
large number to mimic maximizing)
something like:
```python
impossible_customer_value = 1000
customer_value_factor = 2
for vehicle_id in range(manager.GetNumberOfVehicles()):
end_index = routing.End(vehicle_id)
customervaluedim.SetCumulVarSoftLowerBound(end_index,
impossible_customer_value,
customer_value_factor)
```
That is a little bit convoluted, and you can probably do better if you
think longer about it that I just did, but the idea is that the solver
will never be able to assign a high enough total customer value to hit
"impossible_customer_value", so the difference will be multiplied by the
factor and minimized.
What I was talking about in my earlier messages was the factors in
both of those API calls. Those factors are the rule to convert one
dimension into equivalent units of another dimension. If one unit of
customer value really is equal to one second, then the factor can be
1 (assuming your time is in seconds).
But an economist would recommend converting total_travel dimensions
into dollars (or equiv), and the same for customer value, then the
statement
minimize(total_travel +
Sum_all(i){factor_i*(impossible_customer_value - customer_value_i)})
(for all vehicles i)
will make sense, rather than being mostly useless.
--
James E. Marca
Activimetrics LLC
not what I am suggesting. What I am saying is that you, the modeler,
have to decide what it means to optimize both dimensions at once.
There are always tradeoffs, and you have to make that choice.
In the CP-SAT side of the fence, you have to make your own objective
function, so that is more obvious. In routing model land, the
objective is hidden behind API calls.
What I would do is to use maybe SetSpanCostCoefficientForVehicle
https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp#setspancostcoefficientforvehicle
To quote the docs,
"The cost for a vehicle is
span_cost = coefficient * (dimension end value - dimension start value)."
That gets lumped into the objective and minimized, so it is not useful
for maximizing (the coefficient can't be negative).
Since I think you want to maximize customer value, maybe you can do a
tricky hack with SetCumulVarSoft[Lower|Upper]Bound on
the end nodes for each vehicle
https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp#setcumulvarsoftlowerbound
(Set upper bound to zero to mimic minimizing, set lower bound to a
large number to mimic maximizing)
something like:
```python
impossible_customer_value = 1000
customer_value_factor = 2
for vehicle_id in range(manager.GetNumberOfVehicles()):
end_index = routing.End(vehicle_id)
customervaluedim.SetCumulVarSoftLowerBound(end_index,
impossible_customer_value,
customer_value_factor)
```
That is a little bit convoluted, and you can probably do better if you
think longer about it that I just did, but the idea is that the solver
will never be able to assign a high enough total customer value to hit
"impossible_customer_value", so the difference will be multiplied by the
factor and minimized.
What I was talking about in my earlier messages was the factors in
both of those API calls. Those factors are the rule to convert one
dimension into equivalent units of another dimension. If one unit of
customer value really is equal to one second, then the factor can be
1 (assuming your time is in seconds).
But an economist would recommend converting total_travel dimensions
into dollars (or equiv), and the same for customer value, then the
statement
minimize(total_travel +
Sum_all(i){factor_i*(impossible_customer_value - customer_value_i)})
(for all vehicles i)
will make sense, rather than being mostly useless.
> --
> 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/ad796d1e-cd0d-4706-a055-3870a42ef0d9n%40googlegroups.com.
> 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.
--
James E. Marca
Activimetrics LLC
Reply all
Reply to author
Forward
0 new messages