

Vehicle
Routing 


Strategy 

The heuristics on the last page
are applied in cycles. All three heuristics consider node pairs
where the application of the heuristic changes
the sequence in some manner related to the pair.
There are restrictions on changes that assure that
the truck nodes remain in the same order as in the initial
solution. Given the initial base sequence, we select
the first node and then
evaluate
the objective function for every choice of the second node.
If one or more of the pairs result in improvement of the
objective value, the best pair is applied to the base
sequence to form a new base sequence. The process continues
until all nodes are considered as the first node. This is called
a cycle.
Since only
improving pairs
are accepted for implementation, the objective value for the
base sequence always declines. If there is no improvement for
a cycle, the process stops because no further improvement is
possible using the current heuristic. The process then terminates
or continues with a different heuristic.
A strategy involves selecting the order of applying the heuristics
and determining how many cycles to run. A deterministic heuristic
carried to the point where a complete cycle shows no improvement
leads
to a local minimum. To investigate alternative local optima,
we use two different methods for selecting starting solutions
randomly.
The example for this page has 20 deliveries with four identical
trucks. Time is not part of the model, so the goal is to
minimize total route length. Four trucks are used in the example
and each truck is required to make five deliveries. The data
is on the Routing_20.xls demonstration
file. 
Strategy Components 

A strategy consists of a combination of heuristics.
The candidate components for a strategy are listed in the table
below. The process always begins with the solution on the result
worksheet. Strategies are evaluated in the Sequence Optimizing addin
that manipulates solutions on the model worksheet. After the
completion of the optimization process, the solution is transferred
from the model worksheet
to the results worksheet. The initial solution must define
a valid sequence.
It is possible to set the initial solution manually on
the results worksheet.
The default values for the number of cycles are in the last
column. NS is the number nodes sequenced (2*trucks + deliveries).
The search process may use a specified number of cycles or
allow as many cycles as necessary to reach a local optimum
for each heuristic. For a local optimum for the process, the
search process uses as many cycles as necessary until a cycle
results in no improvement for every heuristic.
Component 
Definition 
Default Value 
Original 
The sequence defined when the search process
is initiated 
1 
Random 
The set number of randomly generated initial solutions 
1 
Greedy 
The set number of greedy solutions with the initial solution randomly
generated 
1 
Insert 
The number of cycles of the Insert heuristic 
3 + Int(NS / 10) 
Switch 
The number of cycles of the Switch heuristic 
3 + Int(NS / 10) 
Turn 
The number of cycles of the Turn heuristic 
2 + Int(NS / 10) 
Replication 
The number of replications of the Strategy 
1 
Optionally, the Random or Greedy procedures
will generate a specified number of solutions. The best of
these randomly generated sequences and the original solution
determines the starting solution for the remaining heuristics.
The Insert, Switch, and Turn heuristics follow
in order. Each heuristic is applied for a specified number
of cycles unless a cycle has no improvements. If a cycle leads
to no improvement, the heuristic is terminated allowing the
next heuristic to begin. The specification of the Random or Greedy heuristics
plus the numbers of the cycles for the remaining heuristics
determine the strategy. If the local optimum checkbox
is clicked the sequence number is neglected. 

The Replication input allows strategies
to be run more than once. When a randomized starting solution
is used, it is best to run several replications of the strategy
and choose the best of the local optima. The figures on
the right shows the results of six repetitions of the strategy
that begins with a random solution and continues through
cycles of the insert, switch and turn statistics. Each
repetition stops with a local optimum. The titles in column
AI of the display are followed by one to three integer
numbers. The first number is the repetition number, the
second is the number of times the heuristic type has been
visited during the strategy, and the third number is the
cycle number within the visit.
Replication
summaries are displayed on the Models worksheet
as illustrated at the right. Columns identify the heuristic
or initializing method, the number of runs, the number
of runs finding improved solutions and the value of the
best solution after the starting process or heuristic has
been performed. (The time and run/second statistics are
also shown on the worksheet, but not illustrated here.)
Row 5 shows the initial solution and rows 6 through 14
show the first replication. The replication begins with
a single random solution in row 6. The first two cycles
of the Insert heuristic,
in rows 7 and 8, result in 13 improved solutions, while
the third shows no improvement. Two cycles of the Switch heuristic,
in rows 10 and 11, yield 21 improvements, while the last
in row 12 has none. The single turn cycle in row 13 shows
no improvement. One more insert cycle is required to meet
the requirement for a local minimum. When three heuristics
are used, three consecutive 0's in the Improve column indicate
a local optimum.
The objective value in row 14 is the objective value for
a local optimum solution. Row 16 compares this solution
to the value of the best solution obtained in the previous
replications or the original solution.
Other replications repeat in like manner. Since all begin
with different random initial solutions, each may terminate
with a different local optimum. The Best Value column in
rows 14, 24, 38, 48 and 59 are all different indicating
that four local optimum solutions have been discovered.
The best of these is in row 38.


The last replication is reported
in a new column to avoid overwriting other contents on
the worksheet. We see one more local optimum values in
row 14.
The Total row reports 19419 runs
with 191 improved solutions. The best solution has
the value of about 245. The decision values and sequence
values are reported on the model and result worksheets. 


