Modelling additional constraint for node during delivery

[avadamn]

I’m working on a vehicle routing problem in which when a vehicle visits a nose, it required some additional resources to unload during delivery. These resources are drawn from a pool which can be shared across all nodes. The only constraint is these resources cannot be used simultaneously.

Does anyone have tips and/or example for this? Thanks

[Mizux]

I think you are looking for adding some Cumulative constraint You can see an example in the doc here where the maximum number of vehicles at depot is limited to two at the same time...

You'll need to use MakeFixedDurationIntervalVar

[avadamn]

Thanks @Mizux for the suggestion.

Unfortunately, the nodes I'm working with are disjunctive - it's not possible to control this via capacity of the depot. Is there something similar to AddNoOverlap for interval in routing model?

[Mizux]

Don't get it, why disjunctive constraint will interfere with the following constraint ?
I mean for each location you add an interval.

solver = routing.solver()
intervals = []
for i in range(num_location):
    # Add time windows for each location
    intervals.append(
        solver.FixedDurationIntervalVar(
            routing.CumulVar(routing.NodeToIndex(i), time),
            42, # to tweak according to your delivery time
            "loc_{} interval".format(i)))

then you can set that you can only have one interval at a time i.e. no overlap...

# Constrain the number of maximum simultaneous intervals accross location.
shared_ressource_capacity = 1
shared_ressource_usage = [1 for i in range(num_locations)]
solver.AddConstraint(
    solver.Cumulative(
        intervals,
        shared_usage,
        shared_capacity,
        "SharedRessource"))

you may be intested in MakeDistribute() otherwise

[avadamn]

Thank @Mizux – I misunderstood the earlier hint with regards to the example. I’m able to add the shared capacity into the model now. However I seem to encounter slightly strange result for some of the input.

The model is a modified model from CVRP model. Changes made were

1. Made 16 disjunctive set {1, 16}, … {15,30} and final node of 31 must be visited
2. Demand are used as service time of the nodes
3. Node 1-16 require additional shared resources ‘A’ while the rest required shared resource ‘B’
4. Set {12,27} must be visited before {8,23}

The result from the solve (original data node 18 – with 1time unit service time)

Route for vehicle 0:
  0 Time(0,0) -> 27 Time(0,20) -> 8 Time(20,26) -> 10 Time(26,34) -> 22 Time(39,43) -> 26 Time(43,45) -> 28 Time(45,60) -> 5 Time(60,67) -> 29 Time(72,74) -> 30 Time(75,89) -> 31 Time(89,98)
Time of the route: 98min

Route for vehicle 1:
0 Time(0,0) -> 17 Time(20,39) -> 4 Time(39,58)
Time of the route: 58min

Route for vehicle 4:
 0 Time(0,0) -> 9 Time(0,16) -> 21 Time(60,72) -> 18 Time(72,73) -> 16 Time(73,91)
Time of the route: 91min

From shared resources perspective:

Resource A
9 Time(0,16) -> 8 Time(20,26) -> 10 Time(26,34) -> 4 Time(39,58) -> 5 Time(60,67) -> 16 Time(73,91)

Resources B
27 Time(0,20) -> 17 Time(20,39) -> 22 Time(39,43) -> 26 Time(43,45) -> 28 Time(45,60) -> 21 Time(60,72) -> 18 Time(72,73) -> 29 Time(72,74) -> 30 Time(75,89) -> 31 Time(89,98)

From this, we can see that node 29 and 18 are served at the same time despite of using the shared resources. Increasing service time to > 1 will eliminate this behavior.

The second issue encountered when trying to add more than one shared resources constraints into the model. For this case, the set {1,1 6} was changed to required both shared resource A&B.

Route for vehicle 0:
 0 Time(0,0) -> 27 Time(0,20) -> 8 Time(20,26) -> 10 Time(26,34) -> 17 Time(34,53) -> 22 Time(53,57) -> 26 Time(57,59) -> 28 Time(59,74) -> 29 Time(74,76) -> 30 Time(76,90) -> 31 Time(90,99) ->Time of the route: 99min

Route for vehicle 1:
 0 Time(0,0) -> 18 Time(20,22) ->Time of the route: 22min

Route for vehicle 4:
 0 Time(0,0) -> 9 Time(0,16) -> 21 Time(20,32) -> 5 Time(53,60) -> 4 Time(60,79) -> 16 Time(79,97) ->Time of the route: 97min

For this case, set {1, 16}, node 16 was visited between 79-97 and required resources of A & B. However, I also have node 31 being served between times 90-99 requiring resource B.

Appreciate your input on this

[Mizux]

My 2 cents,
Supposing:

• you have a SlackVar capacity not null
• you are displaying the Min/Max of your CumulVar
  note: this time are the available start time of the delivery not the duration/end time...
• Node 18 and 29 have a service time of 1 unit
• Constraint solver use int (i.e. discrete values/range) so we can enumerate each values.

I would say for node 18 in range [72,73] and node 29 in range [72,74] means solver find several solutions:

• Node 18 with start time 72 (i.e. end time 73), and node 29 with start time 73 or 74 won't overlap
• Node 18 with start time 73 (i.e. end time 74), and node 29 with start time 72 or 74 won't overlap

-> solver return 18 in range [72,73] and 29 in range [72,74] since there is feasible solution, up to you to solve the "details" of interpretation.

Solver return a aggregate of range for each node not a "collection" of range with constraint/relation/interdependence with other node range.
kind of "(29: [73,74] if 18:{72}) or (29:{72,74} if 18:{73})"
note: this is due to the SlackVar which can add waiting time (buffering?) more/less at different places while still keeping the solution with the same objective value.

[avadamn]

Thanks for the clear explanation.

One final question, is there example I can refer to change the objective value of the model? I'm more interested in minimizing makespan rather than the total time vehicle spent in the system.

[Mizux]

I would say https://developers.google.com/optimization/routing/vrp#global_span you have an example usage.
or you can look at https://github.com/google/or-tools/tree/mizux/doc/doc and compare vrp.py and vrpgs.py.

and my comment on GlobalSpan in #685 (comment)

One caveat: for first strategy you must specify a setArcCost() to steer the solver to find a first "good" solution, side effect cost of the route is added to the objective 😞
Workaround -> set a big coeff on GlobalSpan so solver has more incentive to reduce your GlobalSpan than optimizing only the arc cost sum...