Vehicle routing Problem

orangejuss — Mon, 04 Dec 2017 06:50:00 GMT

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;

Re: Vehicle routing Problem

RobPratt — Mon, 04 Dec 2017 17:03:22 GMT

Node 1 plays the role of your dummy node. You just need to modify the distances, as shown in this doc example and pages 8-9 of this SAS Global Forum 2014 paper.

topic Re: Vehicle routing Problem in Mathematical Optimization, Discrete-Event Simulation, and OR

Vehicle routing Problem

Re: Vehicle routing Problem