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
# Vehicle routing Problem

Options

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

12-04-2017 01:50 AM

Hi,

I am trying to write a vehicle routing problem as follows.

Is there anyway to declare a dummy node that has 0 values of time,demand and 0 distance to every node.And every vehicle must start and end on this dummy node?

Thanks.

/* number of vehicles available */

%let num_vehicles = 8;

/* capacity of each vehicle */

%let capacity = 3000;

/* node, x coordinate, y coordinate, demand time */

data vrpdata;

input node x y demand time;

datalines;

1 145 215 0 30

2 151 264 1100 25

3 159 261 700 15

4 130 254 800 35

5 128 252 1400 10

6 163 247 2100 10

7 146 246 400 20

8 161 242 800 25

9 142 239 100 10

10 163 236 500 10

11 148 232 600 35

12 128 231 1200 5

13 156 217 1300 10

14 129 214 1300 15

15 146 208 300 15

16 164 208 900 10

17 141 206 2100 35

18 147 193 1000 25

19 164 193 900 20

20 129 189 2500 10

21 155 185 1800 10

22 139 182 700 20

;

proc optmodel;

/* read the node location and demand data */

set NODES;

num x {NODES};

num y {NODES};

num demand {NODES};

num capacity = &capacity;

num num_vehicles = &num_vehicles;

read data vrpdata into NODES=[node] x y demand ;

set ARCS = {i in NODES, j in NODES: i ne j};

set VEHICLES = 1..num_vehicles;

/* define the depot as node 1 */

num depot = 1;

/* define the arc cost as the rounded Euclidean distance */

num cost {<i,j> in ARCS} = round(sqrt((x[i]-x[j])^2 + (y[i]-y[j])^2));

/* Flow[i,j,k] is the amount of demand carried on arc (i,j) by vehicle k */

var Flow {ARCS, VEHICLES} >= 0 <= capacity;

/* UseNode[i,k] = 1, if and only if node i is serviced by vehicle k */

var UseNode {NODES, VEHICLES} binary;

/* UseArc[i,j,k] = 1, if and only if arc (i,j) is traversed by vehicle k */

var UseArc {ARCS, VEHICLES} binary;

/* minimize the total distance traversed */

min TotalCost = sum {<i,j> in ARCS, k in VEHICLES} cost[i,j] * UseArc[i,j,k];

/* each non-depot node must be serviced by at least one vehicle */

con Assignment {i in NODES diff {depot}}:

sum {k in VEHICLES} UseNode[i,k] >= 1;

/* each vehicle must start at the depot node */

for{k in VEHICLES} fix UseNode[depot,k] = 1;

/* some vehicle k traverses an arc that leaves node i

if and only if UseNode[i,k] = 1 */

con LeaveNode {i in NODES, k in VEHICLES}:

sum {<(i),j> in ARCS} UseArc[i,j,k] = UseNode[i,k];

/* some vehicle k traverses an arc that enters node i

if and only if UseNode[i,k] = 1 */

con EnterNode {i in NODES, k in VEHICLES}:

sum {<j,(i)> in ARCS} UseArc[j,i,k] = UseNode[i,k];

/* the amount of demand supplied by vehicle k to node i must equal demand

if UseNode[i,k] = 1; otherwise, it must equal 0 */

con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:

sum {<j,(i)> in ARCS} Flow[j,i,k] - sum {<(i),j> in ARCS} Flow[i,j,k]

= demand[i] * UseNode[i,k];

/* if UseArc[i,j,k] = 1, then the flow on arc (i,j) must be at most capacity

if UseArc[i,j,k] = 0, then no flow is allowed on arc (i,j) */

con VehicleCapacity {<i,j> in ARCS, k in VEHICLES}:

Flow[i,j,k] <= Flow[i,j,k].ub * UseArc[i,j,k];

/* decomp by vehicle */

for {i in NODES, k in VEHICLES} do;

LeaveNode[i,k].block = k;

EnterNode[i,k].block = k;

end;

for {i in NODES diff {depot}, k in VEHICLES} FlowBalance[i,k].block = k;

for {<i,j> in ARCS, k in VEHICLES} VehicleCapacity[i,j,k].block = k;

/* solve using decomp (aggregate formulation) */

solve with MILP / varsel=ryanfoster decomp=(logfreq=20);

The following OPTMODEL statements create node and edge data for the optimal routing:

/* create solution data set */

str color {k in VEHICLES} =

['red' 'green' 'blue' 'black' 'orange' 'gray' 'maroon' 'purple'];

create data node_data from [i] x y;

create data edge_data from [i j k]=

{<i,j> in ARCS, k in VEHICLES: UseArc[i,j,k].sol > 0.5}

x1=x[i] y1=y[i] x2=x[j] y2=y[j] linecolor=color[k];

quit;

/* create solution data set */

str color {k in VEHICLES} =

['red' 'green' 'blue' 'black' 'orange' 'gray' 'maroon' 'purple'];

create data node_data from [i] x y;

create data edge_data from [i j k]=

{<i,j> in ARCS, k in VEHICLES: UseArc[i,j,k].sol > 0.5}

x1=x[i] y1=y[i] x2=x[j] y2=y[j] linecolor=color[k];

quit;

Accepted Solutions

Solution

12-13-2017
12:59 AM

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

Posted in reply to orangejuss

12-04-2017 12:03 PM

All Replies

Solution

12-13-2017
12:59 AM

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

Posted in reply to orangejuss

12-04-2017 12:03 PM