New algorithms for deterministic and stochastic vehicle routing problems (1981)

In this dissertation, a comprehensive approach to stochastic vehicle routing is developed. Effective solution procedures for various forms of this complex problem are proposed and computationally tested. These solution procedures are adapted from solution procedures that are effective for related problems such as the Traveling Salesman Problem and the Vehicle Routing Problem.
In general, given a set of points on a graph (locations on a map) the problem is to route one or more vehicles in such a way that each point and the total distance traveled is minimized. When there is one vehicle which must visit every location and return to its start location, the problem is called the Traveling Salesman Problem. This problem has been widely studied and has many applications in the transportation and scheduling fields. When there are multiple vehicles, each with a specific capacity, and a portion of this capacity is demanded at each point visited (e.g., delivery trucks), the problem is called the Vehicle Routing Problem. Such diverse operations as garbage collection, school busing, small package air mail service, along with a host of commercial distribution systems (e.g., milk, petroleum, etc.) fit this description and have benefited from algorithms designed to efficiently route the vehicles involved.
When the demands at the various points are random variables whose values only become known when the vehicle serving that point arrives, the problem is a Stochastic Vehicle Routing Problem and must be treated differently than a deterministic problem above.
In stochastic vehicle routing, the problem is to design a route system which has a short overall distance, but at the same time meets the demands on each route with regularity. If too many demand points are placed on one route, the vehicle assigned to that route will often be too small to meet all the demands. When this occurs, either some of the customers will not be served, or a special expense will be incurred in finishing the failed route. Both of these alternatives involve a cost which must be considered when designing the route system.
Before specifically addressing the Stochastic Vehicle Routing Problem, this dissertation presents two efficient algorithms for the Traveling Salesman Problem. These algorithms are described in detail and then tested on a set of problems from the literature. The new algorithms produce better solutions to these test problems than several similar heuristic algorithms that have been proposed by other authors.
After discussing these algorithms for the Traveling Salesman Problem, a new heuristic algorithm for deterministic vehicle routing is presented. It is based on an effective algorithm for the Traveling Salesman Problem, and has generated the best known solutions to several test problems in the literature.
Having presented these new algorithms, the Stochastic Vehicle Routing Problem is formulated in two different forms, a chance constrained model and a penalty function model. These models are developed and tested computationally. The new vehicle routing algorithm presented previously is adapted to handle stochastic demands and is used to generate solutions to some test problems.
The final phase of this dissertation involves adapting the stochastic vehicle routing models to the Subscriber Bus Routing Problem. This problem arises when a subscriber bus system in which customers sign up in advance for bus service to and from some large employment center is used as an alternative to the personal car. Such systems have arisen as a result of the recent escalation of automobile and gasoline costs.