The vehicle routing problem is a combinatorial problem. For a problem of even moderate size, the number of feasible solutions is finite but very large. There is no known algorithm that can determine optimal solutions for very large problems. We cannot hope to solve meaningful problems with the Excel based optimization tools in the ORMM collection, so we seek good solutions with heuristics.

The VRP is represented as a sequencing problem. The sequence gives an ordered list of nodes representing truck and delivery locations. Each truck contributes two nodes to the problem, one for leaving and one for returning, and each delivery contributes one node. Starting from an initial sequence, candidate solutions are discovered by applying various heuristics to the sequence. The goal of each heuristic is to reduce the cost associated with the sequence. The cost model is implemented on the Model worksheet. When the process is complete a solution is obtained that is generally much better than the starting sequence, but there is no guarantee of optimality. The final sequence provides an upper bound to the optimum objective. No lower bound is provided by our methods, so there is no measure of quality. That is an inherent disadvantage of purely heuristic approaches.

Although we believe that meaningful problems can be solved conveniently by this Routing add-in, the add-in cannot compete with the computational methods that have been designed and demonstrated by others. The Vehicle Routing problem (VRP) and the related Traveling Salesman problem (TSP) are perhaps the most studied problems of Operations Research. One of the first computer solutions was demonstrated in 1954 with a solution of a 49 city problem that passes through every state in the continental USA and Washington DC. Great progress has been made during the 50 years since this problem was introduced. At the date of this writing, a TSP with over 85,000 nodes has been solved to optimality. The excellent Traveling Salesman Problem web site (http://www.tsp.gatech.edu/) describes this problem as well as many other interesting facts about the history of the TSP.

In the following we use the term nodes to signify both truck and delivery locations. Since the example uses Euclidean metric to compute distances between two adjacent nodes. The distance is independent of the order in which two nodes appear in the sequence. When the time aspects of the problem are ineffective, the associated routing problem is said to be symmetric. Although heuristics can be adapted to take advantage of symmetry, our add-in does not. Our interest is to make the solution process as general as possible.

For this page and the next we use a problem from the routing_demo.xls

Solutions with One Truck

We illustrate the solution methods first with a TSP that is represented as a VRP with a single vehicle (truck). The data for the problem is on the TSP data worksheet shown below. The time feature is not included in the example. The capacities and loads in column G are set so that the single truck must serve all the deliveries. The map locations in column O refer the map indices shown earlier and are assigned randomly. The truck begins and ends its route at location 9. The deliveries are at various map locations. Coordinates for the locations are obtained from the distance worksheet. The truck and delivery (site) coordinates are the same as the map coordinates, so local distances are zero. The data chosen makes the problem equivalent to the TSP problem where the cost of a solution is equal to the total distance traveled by the single delivery truck.

The figure below shows the initial solution for the problem one the model worksheet. Cell E12 holds the objective function computed for the solution. The green cells in row 15 describe the current sequence by indicating the next site to be visited from each node. The yellow cells in row 16 hold the sequence of nodes on the truck's path. The yellow cells in row 18 compute the Euclidean distance between adjacent nodes on the sequence. For the simplified data of the example, the sum of the values in row 18 is the same as the objective value in E12. The goal of the optimization is to find the solution (row 15) that minimizes the objective value in E12.

We choose this initial solution because it is easy to find. From row 16 we see that the truck starts at node 1, travels sequentially to nodes 3, 4, ...12, and finishes at node 2. Node 1 is the origin for the trip taken by the truck (TO-1) and node 2 is the terminal node for the trip (TT-1). The solution in row 15 shows the sequence in a less direct way. The sequence always starts at node 1. To find the next node in the sequence we look in cell E15 to find the node 3. To find the next node in the sequence we must look at G15, to find the value 4. The process continues until the sequence is complete. Cell P15 indicates a return to node 2, the terminating node for the truck. A feasible sequence with one truck must start at node 1, visit each delivery site once and only once, and finish at node 2.

Solutions with More than One Truck

The model penalizes solutions that are infeasible with respect to resources. The second truck violates the constraint because the capacity of truck 2 is five deliveries and the sequence requires the truck to make ten deliveries. The solution process will eliminate this infeasibility as it attempts to minimize the objective function.

After a series of heuristic changes, we obtain the solution below. The solution illustrates a requirement for feasible solutions for the multi-truck problem. Except for the last truck, the originating node of the next truck must immediately follow a terminating truck node. Row 16 shows that node 2, the terminal node of truck 1, is immediate followed by node 3, the originating node of truck 2. The sequence begins with the originating node of truck 1, and it ends with the terminal node of truck 2. The nodes between the original node and terminal node describe the sequence of deliveries for each truck. Again we cannot guarantee optimality.

The Number of Feasible Solutions

For the small example with two trucks (four truck nodes), the total number of feasible solutions is the Factorial of 11. This number is over 39 million. Exhaustive enumeration of all feasible solutions can find the globally optimal solution, but this method can be used for only very small problems.