Computation Section
Subunit 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 and improve solutions. The Results worksheet reports 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.

Most of the figures on this page are reduced for presentation. A larger version shows when the picture is clicked.


Results Worksheet


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. The origin and terminal truck sites and the delivery sites are each assigned a unique index with the trucks numbered first and then the delivery sites. For the example, the first truck's origin and terminal sites are numbered 1 and 2. The second truck has sites numbered 3 and 4. The twenty deliveries are indexed 5 through 24. The initial sequence is in index order with one exception. The first three truck sites are first in the sequence, followed by the delivery sites, and finally site 4, the terminal site of the last truck. This means that the initial solution has all the deliveries assigned to the last truck. Although this is not often a good solution, it is used as a starting solution for the heuristic search methods to be described later.

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.

austin results initial


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 hold the various cost components as computed on the model worksheet. Our goal is to find a sequence that minimizes the Total Cost computed in cell L7.

Red lines on the table indicate the start and finish of truck routes. For the initial solution the first truck begins at time 0, visits no delivery sites, and immediate returns to its finish site. The second truck then handles all the remaining deliveries. Of course this not a good solution, but it will serve to illustrate the columns of the form.

Column C This is the untitled column C on the figure. The column identifies where each truck begins its trip.
Column D This column is also untitled. It holds the indices of the display
Sequence (E) The sequence is given by the indices assigned to the truck and delivery sites. The initial sequence is in column E. The solution sequence determined by the add-in will be placed here.
Name (F) The names are assigned on the plan-data worksheet.
Location (G) The map locations are assigned on the plan-data worksheet.
Location Name (H) The map location names associated with the locations of the truck and delivery sites.
Type (I) T indicates a truck origin and its terminal site is R. Deliveries have the type D.
Trip (J) 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 (K) This is assigned on the plan-data sheet. The default value is 0.
Early Time (L) This is assigned on the plan-data sheet. The default value is 0.
Arrive (M) 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. The arrival times for subsequent deliveries are determined on the model worksheet.
Site Time (N) These times are defined on the plan-data sheet.
Late Time (O) This is assigned on the plan-data sheet. The default value is 9999.
Depart (P) 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 (Q) 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 (R) On leaving the customer location the truck travels the local distance to the map point nearest the customer location. The truck then travels to the map location of the next site in the sequence. It then travels for the local time to reach next customer location. Each of these distances are divided by the velocity of the truck. This column shows the total of these three times.
Early (S) This is the amount of violation of the early time constraint.
Late (T) This is the amount of violation of the late time constraint.
Cumulative Capacity (U) Each truck 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 ten deliveries. In the initial solution the first truck makes no deliveries, so its capacity is essentially wasted. The second truck makes all 20 deliveries. Column U shows that after the tenth delivery the cumulative capacity becomes negative. This indicates a shortage in capacity for the second truck.
Capacity Short (V) 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 Planning 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 provided. The criterion 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.




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 insert, switch and turn heuristics to improve the solution. The third button, Random plus improvement option generates a random solution and improves it to a local minimum. The Greedy plus improvement option generates a greedy solution and improves it to a local minimum. The first button on the right creates the feasible initial solution. The Search button opens a dialog that allows the specification of more complicated search options. The Map button creates a worksheet with a map of the current solution. The Google Earth button creates a program the is used to show the solution on the Google Earth application. This button only appears when locations are given geometric coordinates.

results buttons

The cell E11 allows the heuristic to be run several times in succession. It is only effective for one of the improvement options that involve random starts. For example if the repeat number is set to 10 and we choose the Random plus Improvement option, the improvement process is carried out ten times. If more than one local optimum is reached. The solution found is the best of these.

To illustrate the improvement process we choose the Random plus Improvement button. The results are shown below. Click the figure to see a larger illustration. The first truck visits delivery sites 14, 13, 12, 16, 9, 7, 20, 17, 1, and 8. The second truck visits sites 3, 6, 10, 18, 5, 15, 2, 11, 4, and 19. There is no shortage in the capacity, since each truck makes 10 deliveries. The sequence of trucks and deliveries defines the two trips. There may be better solutions than this one since a heuristic solution cannot guarantee the optimum.

results austin



  Clicking the Map button creates a map showing the two trips. Trips routes between map locations are colored green and red. Delivery locations are yellow and truck locations are black.
austin 20 map



There is no guarantee that this is an optimum solution. The multiple vehicle routing problem is a hard problem. There are optimization models that can assure optimality, however, large problems may lead to prohibitive computation times even on powerful computers.

On a later page we show examples of this problem with other parameters, but the next page considers the model worksheet.

Return to Top

tree roots

Operations Management / Industrial Engineering
by Paul A. Jensen
Copyright 2004 - All rights reserved