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 !

[weihenglim]

In this case, I am trying to account for the duplicate nodes when modelling the pickup and delivery points.

For example, given 2 locations [A, B], we end up having 4 nodes after the duplication: [A_1, A_2, B_1, B_2] where A_1 and B_1 are the 'on-time' nodes while A_2 and B_2 are the 'late' nodes as suggested in your original answer (to simulate the fixed cost via 2 disjunctions).

If we have a pickup/delivery pair of {A, B}, this means that we can pick up from either A_1 or A_2 and drop off at either B_1 or B_2 (hence why I had a nested loop to account for all possible combinations). Hopefully this gets my point across, sorry if my explanation seems a bit confusing.

[Mizux]

So you want ot model 1 P&D from [A_1, A_2] to [B_1, B_2].
So I would suggest to use AddPickupAndDeliverySets.

a_1 = manager.NodeToIndex(A1)
a_2 = manager.NodeToIndex(A2)
dij_a = routing.AddDisjunction([a_1, a_2])
routing.AddDisjunction([a_1], PENALTY) # not on time aka visiting a_2 instead of a_1

b_1 = manager.NodeToIndex(B1)
b_2 = manager.NodeToIndex(B2)
dij_b = routing.AddDisjunction([b_1, b_2])
routing.AddDisjunction([b_1], PENALTY) # not on time aka visiting b_2 instead of b_1

routing.AddPickupAndDeliverySets(dij_a, dij_b)

warning: not tested/played with this API yet so I can't guaranty it will work smoothly ^^;

[weihenglim]

Just ran some manual tests on a few sets of data and AddPickupAndDeliverySets seems to work perfectly.

Thanks for your help, really appreciate it.

[johnnykwan21]

@weihenglim you can manage it in the transit callback with a map or few if e.g.

map = [
  0, 1, ..., N, # orignal node
  1, 1, 3, 5, 4, # duplicate node orignal index
]

def my_transit(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    from_node = map[from_node] # map to original node so in range 0-N
    to_node = manager.IndexToNode(to_index)
    to_node = map[to_node]
    return matrix[from_node][to_node] # orignal NxN matrix is sufficient

hi there, i'm now solving a similar problem. would like to know any demo code of how to split node A into A_1 & A_2? the origin node could be set as a on-time node, so just set one dummy A_2 node as the late node. but i can't figure out how to implement this. thanks so much!

[weihenglim]

For the splitting of nodes I just included an additional map array in the data model like so:

data['duplicate_map'] = [
    i if i < len(data['time_matrix']) else i - len(data['time_matrix']) + 1 
    for i in range(0, len(data['time_matrix']) * 2 - 1)
]

The time callback will then look something like this:

def time_callback(from_index, to_index):
    """Returns the travel time between the two nodes."""
    # Convert from routing variable Index to time matrix NodeIndex.
    from_node = data['duplicate_map'][manager.IndexToNode(from_index)]
    to_node = data['duplicate_map'][manager.IndexToNode(to_index)]
    return data['time_matrix'][from_node][to_node] + data['service_times'][from_node]

Also don't forget to account for the extra nodes when creating the routing index manager:

manager = pywrapcp.RoutingIndexManager(len(data['duplicate_map']), data['num_vehicles'], data['depot'])