BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
simen1994
Calcite | Level 5

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

1 ACCEPTED SOLUTION

Accepted Solutions
RobPratt
SAS Super FREQ

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

6 REPLIES 6
RobPratt
SAS Super FREQ

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
Calcite | Level 5

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
SAS Super FREQ

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
Calcite | Level 5

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
SAS Super FREQ

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
Calcite | Level 5

It worked 🙂 Thanks Rob!

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.

Discussion stats
  • 6 replies
  • 1200 views
  • 1 like
  • 2 in conversation