Sorry that the documentation example misled you. The approach shown is not the state-of-the-art way to solve a CVRP problem but was intended to demonstrate the usefulness of decomp versus the default branch-and-cut algorithm for a problem that is simple to state and an instance that decomp quickly solves to optimality. Here are a couple of other ideas to speed up the solve, and these apply more generally to other MILP problems.
The following code implements a simple greedy heuristic to obtain a feasible solution:
/* declare parameters for greedy heuristic */
set <num,num> PATH init {};
num totalDemand = sum {<i,j> in PATH} demand[j];
num currentNode init depot;
set VISITED init {currentNode};
set CANDIDATES = {j in NODES diff VISITED: totalDemand + demand[j] <= &capacity};
num costToCandidate {j in CANDIDATES} = cost[currentNode,j] / demand[j];
num minCost, nextNode;
num currentDemand;
/* greedy heuristic */
for {k in VEHICLES} do;
PATH = {};
currentNode = depot;
do until (card(CANDIDATES) = 0);
minCost = constant('BIG');
for {j in CANDIDATES} do;
if minCost > costToCandidate[j] then do;
minCost = costToCandidate[j];
nextNode = j;
end;
end;
VISITED = VISITED union {nextNode};
PATH = PATH union {<currentNode,nextNode>};
UseNode[nextNode,k] = 1;
UseArc[currentNode,nextNode,k] = 1;
currentNode = nextNode;
end;
PATH = PATH union {<currentNode,depot>};
UseNode[depot,k] = 1;
UseArc[currentNode,depot,k] = 1;
currentDemand = totalDemand;
for {<i,j> in PATH} do;
Flow[i,j,k] = currentDemand;
currentDemand = currentDemand - demand[j];
end;
end;
To run this, insert it before the SOLVE statement, and use the PRIMALIN option to warm start the MILP solver with the solution obtained by the heuristic:
solve with MILP / decomp varsel=ryanfoster primalin;
This greedy approach is a construction heuristic in that it constructs a feasible solution from scratch. You can also implement an improvement heuristic that uses the MILP solver itself to improve a given feasible solution. The following code considers each pair of vehicles and tries to improve the solution for that pair, leaving all other UseNode variables fixed to their current values:
/* improvement heuristic */
reset option printlevel=0;
fix UseNode;
for {k1 in VEHICLES, k2 in VEHICLES: k1 < k2} do;
put k1= k2=;
for {k in {k1,k2}, i in NODES diff {depot}} unfix UseNode[i,k];
solve with MILP / primalin;
for {k in {k1,k2}, i in NODES diff {depot}} fix UseNode[i,k];
end;
for {k in VEHICLES, i in NODES diff {depot}} unfix UseNode[i,k];
reset option printlevel;
For the 55-city instance, the greedy heuristic returns a solution with objective value 876, and the improvement heuristic improves it to 627 in just a few minutes. Because the optimal value is 588, this solution is within 6.6% of optimal.
Besides these two heuristics, you can use PROC OPTMODEL programming statements to write your own heuristic or read in a solution obtained by any other method, such as the one obtained by @josgri via PROC GA. Using the PRIMALIN option to provide a starting solution is often a good way to speed up the MILP solver.
... View more
