Add fixed costs for soft time window in solving routing problem

[kaikezhang]

I am using Python to solve routing problem where I need to impose fixed costs and variable costs on nodes with delayed service. I noticed the SetCumulVarSoftUpperBound function allows me to add variable costs, that is cost = coefficient * (cumulVar - upper_bound) if cumulVar > upper_bound. In my problem, I also need to impose fixed costs, that is, cost = fixed_costs + coefficient * (cumulVar - upper_bound) if cumulVar > upper_bound. Is there any way I can achieve this?

[mslazynski]

I would also like to find a solution for this particular scenario. IMHO it's impossible right now.

[Mizux]

Did you try to use two nodes and two disjunctions ?
The main idea,

• you can visit one node A_1 in time (hard TW) otherwise,
• you have to visit location A_2 which has a SoftUpperBound + the drop of A_1 will add the fixed cost as the penalty ;)

e.g. node A with TW[13,42], fixed cost = 31, coeficient = 23

• first we replace this node A by two node: A_1, A_2 with:
  time_dimension.Cumulvar(A_1).setRange(13, 42) i.e. hard TW so A_1 can only be visited "in time".
  IIRC time_dimension.SetCumulVarSoftUpperBound(A_2, 42, 23) <= soft upper range, i.e. if we can't visit A_1 we can still visit A_2 but we have to pay the coefficient * delta = cost
• Add disjunction so only one node must be visited
  routing.AddDisjunction([A_1, A_2], /*penalty*/0, 1)
  note: here we don't care of the penalty stuff, just want to express "only visit one node among both"
• Add an other disjunction if A_1 is dropped then pay the fixed cost (here the trick to add the fixed cost) !
  routing.AddDisjunction([A_1], /*penalty aka fixed cost*/ 31, 1)

warning: Still didn't had the time to test it, any feedback welcome !