Adding / Decreasing capacity of a vehicle when visiting nodes

[VilleKokkarinen]

Is it possible to alter the vehicle's capacity mid route?
(i'm using .Net, but if you have a similar solved solution, in another language it's more than fine for me to convert.)

Consider the next situation:
Truck starts at depot,
Goes to location 1, picks up a container with volume X
Goes to location 2, picks up up to X amount of material into the container.
Goes to location 3, drops off the material.
Goes to location 1, drops off container.
Goes to depot.

I've thought about different methods on how to manage this, and if it's possible to alter the vehicle capacity of certain dimension mid route it would probably be the best and cleanest solution.

=> picking up a container with max capacity of 1000 units, would allow the truck to then pickup material of 1000 units, and when the truck returns that container, it can no longer pickup material.

The containers can be of various sizes which makes this such a problem for myself to think about...

Currently i'm adding constraints to force visiting a container node before the material nodes, and the truck is only constrained by the weight of the container + material, even if the container would be too small to fit all the material while the weight stays below the max allowed.

[sschnug]

Imho capacity-reasoning is typically based on the routing-solvers dimension-accumulation concept which itself is based on static / a-priori defined arc-costs/effects in regards to this dimension. This would render support for something like alter the vehicle's capacity mid route quite surprising (as you probably lose all invariants based on this static design).

(I'm ignoring time-dependent transits here because i don't much about them except for: they are probably still a bit experimental and i expect them to be troublesome).

Did you try something silly as (disclaimer: i did not think in depth about it):

• Introduce a capacity(-accumulation) dimension as usual
  • BUT: instead of starting at 0 and moving in-between [0,X], we will:
    • Start at large constant bigM
    • Upper-bound for capacity @ bigM
  • NOW:
    • Picking up a container adds negative capacity proportional to the containers size
    • Picking up material adds positive capacity
    • Droping of material adds negative capacity
    • Dropping of container adds positive capacity

So for example:

• big; = 1000 <= 1000
• pick up container with size 100 NEGATIVE: 900 <= 1000
• pick up material with size 10 POSITIVE: 910 <= 1000
• pick up material with size 90 POSITIVE: 1000 <= 1000
• drop of material with size 50 NEGATIVE: 950 <= 1000
• drop of material with size 50 NEGATIVE: 900 <= 1000
• drop container with size 100 POSITIVE: 1000 <= 1000

The only reason we do this strange big-M stuff is because the dimensions are by definition quite asymmetric due to the non-negativity assumption (it's a feature, not a bug as people familiar with linear-programming will understand).

Our focus here is: material-load is limited by container-capacity. Our big-M capacity serves as bound there. After having loaded container=100, we can not surpass 100 of load.

Seeing this, there are two issues:

• we can unload more than we loaded
  • i guess we should introduce a second capacity-dimension which ignores containers and only keeps load/unload in check (basic start=0 dim without upper-bound)
    • second dimension in the following sense: both are constraints and both restrict the solution-space / both are active
• we are missing container add/remove sequence rules
  • i don't know what exactly you need (e.g. forbid having 2 containers loaded at once) but i guess there are chances to model this through:
    • another dimension with +-1 for container-nodes (start=0, capa=1)
    • VisitTypes(?)