My 0.5 cent
DISCLAIMER: THIS IS NOT TESTED AT ALL (any feedback welcome)
Technically you can have a "value memory" per node using a SlackVar:
1) Use the IntExpr `NextVar(I) == J` to check (i.e. having a BooleanVar) if "node J is the next node of node I".
2) use a SlackVar from a dummy dimension (let's call it DIM_ONE) as node memory to store the max(the current node, the previous slack)
2.1) DIM_ONE dimension has a 0 constant transit callback, a very big capacity and slack range that must be at least PEAK cost
3) You should have the "peak" value in the last node's SlackVar before the end node (and an ugly CumulVar)
4) Create an other dummy dimension (let's call it TWO) whose is zero everywhere only slackVar of last node before end node == slackVar of dimension ONE
5) Use dimTWO.SetCumulVarSoftUpperBound(routing.End(0), 0, penalty_per_unit) to have a peak cost added to the objective.
6) Profit ?
e.g. route S(0) -> 13 -> 42 -> 31 -> E(0),
with: cost(13) = 5, cost(42) = 10 (our peak), cost(31) = 8
```md
| Dim/Field | S | 13 | 42 | 31 | E |
| -- | -- | -- | -- | -- | -- |
| Point cost | 0 | 5 | 10 | 8 | 0 |
|ONE/Slack | 0 | 5 | 10 | 10 | NA | < max (cost(N), slack(N-1))
|ONE/Cumul| 0 | 0 | 5 | 15 | 25 | < pill of xxxxx
|TWO/Slack | 0 | 0 | 0 | 10 | NA | < should have all slack to 0 except the "last one"
|RWO/Cumul| 0 | 0 | 0 | 0 | 10 | <= What we are looking for ! (we can use CumulVarSoftUpperBound to create an "objective's cost" from it)
```
pseudo code:
# Initialisation
cost = [......] # your point cost array
routing.AddConstantDimensionWithSlack(
0, # transit 0
BIG_ENOUGH, # capacity: don't care jsut need to be able to store at least PEAK*ROUTE_LENGTH in worst case
PEAK, # slack_max: to be able to store peak in slack
True, # Fix StartCumulToZero not really matter here
"ONE"
)
dim_one = routing.GetDimensionOrDie("ONE")
routing.AddConstantDimensionWithSlack(
0, # transit 0
PEAK, # capacity: we only want to be able to have PEAK value in CumulVar(End)
PEAK, # slack_max: to be able to store peak in slack
True, # Fix StartCumulToZero YES here
"TWO"
)
dim_two = routing.GetDimensionOrDie("TWO")
# force depot Slack to be cost since we don't have any predecessor...
for v in range(manager.GetNumberOfVehicles()):
dim.SlackVar(routing.Start(v)).SetValue(cost[0])
# Step by step relation
for I in all_node:
if I is in end_nodes_list:
continue # again end node don't have any successor + end node don't have any slack...
for J in all_node:
# todo(mizux) test what happen when using NextVar(EndNode) for fun ;)
cond = routing.NextVar(I) == J
expr = dim_one.SlackVar(J) == solver.Max(dim_one.SlackVar(I), cost[j])
solver.ConditionalExpression(cond, expr, 0) # not tested should do the implication
# relation between dimensions, copy last node Slack from dim ONE to dim TWO
for I in all_node:
cond = routing.NextVar(I) == solver.IntVar([end_nodes_list]) # The node after I is an End node
expr = dim_one.SlackVar(I) == dim_two.SlackVar(I)
solver.ConditionalExpression(cond, expr, 0)
# Should force all others dim_two slack var to zero...
for v in range(manager.GetNumberOfVehicles()):
# routing.AddVariableMinimizedByFinalizer(dim_two.CumulVar(routing.End(v))); # not sure is needed
dim_two.SetCumulVarSoftUpperBound(routing.End(0), 0, penalty_per_unit) # step 5)
```
note: I'll try to create a gist and/or a github discussion (Find Max costly node in a route ? (any suggestion welcome)) to have syntax highlight etc...
mailing list don't support markdown and message edit...
PS:
std::pair<int, bool> AddConstantDimensionWithSlack(
int64_t value, int64_t capacity, int64_t slack_max,
bool fix_start_cumul_to_zero, const std::string& name);
YUP slack_max is AFTER [vehicle] capacity argument ONLY in this method ! Google consistency for the win ;)
-> maybe we should fix it for v9.0 (and break the code of everyone using it #ConsistencyMatter #YouCanBlameMe (ed don't know if this #tag exists))