Topic
4 replies Latest Post - ‏2013-05-07T17:07:02Z by CedricVB
CedricVB
CedricVB
4 Posts
ACCEPTED ANSWER

Pinned topic Truck load in VRP

‏2013-04-25T00:02:26Z |

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

Updated on 2013-04-25T00:03:01Z at 2013-04-25T00:03:01Z by CedricVB
  • Petr Vilím
    Petr Vilím
    14 Posts
    ACCEPTED ANSWER

    Re: Truck load in VRP

    ‏2013-04-29T07:53:58Z  in response to CedricVB

    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

    Updated on 2013-04-29T07:58:30Z at 2013-04-29T07:58:30Z by Petr Vilím
    • CedricVB
      CedricVB
      4 Posts
      ACCEPTED ANSWER

      Re: Truck load in VRP

      ‏2013-04-30T19:43:57Z  in response to Petr Vilím

      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);
      

      I'm looking for some function that says...

      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.

      Updated on 2013-04-30T19:44:29Z at 2013-04-30T19:44:29Z by CedricVB
      • Petr Vilím
        Petr Vilím
        14 Posts
        ACCEPTED ANSWER

        Re: Truck load in VRP

        ‏2013-05-01T19:32:45Z  in response to CedricVB

        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

  • CedricVB
    CedricVB
    4 Posts
    ACCEPTED ANSWER

    Re: Truck load in VRP

    ‏2013-05-07T17:07:02Z  in response to 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!

    Updated on 2013-05-07T17:09:31Z at 2013-05-07T17:09:31Z by CedricVB