Hi all :
When solving CVRPs, for learning/teaching purposes I wanted to quantify the performance gain of the decomposition algo: however I found no way to turn it off. Is there a way ?
And : Just to get a rough idea where a Genetic Algorithm would get to I used <solve with LSO> : this resulted in an early stop with < WARNING: The best solution found does not satisfy the feasibility tolerance. NOTE: Failed. >
Any ideas how to get some methodological comparison data (timings) - preferably within SAS/OR ?
I experimented with several instances of VRP-Lib, a particular instance with rather optimal .block settings and good performance is from SAS documentation (OR - 15.1) ::
/* vrpdata represents an instance from VRPLIB that has 22 nodes and eight vehicles (P-n22-k8.vrp), which was originally described in Augerat et al. (1995). The data set lists each node, its coordinates, and its demand. */
/* number of vehicles available */ %let num_vehicles = 8; /* capacity of each vehicle */ %let capacity = 3000; /* node, x coordinate, y coordinate, demand */ data vrpdata; input node x y demand; datalines; 1 145 215 0 2 151 264 1100 3 159 261 700 4 130 254 800 5 128 252 1400 6 163 247 2100 7 146 246 400 8 161 242 800 9 142 239 100 10 163 236 500 11 148 232 600 12 128 231 1200 13 156 217 1300 14 129 214 1300 15 146 208 300 16 164 208 900 17 141 206 2100 18 147 193 1000 19 164 193 900 20 129 189 2500 21 155 185 1800 22 139 182 700 ;
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);
/* create solution data set */ create data solution_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] function='line' drawspace='datavalue'; quit;
proc sgplot data=solution_data noautolegend; scatter x=x1 y=y1 / datalabel=i; vector x=x2 y=y2 / xorigin=x1 yorigin=y1 group=k noarrowheads; xaxis display=none; yaxis display=none; run;
Any tips are welcome.
Odenwald
... View more