Rewrite the example to sequentially generate first solutions using the following predefined first solution heuristics: IloSavingsGenerate, IloSweepGenerate, IloNearestDepotGenerate, IloNearestAdditionGenerate, and IloInsertionGenerate. Analyze the output to see how the different first solution heuristics change the first solution and its cost.
Suggested Answer
To sequentially generate first solutions using different heuristics, create a function IloRoutingSolver::sequentialGenerate. This function is called in the main function using solver.sequentialGenerate():
void RoutingSolver::sequentialGenerate() {
generate(IloSavingsGenerate(_env) && _instantiateCost,
(char *)"Savings");
generate(IloSweepGenerate(_env) && _instantiateCost,
(char *)"Sweep");
generate(IloNearestDepotGenerate(_env) && _instantiateCost,
(char *)"Nearest to Depot");
generate(IloNearestAdditionGenerate(_env) && _instantiateCost,
(char *)"Nearest addition");
generate(IloInsertionGenerate(_env, _instantiateCost),
(char *)"Insertion");
}
|
Different first solution heuristics will work differently depending on the particulars of your problem. In this example, using the sweep heuristic found the lowest cost solution, 270.403 units. The savings heuristic found the next lowest cost solution, 280.947 units, followed by nearest-addition, insertion, and nearest-to-depot. The solution found using the nearest-to-depot heuristic had a cost of 369.297 units. From this example, you can see that trying different first solution heuristics can greatly change the cost of your final solution. For more information on choosing the right first solution heuristic for you problem, see "Using the predefined first solution heuristics".
You can view this complete program and output online in the YourDispatcherHome/examples/src/generate.cpp file.
The following output is generated for the savings heuristic:
Savings
Number of fails : 38
Number of choice points : 1052
Number of variables : 390
Number of constraints : 98
Reversible stack (bytes) : 60324
Solver heap (bytes) : 337960
Solver global heap (bytes) : 42744
And stack (bytes) : 20124
Or stack (bytes) : 44244
Search Stack (bytes) : 4044
Constraint queue (bytes) : 11160
Total memory used (bytes) : 520600
Elapsed time since creation : 0.047
Number of nodes : 12
Number of visits : 21
Number of vehicles : 5
Number of dimensions : 2
Number of accepted moves : 0
===============
Cost : 280.947
Number of vehicles used : 4
Solution :
Unperformed visits : None
truck1 :
-> depot weight[0..6] distance[0..Inf) -> visit5 weight[0..6]
distance[14.1421..Inf) -> visit10 weight[21..27] distance[28.3548..Inf) ->
visit9 weight[26..32] distance[40.3964..Inf) -> visit1 weight[37..43]
distance[64.6038..Inf) -> depot weight[44..50] distance[78.4963..Inf)
truck2 :
-> depot weight[0..4] distance[0..Inf) -> visit3 weight[0..4]
distance[32.5576..Inf) -> visit2 weight[16..20] distance[47.8547..Inf) -> depot
weight[46..50] distance[68.8785..Inf)
truck3 :
-> depot weight[0..8] distance[0..Inf) -> visit8 weight[0..8]
distance[22.0227..Inf) -> visit7 weight[23..31] distance[36.0584..Inf) -> depot
weight[42..50] distance[62.4781..Inf)
truck4 :
-> depot weight[0..7] distance[0..Inf) -> visit6 weight[0..7]
distance[11.4018..Inf) -> visit4 weight[15..22] distance[32.4256..Inf) ->
visit11 weight[24..31] distance[59.0526..Inf) -> depot weight[43..50]
distance[71.0942..Inf)
truck5 : Unused
|
The following output is generated for the sweep heuristic:
Sweep
Number of fails : 14
Number of choice points : 1056
Number of variables : 390
Number of constraints : 93
Reversible stack (bytes) : 60324
Solver heap (bytes) : 337960
Solver global heap (bytes) : 42744
And stack (bytes) : 20124
Or stack (bytes) : 44244
Search Stack (bytes) : 4044
Constraint queue (bytes) : 11160
Total memory used (bytes) : 520600
Elapsed time since creation : 0
Number of nodes : 12
Number of visits : 21
Number of vehicles : 5
Number of dimensions : 2
Number of accepted moves : 0
===============
Cost : 270.403
Number of vehicles used : 4
Solution :
Unperformed visits : None
truck1 :
-> depot weight[0..4] distance[0..Inf) -> visit4 weight[0..4]
distance[17.2047..Inf) -> visit5 weight[9..13] distance[37.6007..Inf) ->
visit10 weight[30..34] distance[51.8134..Inf) -> visit9 weight[35..39]
distance[63.855..Inf) -> depot weight[46..50] distance[86.9418..Inf)
truck2 :
-> depot weight[0..1] distance[0..Inf) -> visit11 weight[0..1]
distance[12.0416..Inf) -> visit2 weight[19..20] distance[22.6717..Inf) -> depot
weight[49..50] distance[43.6955..Inf)
truck3 :
-> depot weight[0..4] distance[0..Inf) -> visit3 weight[0..4]
distance[32.5576..Inf) -> visit1 weight[16..20] distance[51.767..Inf) -> visit8
weight[23..27] distance[63.4289..Inf) -> depot weight[46..50]
distance[85.4516..Inf)
truck4 :
-> depot weight[0..16] distance[0..Inf) -> visit7 weight[0..16]
distance[26.4197..Inf) -> visit6 weight[19..35] distance[42.9121..Inf) -> depot
weight[34..50] distance[54.3139..Inf)
truck5 : Unused
|
The following output is generated for the nearest-to-depot heuristic:
Nearest to Depot
Number of fails : 13
Number of choice points : 1055
Number of variables : 390
Number of constraints : 93
Reversible stack (bytes) : 60324
Solver heap (bytes) : 337960
Solver global heap (bytes) : 42744
And stack (bytes) : 20124
Or stack (bytes) : 44244
Search Stack (bytes) : 4044
Constraint queue (bytes) : 11160
Total memory used (bytes) : 520600
Elapsed time since creation : 0
Number of nodes : 12
Number of visits : 21
Number of vehicles : 5
Number of dimensions : 2
Number of accepted moves : 0
===============
Cost : 369.297
Number of vehicles used : 4
Solution :
Unperformed visits : None
truck1 :
-> depot weight[0] distance[0..Inf) -> visit6 weight[0] distance[11.4018..Inf)
-> visit11 weight[15] distance[33.2421..Inf) -> visit1 weight[34]
distance[45.3251..Inf) -> visit4 weight[41] distance[76.3896..Inf) -> depot
weight[50] distance[93.5942..Inf)
truck2 :
-> depot weight[0..1] distance[0..Inf) -> visit5 weight[0..1]
distance[14.1421..Inf) -> visit8 weight[21..22] distance[47.3837..Inf) ->
visit10 weight[44..45] distance[93.0017..Inf) -> depot weight[49..50]
distance[121.321..Inf)
truck3 :
-> depot weight[0..9] distance[0..Inf) -> visit2 weight[0..9]
distance[21.0238..Inf) -> visit9 weight[30..39] distance[37.3026..Inf) -> depot
weight[41..50] distance[60.3894..Inf)
truck4 :
-> depot weight[0..15] distance[0..Inf) -> visit7 weight[0..15]
distance[26.4197..Inf) -> visit3 weight[19..34] distance[61.434..Inf) -> depot
weight[35..50] distance[93.9916..Inf)
truck5 : Unused
|
The following output is generated for the nearest-addition heuristic:
Nearest addition
Number of fails : 21
Number of choice points : 1052
Number of variables : 390
Number of constraints : 98
Reversible stack (bytes) : 60324
Solver heap (bytes) : 341980
Solver global heap (bytes) : 42744
And stack (bytes) : 20124
Or stack (bytes) : 44244
Search Stack (bytes) : 4044
Constraint queue (bytes) : 11160
Total memory used (bytes) : 524620
Elapsed time since creation : 0.015
Number of nodes : 12
Number of visits : 21
Number of vehicles : 5
Number of dimensions : 2
Number of accepted moves : 0
===============
Cost : 285.232
Number of vehicles used : 4
Solution :
Unperformed visits : None
truck1 :
-> depot weight[0] distance[0..Inf) -> visit6 weight[0] distance[11.4018..Inf)
-> visit7 weight[15] distance[27.8942..Inf) -> visit1 weight[34]
distance[50.7196..Inf) -> visit4 weight[41] distance[81.7841..Inf) -> depot
weight[50] distance[98.9887..Inf)
truck2 :
-> depot weight[0..1] distance[0..Inf) -> visit11 weight[0..1]
distance[12.0416..Inf) -> visit2 weight[19..20] distance[22.6717..Inf) -> depot
weight[49..50] distance[43.6955..Inf)
truck3 :
-> depot weight[0..13] distance[0..Inf) -> visit5 weight[0..13]
distance[14.1421..Inf) -> visit9 weight[21..34] distance[26.5115..Inf) ->
visit10 weight[32..45] distance[38.553..Inf) -> depot weight[37..50]
distance[66.8727..Inf)
truck4 :
-> depot weight[0..11] distance[0..Inf) -> visit8 weight[0..11]
distance[22.0227..Inf) -> visit3 weight[23..34] distance[43.1177..Inf) -> depot
weight[39..50] distance[75.6754..Inf)
truck5 : Unused
|
The following output is generated for the insertion heuristic:
Insertion
Number of fails : 11
Number of choice points : 13680
Number of variables : 390
Number of constraints : 93
Reversible stack (bytes) : 60324
Solver heap (bytes) : 341980
Solver global heap (bytes) : 473476
And stack (bytes) : 20124
Or stack (bytes) : 44244
Search Stack (bytes) : 4044
Constraint queue (bytes) : 11160
Total memory used (bytes) : 955352
Elapsed time since creation : 0.078
Number of nodes : 12
Number of visits : 21
Number of vehicles : 5
Number of dimensions : 2
Number of accepted moves : 0
===============
Cost : 320.843
Number of vehicles used : 4
Solution :
Unperformed visits : None
truck1 :
-> depot weight[0..4] distance[0..Inf) -> visit4 weight[0..4]
distance[17.2047..Inf) -> visit2 weight[9..13] distance[54.2182..Inf) -> visit1
weight[39..43] distance[66.5875..Inf) -> depot weight[46..50]
distance[80.4799..Inf)
truck2 :
-> depot weight[0..2] distance[0..Inf) -> visit5 weight[0..2]
distance[14.1421..Inf) -> visit9 weight[21..23] distance[26.5115..Inf) ->
visit3 weight[32..34] distance[57.5115..Inf) -> depot weight[48..50]
distance[90.0691..Inf)
truck3 :
-> depot weight[0..16] distance[0..Inf) -> visit7 weight[0..16]
distance[26.4197..Inf) -> visit6 weight[19..35] distance[42.9121..Inf) -> depot
weight[34..50] distance[54.3139..Inf)
truck4 :
-> depot weight[0..3] distance[0..Inf) -> visit10 weight[0..3]
distance[28.3196..Inf) -> visit11 weight[5..8] distance[50.2513..Inf) -> visit8
weight[24..27] distance[73.9579..Inf) -> depot weight[47..50]
distance[95.9806..Inf)
truck5 : Unused
|
PREVIOUS
NEXT