How can I add time windows to a VRP model?

[simen1994]

Hello! I am working on a School assignment. I am using SAS Studio to build up a VRP model.

The model is a typical VRP problem with split deliveries, a set of nodes, two trucks, truck capacity and time Windows.

How do I define the time windows? There has to be a lower time window and a upper time window.

Example: A customer has a time window between 08:00 and 08:30. The customers demand has to be fulfilled between 08:00 and 08:30 by 1 or 2 trucks (split deliveries).

[RobPratt · Accepted solution]

You can enforce time windows by introducing a Start variable and big-M constraints:

var UseArc {ARCS, VEHICLES} binary;
var Start {i in NODES, k in VEHICLES} >= r[i] <= d[i];
/* if UseArc[i,j,k] = 1 then Start[i,k] + c[i,j,k] <= Start[j,k] */
con StartCon {i in NODES, j in NODES diff {depot}, k in VEHICLES: i ne j}:
   Start[i,k] + c[i,j,k] - Start[j,k] 
<= (Start[i,k].ub + c[i,j,k] - Start[j,k].lb) * (1 - UseArc[i,j,k]); 

[simen1994]

This is my model now. I'm afraid I didnt understand your solution, because im very new to this. Could you ad the time constraint to this?

proc optmodel;
/*DATA*/
set trucks  = {1,2};
set customers = {0,1,2,3};
number distance{customers, customers}=[
0 2 4 5
2 0 0.8 1.5
4 0.8 0 0.6
5 1.5 0.6 0
];

number demand{customers} =[0 10 5 10];

number truckCapacity{trucks} = [20 20];

/*VARIABLES*/

var X{customers,customers,trucks} binary;

var Y{trucks, customers} binary;

var Q{trucks,customers};

/*Objective function*/

minimize C = sum{i in customers, j in customers, k in trucks} distance[i,j]*X[i,j,k];

/*CONSTRAINTS*/

/*Each truck must start from depot*/

con startDepot{k in trucks} : sum{j in customers : j>0} X[0,j,k] = 1;

/*Each truck must return to depot*/

con endDepot{k in trucks} : sum{i in customers : i>0} X[i,0,k] = 1;

/*Flow conservation - what comes in - must come out*/

con flowConst{i in customers, k in trucks}:
 sum{j in customers : j ne i}
  (X[j,i,k] - X[i,j,k]) =0;

/*Demand must be fulfilled*/

con demandFulfill{i in customers: i>0}:
 sum{k in trucks}Q[k,i] = demand[i];

/*Logical constraint: X -> Y*/

con xyConst{j in customers , k in trucks: j>0}:
 sum{i in customers : i ne j} X[i,j,k] = Y[k,j];

/*Logical constraint: Q -> Y*/

con qyConst{i in customers , k in trucks: i>0}:
 Q[k,i] <= demand[i]*Y[k,i];

/*Truck capacity in m^3*/

con truckCapacityConst{k in trucks}:
 sum{i in customers : i>0}Q[k,i] <= truckCapacity[k];

solve with milp / maxtime=600;

print X Y Q C;

quit;

[RobPratt]

The correspondence is VEHICLES<->trucks, NODES<->customers, and ARCS<->customers cross customers.

Where is your time window data?  You also will need travel time data between customers, like you already have travel distances between customers.

[simen1994]

I think I understand now. I have added now the travel time between the nodes and a new variable which is arrivaltime B{i,j}.

Before I add the time constraints I Guess there should be a constraint which tells the value of the arrival time.

I have written it like this:   X[i,j,k]*runtime[i,j] = B[i];                    =>        Desicion variables * runetime between the nodes = arrival time.

After this I would constrain the arrival time to a upper and a lower time window.

Is this the correct way to do it?

If this is correct, what should come before: X[i,j,k]*runtime[i,j] = B[i];? It should be sum of all trucks.

proc optmodel;
/*DATA*/
set trucks  = {1,2};
set customers = {0,1,2,3};
number distance{customers, customers}=[
0 2 4 5
2 0 0.8 1.5
4 0.8 0 0.6
5 1.5 0.6 0
];

number demand{customers} =[0 10 5 10];

number truckCapacity{trucks} = [20 20];

/*NEW DATA*/

/*Time windows

Customer 0 (depot) => 07:00-07:00
Customer 1   => 07:00-07:30
Customer 2   => 07:00-07:50
Customer 3    => 08:00-08:30
*/

number lowertimeWindows{customers}=[0 0 0 60];
number uppertimeWindows{customers}=[0 30 50 90];

number runtime{customers, customers}=[
0 10 20 25
10 0 15 22
20 15 0 18
25 22 18 0];

/*VARIABLER*/

var X{customers,customers,trucks} binary;

var Y{trucks, customers} binary;

var Q{trucks,customers};

/*NEW VARIABLE*/
var B{customers}; /*The number of minutes it takes for the trucks to meet the demand*/

/*Objective function*/

minimize C = sum{i in customers, j in customers, k in trucks} distance[i,j]*X[i,j,k];

/*CONSTRAINTS*/

/*Each truck must start from depot*/

con startDepot{k in trucks} : sum{j in customers : j>0} X[0,j,k] = 1;

/*Each truck must return to depot*/

con endDepot{k in trucks} : sum{i in customers : i>0} X[i,0,k] = 1;

/*Flow conservation - what comes in - must come out*/

con flowConst{i in customers, k in trucks}:
 sum{j in customers : j ne i}
  (X[j,i,k] - X[i,j,k]) =0;

/*Demand must be fulfilled*/

con demandFulfill{i in customers: i>0}:
 sum{k in trucks}Q[k,i] = demand[i];

/*Logical constraint: X -> Y*/

con xyConst{j in customers , k in trucks: j>0}:
 sum{i in customers : i ne j} X[i,j,k] = Y[k,j];

/*Logical constraint: Q -> Y*/

con qyConst{i in customers , k in trucks: i>0}:
 Q[k,i] <= demand[i]*Y[k,i];

/*Truck capacity in m^3*/

con truckCapacityConst{k in trucks}:
 sum{i in customers : i>0}Q[k,i] <= truckCapacity[k];
 
/*NEW CONSTRAINTS*/

con sum{} X[i,j,k]*runtime[i,j] = B[i];

solve with milp / maxtime=600;

print X Y Q C B;

quit;

[RobPratt]

Try this:

var Start {i in customers, k in trucks} >= lowertimeWindows[i] <= uppertimeWindows[i];
/* if X[i,j,k] = 1 then Start[i,k] + runtime[i,j] <= Start[j,k] */
con StartCon {i in customers, j in customers diff {0}, k in trucks: i ne j}:
   Start[i,k] + runtime[i,j] - Start[j,k] 
<= (Start[i,k].ub + runtime[i,j] - Start[j,k].lb) * (1 - X[i,j,k]); 

The value of Start[i,k] matters only when customer i is served by truck k, that is, when Y[k,i] = 1.

[simen1994]

It worked 🙂 Thanks Rob!