|
|
 |
Vehicle
Routing |
 |
-
Results |
|
|
The Make Plan button
at the top of the Data worksheet creates two worksheets,
the Model worksheet and the Results worksheet.
The model worksheet implements our model of the vehicle routing
problem. It is used by the Optimize Sequence add-in
to evaluate solutions. The Results worksheet presents
the results of the solution algorithms. For the casual user
it is not really necessary to learn all the details of the
model worksheet, so we present the results worksheet first.
The figure below shows the results worksheet as it first appears
and before any attempt to find a good solution. Click the figure
to open a window with a larger illustration. The solution is
described by the sequence shown in column E. Each truck, site
and trip are assigned a unique index with the trucks number
first, then the sites, and then the additional trips. For the
example the two trucks are indexed 1 and 2. The ten deliveries
are indexed 3 through 12. There are no extra trips, but we
add the final return of truck 2 as the final index, 13. The
initial sequence is in index order as shown below. The Sequence column
is shown in green to indicate that the user may change the
sequence. When one of the search routines in invoked, the add-in
fills this column with the solution obtained.
|
|
| |
Some of the columns of this form are taken
from the data worksheet and others are transferred from the
model worksheet. We list below the meanings of the
various columns. The contents of the columns are controlled
by the add-in so any user changes, except in the sequence column,
are neglected. The yellow cells at the top of the page hold
Excel formulas that compute the various cost components. Our
goal is to find a sequence that minimizes the Total Cost computed
in cell L7.
Red lines on the table indicate the start of the first trips
for the trucks, while blue lines indicate starts of subsequent
trips. For the initial solution the first truck begins at time
0 visits no delivery sites and immediate returns to the depot.
The second truck then handles all the remaining deliveries
and finally returns to the depot. Of course this not a good
solution, but it will serve to illustrate the columns of the
form. |
| |
| Trip |
This is the untitled column A on the figure. It is used
to identify the truck or trip used by part of the sequence.
Truck 1 is always encountered first. |
| Index |
This is an index of the sequence and the row numbers of
the display. |
| Sequence |
The sequence is given by the indices assigned to the trucks,
deliveries and additional trips assigned on the data worksheet. |
| Name |
The names are assigned on the data worksheet. |
| Location |
The map locations are assigned on the worksheet. |
| Trip |
Trips are numbered sequentially. Truck 1 is always assigned
trip 1, but the trip numbers of other trucks and deliveries
depend on the sequence. |
| Time Available |
This is assigned on the data sheet. The default value
is 0. |
| Early Time |
This is assigned on the data sheet. The default value is
0. |
| Arrive |
This is the arrival time at a site. The arrival time is
computed considering the distances between adjacent sites
on the route, the delivery times and the available times.
Trucks run routes independently. A truck begins its trip
at the truck's available time, 0 for the example. Both trucks
start at time 0. The arrival time for subsequent deliveries
depend on the information in the remaining columns. |
| Site Time |
These times are defined on the data sheet. |
| Late Time |
This is assigned on the data sheet. The default value is
9999. |
| Depart |
A truck departs from the site at the arrival time plus
the site time. The departure times are multiplied by the
duration penalties to compute the cost component of L3. |
| Local Travel Time |
After a truck departs a site it must travel to the assigned
map location. The time for this trip is in this column. |
| Travel Time to Next Site |
On arriving at the map location, the truck then travels
to the map location of the next site in the sequence. It
then travels the local time to reach next site. This column
shows the total of these three times. The departure time
plus the local travel time plus the travel time to the next
map location, plus the local time to the next site determine
the arrival time to the next site. In the example truck 2
leaves the depot at time 18, has 0 local travel time, and
the time to the next site is 126. Then the arrival time to
the next site (the first delivery site) is 144. |
| Early |
This is the amount of violation of the early time constraint.
Since all early times were 0, there is no violation of this
constraint for the example. The early times are multiplied
by the early penalties to compute the cost component in cell
L4. |
| Late |
This is the amount of violation of the late time constraint.
Since all late times were 9999, there is no violation of
this constraint for the example. The early times are multiplied
by the early penalties to compute the cost component in cell
L5. |
| Cumulative Capacity |
Each truck or trip contributes to capacity and each delivery
takes capacity away. The cumulative capacity computes the
amount of capacity remaining at any point in the sequence.
For the example, each truck has capacity for 5 deliveries.
The first truck makes no deliveries, so its capacity is essentially
wasted. The second truck makes all 10 deliveries. The column
shows that after the fifth delivery the cumulative capacity
becomes negative. This indicates a shortage in capacity. |
| Capacity Short |
This column reports a positive value equal to the cumulative
capacity when the later number is negative. This indicates
how much the resource constraint is violated. The total short
is multiplied by the resource violation penalty to compute
the cost component in L6. |
|
| |
The information entered on the Data worksheet
defines the set of the deliveries required for some interval
of time, perhaps a day of operation. The add-in tries to develop
a schedule that will meet the delivery requirements with the
trucks and the trips provided. The criteria is a composite cost
that includes the cost for travel, the total duration penalties,
the total early and late penalties, and the total resource violation
penalties. The model involves both time and distance as will
be reflected on the model worksheet. The results worksheet is
not dynamic. Changing the information in some cells does not
automatically reflect in the values of other cells. |
Buttons |
| |
At the top of the page there are
several buttons. The first button on the left evaluates the
current solution. If the sequence is changed in column E,
click this button to see the results of the change. The second
button, Improve Current Solution, uses a two-change
search process that interchanges pairs of the decision vector
in an attempt to improve
the solution. The result is shown in column E and the results
page reflects this solution. The third button, 10 Random
plus improvement generates
10 solutions at random and improves the best of the ten. The
first button on the right, Search, opens a dialog
that allows the specification of more complicated search options.
The Map button creates a worksheet with a map of the
solution. The Data Worksheet button makes the
data worksheet active.
To illustrate the improvement process we choose
the 10 Random plus improvement button. The results are
shown below. Click the figure to see a larger illustration. The
first truck visits delivery sites 6, 1, 8, 7 and 3. The second
truck visits sites 10, 5, 8, 4, and 2, and finally returns to
the depot. There is no shortage in the capacity since each truck
makes 5 deliveries. Notice that the sequence of sites and trucks
defines the two routes. When truck 1 leaves site 3, the last one
it visits, it returns to the depot. Note that the return time of
truck 1 is not explicitly computed on the table. Rather the return
of truck 1 signals the change in the sequence to the route of truck
2. |
|
| |
Clicking the Map button creates a map
showing the two routes. The map coordinates and site names
are too small to be displayed here. |
| |
|
| |
There is no guarantee that this
is an optimum route solution. The multiple vehicle routing
problem is a hard problem and only exhaustive enumeration can
assure optimality. Although exhaustive enumeration is possible
for this small problem, for most problems the necessary computation
is prohibitive.
On a later page we show examples of this problem with other
parameters, but the next page considers the model worksheet. |
| |
|
|
