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

Tuesday

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

Friday

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

Posted in reply to simen1994

Wednesday - last edited Friday

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

Friday

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

Posted in reply to simen1994

Wednesday - last edited Friday

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

Friday

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

Friday - last edited Friday

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.