SAS Optimization, and SAS Simulation Studio

turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Find a Community

Topic Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

Highlighted
# How can I add time windows to a VRP model?

Options

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

04-17-2018 06:08 AM

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to simen1994

04-18-2018 11:46 AM - edited 04-20-2018 10:04 AM

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

All Replies

Solution

04-20-2018
03:49 AM

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to simen1994

04-18-2018 11:46 AM - edited 04-20-2018 10:04 AM

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

04-20-2018 03:52 AM

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;

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to simen1994

04-20-2018 10:02 AM - edited 04-20-2018 10:05 AM

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.

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

04-23-2018 02:41 AM

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;

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to simen1994

04-23-2018 12:50 PM

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.

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to RobPratt

04-24-2018 01:35 PM

It worked Thanks Rob!