The Model worksheet is entirely constructed by the Routing add-in. It's purpose is to collected data from the Data and Distance worksheets and interact with the search algorithms in the Optimize Sequence add-in. Although users familiar with the Optimize add-in may experiment by changing some features of this worksheet, in general it is better to leave it alone. The results obtained from the model are reported on the Results worksheet.

In the following we divide the model worksheet into three parts to simplify the discussion. The parts are different in function, so the division is not arbitrary. The particular solution shown in the example is the same one illustrated on the Results page.

Optimize Model

The top of the model worksheet holds control buttons, the optimization model, and data regarding the distance between map locations. Rows 10 through 19 hold the decision variables, objective value, feasibility indicator and computational cells related to the routing model. A similar form is constructed by the Optimize add-in as described on the Combinatorial Form page. The form is particularly adapted to the TSP on the Traveling Salesman page. Here we adapt the TSP form for the routing problem.

The main difference between the TSP and the routing models is the incorporation of multiple trucks and multiple trips on the list of items that will be visited. The first two indices are associated with the two trucks of the example. Following this, the ten delivery sites are listed. The last index is associated with the return trip for the last truck. If additional trips were allowed these are included just before the Return column. In general, multiple trucks are listed first, the delivery sites are listed next, and finally multiple trips are listed last.

We seek the sequence of the 13 items that will minimize the objective computed in cell G12. Items 1and 13 are fixed in the sequence as the first and last. The other items are varied in the search for the optimum. The variables of the problem are the green cells in row 16. An entry for an item is the next item to visit. For the example the next item to visit after item 1 (Truck 1) is item 8 (site 6). The next item after item 8 is item 12 (site 10). The sequence does not immediate appear in row 16, but by tracing the next item to visit for each item the sequence can be generated. The sequence is computed in the yellow cells of row 17. For the example, the sequence is (1, 8, 3, 11, 9, 5, 2, 12, 7, 10, 5, 4, 13). The colored indices in the sequence are positions related to the trucks. The particular sequence defines the route (8, 3, 11, 9, 5) for truck 1. The route begins at the location of truck 1 and ends at the location of truck 2. The route for truck 2 is (12, 7, 10, 5, 4), beginning at the location of truck 2 and ending at the return depot. The travel distances associated with the links of the trip are computed in row 19. The cells in these rows hold look-up functions that choose numbers from the distance table starting in row 21. For example the value 39 in cell E19 is obtained from the 8th row of the travel distance table.

Data Cells

Results Cells

The results cells starting in row 55 are controlled by the current decision variables. All the cells are colored yellow to indicate that they contain Excel formulas. The columns are ordered by the current sequence. The display is dynamic in that the columns change as the decision variables in row 16 change. For each trial solution the objective value is computed from this portion of the worksheet.

The sequence of trucks and delivery sites is in row 56. The trip row (57) gives an integer index that indicates the components of the sequence that are assigned to the various trips. The current example has two trips representing the routes of the two trucks. The times available, early times, site times, late times, and local travel times are transferred by index functions from the data cells. An arrival time in row 60 is computed as the sum of departure time of the previous item plus the travel time to the next site. If this turns out to be earlier than the time available, the time available becomes the arrival time. The departure time is computed as the arrival time plus the site time. The travel time to the next site is the sum of: the local travel time from the current site to its map location, the intersite distance between the current site and the next site, and the local time to the next site.

Row 60 shows the arrival time at each site and row 63 shows the corresponding departure time. Notice that starting at truck 1, the times increase through the route of truck 1 until truck 2 is encountered in the sequence. Then the arrival time for truck 2 is 0. This is beginning of the second trip. The second trip occurs simultaneously with the first trip. The second trip is completed by the return to the depot.

The evaluation of the sequence in terms of the early and late times and the resource shortages begins on row 68. Since the example has no bounding early and late times, all the entries in rows 68 and 69 are 0. Row 70 shows the cumulative capacity for the sequence. When a new truck is assigned to a route, the capacity is the capacity of that truck. As the truck visits delivery sites, the cumulative capacity is decreased. A shortage is indicated by a negative number in this row. Row 72 reports the amounts of the shortages. Since the current sequence has no shortage, the contents of this row are 0.

Rows 73 through 76 numerically evaluate the solution. Row 73 shows the travel costs. The duration costs in row 74 are computed by multiplying the departure times by the duration penalties. The example uses 0 as the duration penalties, so the entries are all 0. The early and late costs multiply the early and late amounts by the penalties for these factors. The objective function finally computed in cell G12 at the top of the page is the sum of the contents of the cells in this array plus the shortage costs for the resources.

Sequence Optimization

The Search button at the top of the page presents a dialog with various search options. A similar dialog is presented by the Optimize add-in where the details of the dialog are presented in detail. For the example we have chosen to generate 10 solutions at random and improve the best of these by two-way interchanges of the decision variables in row 16.

Although an acceptable solution was obtained for this small problem, the search difficulty becomes exponentially more difficult as the problem size grows. It also becomes more difficult as we add complexity to the problem by making the early and late times restrictive and as more resources are added. The worksheet evaluation with each solution is not very fast computationally. Even one pass through the improvement process takes a large number of individual solution evaluations. This is the price to pay for generality.

Whether this add-in is sufficient for actual practice has not been demonstrated. We can model and solve small problems and perhaps that will be sufficient for students and for small delivery systems found in practice. One strategy is to generate a great number of random solutions and choose improve the best. Individual solutions are easy to evaluate and a limited amount of improvement is very beneficial.

Buttons

At the top of the page there are several buttons. The first button displays the Search dialog shown earlier. The Map button creates the map of the current solution. This is the same map as the one created by a similar button on the results page. The buttons on the right open the unique Data and Results worksheets corresponding to the Model worksheet. Whenever data is changed on the Data worksheet the Model worksheet must be created anew to reflect the new data.