Local Optimum Solutions 

The sequences for six local solutions found during
the search are
shown below. Using the selected strategy, none
of these solutions can be improved. The solutions are sorted
by their objective values with the best on top. 


The best and worst or the six local optima
are shown in the figures below. The best solution (on the left)
looks reasonable. The worst (on the right) illustrates the
problem of heuristic solutions. It is
not
hard to see that the yellow trip is not advisable, but no
single
change can improve it. There are several ways to reduce the
problem of local minima including:
heuristics that sometimes accept nonimproving moves, solving
the problem to optimality as an integer program, and solving
the problem with a large number of random initial solutions and
selecting the best local optimum. All of these solutions increase
the computational cost
of finding good solutions. The only available solution for this
addin is to use many repetitions of the strategy. Later versions
of the addin may investigate the other options. 


Builtin Strategies 

The buttons on column D of the Results worksheet
initiate several builtin strategies. The Repeat field
specifies the number of replications for the strategy.
The first two buttons on the left are not affected by the
number in this field, but multiple replications are useful
for the last two strategies that involve random initial
solutions.
The first button in column D evaluates the current solution
without searching for a better solution. This might be
useful when the analyst is adjusting a solution determined
by the addin. The current sequence is defined by the entries
in column E of the Results worksheet.
When the button is clicked, the sequence is transferred
to the Model worksheet to evaluate the solution.
Computed results on the Model worksheet are subsequently
transferred back to the Results worksheet. The
userdefined sequence must have no loops and must have
a unique index in each row of column E.


The buttons on the right side (column H)
call VBA subroutines. The Initial
Solution button
creates a simple solution for the VRP problem illustrated
at the right. The initial sequence is in column E. The example
has four trucks and for the initial solution truck 1 through
3 have no deliveries, while truck 4 has them all. In general,
when the plan has several trucks, the last truck handles
all the deliveries. The route through the deliveries is determined
by the delivery indices. This is usually not a good solution,
but it provides a convenient starting point for illustrating
the various options.
The Search button provides for a userdefined
search as described below. The Map button creates
a worksheet mapping the coordinates of the trucks and deliveries
and displays the route in column E. The Google Earth button
helps to create a Google Earth display of the results. This
is described on a later page of this section. 

The Improve Current Solution button
on the left seeks a local optimum solution starting from
the sequence in column E. The statistics on the right are
for the simple initial solution pictured above. Only two
insert cycles are used because the second insert cycle
made no improvement. Three switch cycles, and a turn cycle
completes the first replication. Since improvements occur
after the insert cycles in rows 6 and 7, a second replication
begins in row 12. The process is terminated when that cycle
provides no improvement. It is interesting that this solution
is better than the best found with six random starting
solutions.


The Random Plus Improvement button
generates a random solution and improves that solution
to a local optimum. The random solution value is in row
6.
The final solution is a local minimum. 

The greedy initial solution is
constructed in a manner that usually results in a better
solution than a random start. As for the simple initial
solution the first 3 trucks are assigned no deliveries
and the last truck has all the deliveries. Rather than
list the deliveries in order of index as for the simple
initial solution, the greedy solution selects
a random
order for the deliveries. Then a cycle of the insert heuristic
considers each delivery in order and places it in the
position that most improves the objective value. Since
this is a onepass greedy process, it rarely obtains even
a local optimum, but it leads to better initial solutions
than
a purely random start mechanism. In the example the result
is reported in row 6.
The improvement strategy is then applied to obtain a
local optimum. For the example, the final solution is even
worse than the random start. There is no guarantee that
a better initial solution leads to a better final solution.
Multiple replications are allowed for this option. 


Userdesigned Strategies 

Clicking the Search button
at the top of the Results or Model worksheets
presents a dialog for choosing the strategy. The dialog below
selects a greedy start that is the best of three random greedy
solutions (the top field on the right). Clicking
the Improve check box on the right without checking
the Local Optimum check box allows cycle numbers to
be specified for the strategy. The heuristics are always applied
in the order insert, cycle and turn, but different numbers
of cycles may be entered, including 0. The search replication
box is set to 3. The search activity is detailed starting in
column AI. Each replication begins with the best of three greedy
solutions and continues until either the desired number of
cycles has been performed or local optimums are obtained. Since
optimality conditions are not satisfied, the solution of a
replication may not be a local optimum, although in this case
it was shown to be local optimum earlier on this page.
We provide the Search option to allow student experimentation
and to test alternative strategies. For a large problem it
might be better to select the number of cycles, because the
solution time is not easily bounded for the
local optimum option.


A variety of strategies are available through
the algorithm. There is no limit to the size of the problems
that can be solved with the addin except as limited by the
number of columns on the Excel worksheet. Of course larger
problems require more solution evaluations to reach quality
solutions and heuristic cycles use
more time. Excel with the Routing addin is not a
competitor to commercial programs or more efficient algorithms
running on powerful computers, but this tool may have value
to students and to small organizations. 


