Turn on suggestions

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

Showing results for

Options

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

🔒 This topic is **solved** and **locked**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 04-17-2018 06:08 AM
(1046 views)

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

6 REPLIES 6

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

It worked 🙂 Thanks Rob!

Registration is open! SAS is returning to Vegas for an AI and analytics experience like no other! Whether you're an executive, manager, end user or SAS partner, SAS Innovate is designed for everyone on your team. Register for just $495 by 12/31/2023.

**If you are interested in speaking, there is still time to submit a session idea. More details are posted on the website. **

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.