Originally posted by: ShivaliLomate

Hi,

I am doing constraint programming for vehicle routing problem. Vehicle volume is my int+ decision variable which stores values of inventory at each interval after unloading as well as loading the vehicle. unloading is possible at customer location and loading is possible at depot location only.  Movement of vehicle possible from a) depot to customer b) customer to customer c) customer to depot and trip consist of any one or all of there combination of movement .There are three possible scenario which are explained below:

1. when  trip start from depot location then vehicle volume is nothing but heightatend of loading - unloading, actual constraint formed is as shown in CT_1.

2. When trip not going to start form depot initially then it should take vehicle opening inventory as initial capacity, this is formulated in CT_3. but this contraint is valid when trip in first in sequence for that vehicle, for this i used typeOfPrev construct to ensure that trip should be first on that vehicle.

3. Third case is for inventory tracking  all further trips  which are in sequence on that particular vehicle( invalid for fisrt trip on vehicle and also invalid for trip which is strating form depots). This shown in constraint CT_2.

 

But there is problem is this constraints are not working properly. specially there is problem in constraint CT_3. with use of typeOfPrev construct i think we are not getting first trip on that vehicle. Can you see constraints as formulated below and try to figured out where we are going wrong ??? or is there any additional constraints need to model.

 

Decision variable:-

dvar int+ vehicleVolume[t in Trips] in 0..ftoi(t.Vehicle.Capacity);

dvar interval unloading[t in Trips] optional size 1;

dvar interval loading[t in Trips] optional size 1;

dvar interval trip[t in Trips] optional in 0..H size 0..H ;

dvar sequence vehicle[v in Vehicles] in all(t in Trips: v.Id == t.Vehicle.Id)trip[t] types all (t1 in Trips: t1.Vehicle.Id == v.Id) t1.Route.Id;

 

cumulFunction UnloadingVolume[t in Trips] = stepAtStart(unloading[t],0,ftoi(t.Vehicle.Capacity));

cumulFunction LoadingVolume[t in Trips] = stepAtStart(loading[t],ftoi(t.Vehicle.Capacity));

constraint:-

forall(t in Trips, d in Depots: t.Route.Location1 == d.Location.Id)

CT_1 vehicleVolume[t] == heightAtEnd(loading[t],LoadingVolume[t]) - heightAtEnd(unloading[t],UnloadingVolume[t]);

 

forall(t in Trips, d in Depots: t.Route.Location1 != d.Location.Id){
 

 CT_2 vehicleVolume[t] == sum(t1 in Trips:t.Vehicle.Id == t1.Vehicle.Id)((typeOfPrev(vehicle[t1.Vehicle],trip[t1],0)== t.Route.Id) * vehicleVolume[t1])-
                                       heightAtEnd(unloading[t],UnloadingVolume[t]);

 

   CT_3: vehicleVolume[t] == ((typeOfPrev(vehicle[t.Vehicle],trip[t],1)== 1) * (t.Vehicle.OpeningInventory) - heightAtEnd(unloading[t],UnloadingVolume[t]));
                                       

}   

 

    // no overlap constrainted  
    forall(v in Vehicles)
        CT_0: noOverlap(vehicle[v]);

 

 

#CPOptimizer
#DecisionOptimization

Originally posted by: PhilippeLaborie

Hello,

Why do you mean by "this constraints are not working properly" ?
- Does it produce a solution that is not a real solution to your actual problem? In this case, looking at the constraint and at the "solution" of the model, can you identify if this "solution" respects the semantics of the constraint? If yes, can you identify what is missing in the constraint?
- Does it claim (prove) that the model is infeasible?
- Or is it just that the engine cannot find a feasible solution in reasonable time?

In the current version of your model, I do not see why you are using cumul functions as there is no global cumul function for each vehicle that would represent the vehicle level over time. It seems to me that you are mixing two different approaches for modeling the problem:

1- a cumul function approach where you have your interval variables loading/unloading increasing/decreasing a cumul function for the truck representing its level over time. Here that would be something like:

cumulFunction vehicleVolume = sum(t in Trips) stepAtStart(loading[t],ftoi(t.Vehicle.Capacity)) - sum(t in Trips) stepAtEnd(unloading[t],ftoi(t.Vehicle.Capacity));

and then a constraint like:

vehicleVolume <= t.Vehicle.Capacity

2- a model where you do not use cumul function at all but only integer variables (like your dvar int+ vehicleVolume[t in Trips]) and a set of constraints to relate the volume at a given activity with the volume at the previous activity, thanks to typeOfPrev constraints.

Another thing I do not get in your model is the notion of "trip". The trips index both the load, unload and trip activities. So does a trip concerns only a single customer visit and is made of a chain of load->trip->unload (I do not see those precedences in the model)? Do you know in advance the set of trips? Also, each trip seems to have a dedicated vehicle t.Vehicle.Id so the scheduling of the different vehicles seem to be independent problems ...

 

#CPOptimizer
#DecisionOptimization