Originally posted by: CedricVB

Hello,

I'm modeling a VRP (pickup&delivery) in which nodes can be visited by multiple vehicles.
Multiple vehicles can also be used to fulfill one customer order.

e.g. a customer order contains 40 palettes. In case we've got a number of vehicles with a maximum load of 30 palettes,
at least 2 vehicles will have to be used to fulfill the order.

I've got a dvar "z" which decides how many items (palettes) of a certain customer order will be handled by a truck.

dvar int z[Orders][Camions];

 

cumulFunction load[k in Camions] = step(0,0)

              - sum (d in Deliveries) stepAtStart(visit[k][d.destination], z[d][k])

              + sum (d in Deliveries) stepAtEnd(visit[k][d.from], z[d][k]);

Now I'd like to have a function that describes the load of a vehicle over time. At first I thought it would be possible to do this with a cumulFunction, but the stepAtStart/stepAtEnd functions don't accept a dvar as second argument. How should I go about this?

I'd be most thankful if you could help me out.

Kind regards,
Cedric

Originally posted by: Petr Vilím

Hello Cedric,

the trick is to use elementary stepAtFoo functions with variable height. For example:

cumulFunction loadStep = stepAtStart(someIntervalVar, 0, maxPalettes);

In a way the statement above creates a new decision variable with domain [0, maxPalettes]. Its value can be accessed using function heightAtStart. For example to force the step to be bigger than 3:

heightAtStart(someIntervalVar, loadStep) > 3;

Or to create another step with the same height:

cumulFunction unloadStep = stepAtEnd(otherIntervalVar, 0, maxPalettes);

heightAtStart(someIntervalVar, loadStep) == heightAtEnd(otherIntervalVar, unloadStep);

Finally, the main cumul function should be combined from individual steps. In our simple case:

loadStep - unloadStep <= truckCapacity;

I hope it helps, Petr

Originally posted by: CedricVB

Awesome, thank you for your example! This is all very new to me.

I'm still a bit lost though on how to apply this part for all intervals in my sequence:

heightAtStart(someIntervalVar, loadStep) == heightAtEnd(otherIntervalVar, unloadStep);

heightAtEnd(someSequence, THISINTERVAL, unloadStep) ==  heightAtStartOfNext(someSequence, THISINTERVAL, loadStep)

I think this can be done with writing expression that uses typeOfNext, but I'm not sure if this is the right way to go about it.

Originally posted by: Petr Vilím

Hello Cedric,

I'm not sure that I understand your needs correctly. Load and unload should be direct successors? The truck cannot load/unload something else along the way? In this case, is the cumul function really needed? Different orders do not compete over the capacity of the truck in this case. I get it wrong probably, could you describe in more detail the problem you want to solve?

Just a side remark. Function typeOfNext can be used with for sequence variable and noOverlap. In other words, for activities that cannot overlap. It cannot be used with cumul function though. Activities on cumul functions (that is pulses and steps) can overlap. And therefore there is also no "next". Of course, sometimes it is useful to model the problem by a cumul function and noOverlap over the same set of intervals.

Petr

Originally posted by: CedricVB

It took some time for me to understand that the "heightAt" is actually the "size of the modification being applied to the cumulFunction at that point". I thought it was the absolute height (the actual load) of the truck at the point. Once that was clear, I was able to model the VRP thanks to your help.

It's weird though that in the problem browser, the values of the individual cumulFunctions (loadStep[k] and unloadStep[k]) don't show the correct value. They just show: 

stepwise{ 0 -> 0; 0 } stepwise{ 0 -> 0; 0 } stepwise{ 0 -> 0; 0 } stepwise{ 0 -> 0; 0 }

The combined cumulFunction shows the correct load though:

cumulFunction load[k in Camions] = loadStep[k] - unloadStep[k];

stepwise{ 0 -> 360; 5 -> 508; 0 -> 563; 28 -> 637; 15 -> 801; 0 } stepwise{ 0 -> 589; 33 -> 688; 0 } stepwise{ 0 -> 360; 10 -> 534; 0 -> 569; 7 -> 668; 0 } stepwise{ 0 -> 435; 5 -> 537; 0 -> 578; 17 -> 660; 0 }

Also decision expressions that use the heightAtStart functions, will always report "0" in the problem browser (though they are correctly calculated during optimization).

Weird! But no biggie :)
Thanks for your assistance!