Computation Section
Vehicle Routing

A typical application of the Routing add-in is to plan routes for a delivery company that serves a small geographic area. The company schedules deliveries for each day to several sites in the area, and the company has one or more delivery vehicles. Our goal is to assign vehicles to deliveries and sequence the deliveries so that all deliveries are completed during the day. Generally, a single vehicle will carry several deliveries. The fleet of trucks must cover all demand.

The problem can be of any scale. We illustrate the methods of this section by the well known traveling salesman problem involving visits to state capitals in the continental United States.

 The figure below shows the capitals of the 48 continental states of the United States and the national capital in Washington DC. A traveler starts in Washington DC and travels through each capital and finally returns to Washington DC. The traveler 'goal is to minimize the total travel distance on the route. The routing add-in is to find the optimum route. Traditionally this is called the traveling salesman problem. or TSP. The figure is from the Google Earth web-based application.. The add-in has subroutines that create the code for this display.
state capitals
  The figure below shows a route found by the add-in. Although the route is a local minimum with respect to the algorithm used to solve the problem, there may be better solutions. The methods of this add-in find local optimum solutions, but there is no guarantee that the solution found is optimum. When geographic coordinates describes the locations of the problem, the add-in provides the code for the Google Earth display. The red push pins identify the state capitals. The single black push pin shows the start and end point of the route.
  An alternative representation is the Map constructed by the add-in and shown on an Excel worksheet. Points are located with the Cartesian coordinate system.
states tsp
  When there is more than one traveler, we will call the problem the Vehicle Routing Problem, VRP. Here there are two vehicles and the locations to visits are called delivery locations. Using the state capital locations, the figure below shows a solution of the vehicle routing problem with two vehicles with one vehicle satisfying 25 deliveries and the other 24. One vehicle starts and ends at Washington DC, while the other starts and ends at the Olympia, Washington (the northernmost state capital among the 48 considered. The routes are distinguished by red and green. The solution is probably not optimum as it seems like it would be more efficient to divide the country into eastern and western routes. We consider the example further on the States page of this section. The example worksheet can be downloaded from the list at the top of the page it is called: Routing_state_capitals.xls.
state route two vehicles

This Vehicle Routing add-in is a modification of parts of the Combinatorics add-in. The Optimal Sequence add-in was constructed with parts of the Optimize add-in. The new add-in is better in many respects since it is devoted to the single purpose of routing.

My inspiration for this topic is an e-mail I received some time ago from a member of a group that delivers singing messages on Valentines Day. Calls come from citizens of the city asking to schedule the delivery of singing valentines. Each delivery requires a team of live singers. Of course the destinations are in all parts of the city, and singers are also geographically dispersed. The chair person of the group wanted a tool to assign and route singers to destinations. Since this is a once-in-a-year event staffed by volunteers, the person didn't have money to spend, so he tried my Combinatorics add-in for TSP problems. The add-in was unsuccessful because it could not handle multiple vehicles.

At a seminar I heard about the problem of assigning Catholic priests to outlying rural parishes in Texas. Each parish could not afford a dedicated priest so the problem was to assign priests to the parishes to minimize the travel required. Again the problem is a VRP with priests in the role of vehicles and parishes in the role of delivery locations.

A small-time liquor distributor once wrote that he wanted a tool to schedule his delivery trucks. He noted that commercial VRP packages start in price at about 10,000 $US. That cost was too high for him, so he wondered if one of my add-ins might be useful.

My latest direct experience was with students from Texas A&M working on their senior project. VRP was part of their design problem. The VRP included with the Combinatorics add-in was insufficient in some respects. In particular the add-in required that when one trip was completed at a depot, the next truck was forced to leave from the same depot. This makes it difficult to model multi-depot problems with the Combinatorics add-in. This experience lead directly to the revision of the add-in reported here. With the new add-in there is no restriction on the starting and returning locations.

Vehicle routing is necessary for many businesses and there are a number of vendors offering commercial software and services. OR/MS Today has published regular surveys on features and prices of VRP products. Click here to see the 2010 survey. The industry provides useful tools, but their costs may be excessive for small businesses and nonprofit institutions. Our routing add-in should be thought of as a very distant and very introductory cousin of the commercial systems. Since it is free, the add-in might be useful for institutions that are small and/or poor. Also, the VBA code can be modified to accept new model features so students and others are invited to experiment.

The Routing add-in uses the Optimal Sequence add-in that provides search heuristics for finding solutions, so the two add-ins must be simultaneously installed. The only limits to the size of problems that can be formulated are the worksheet limitations of Excel, but for large problems, time and memory requirements may be excessive. Since heuristics are used, solutions found are local optimums. Options are included to find several local optimum solutions during a single run of the add-in.

bottom bar

Return to Top

tree roots

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

Next Page