Operations Research topics: SAS/OR,
SAS Optimization, and SAS Simulation Studio

How can I add time windows to a VRP model?

Accepted Solution Solved
Reply
Highlighted
Occasional Contributor
Posts: 5
Accepted Solution

How can I add time windows to a VRP model?

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


Accepted Solutions
Solution
‎04-20-2018 03:49 AM
SAS Employee
Posts: 586

Re: How can I add time windows to a VRP model?

[ Edited ]
Posted in reply to simen1994

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

View solution in original post


All Replies
Solution
‎04-20-2018 03:49 AM
SAS Employee
Posts: 586

Re: How can I add time windows to a VRP model?

[ Edited ]
Posted in reply to simen1994

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]); 
Occasional Contributor
Posts: 5

Re: How can I add time windows to a VRP model?

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;

SAS Employee
Posts: 586

Re: How can I add time windows to a VRP model?

[ Edited ]
Posted in reply to simen1994

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.

Occasional Contributor
Posts: 5

Re: How can I add time windows to a VRP model?

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;

 

 

SAS Employee
Posts: 586

Re: How can I add time windows to a VRP model?

Posted in reply to simen1994

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.

Occasional Contributor
Posts: 5

Re: How can I add time windows to a VRP model?

It worked Smiley Happy Thanks Rob!

☑ This topic is solved.

Need further help from the community? Please ask a new question.

Discussion stats
  • 6 replies
  • 298 views
  • 0 likes
  • 2 in conversation