Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints Marius M. Solomon Operations Research, Vol. 35, No. 2. (Mar. – Apr., 1987), pp. 254-265.
Stable URL: http://links.jstor.org/sici?sici=0030-364X%28198703%2F04%2935%3A2%3C254%3AAFTVRA%3E2.0.CO%3B2-E Operations Research is currently published by INFORMS.
Your use of the JSTOR archive indicates your acceptanceof JSTOR’s Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR’s Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisherregarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/journals/informs.html. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission.
The JSTOR Archive is a trusted digital repository providing for long-term preservation and access to leading academicjournals and scholarly literature from around the world. The Archive is supported by libraries, scholarly societies, publishers, and foundations. It is an initiative of JSTOR, a not-for-profit organization with a mission to help the scholarly community take advantage of advances in technology. For more information regarding JSTOR, please contact [email protected].
http://www.jstor.org Fri Jan25 09:47:51 2008
ALGORITHMS FOR
THE VEHICLE ROUTING AND SCHEDULING PROBLEMS
WITH TIME WINDOW CONSTRAINTS
MARIUS M. SOLOMON
Northeastern University, Boston, Massachusetts
(Received February 1984; revisions received October 1984; March, October 1985; accepted December 1985)
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problemswith time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate theproblems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
key element of many distribution systems is the routing and scheduling of vehicles through a set of customers requiringservice. The vehicle routing problem (VRP) involves the design of a set of minimum-cost vehicle routes, originating and terminating at a central depot, for a fleet of vehicles that services a set of customers with known demands. Each customer is serviced exactly once and, furthermore, all the customers must be assigned to vehicles without exceeding vehicle capacities (see Bodin et al. 1983 for acomprehensive survey). In the vehicle routing and scheduling problem with time window constraints (VRSPTW), these issues must be addressed under the added complexity of allowable delivery times, or time windows, stemming from the fact that some customers impose delivery deadlines and earliest-delivery-time constraints. In the presence of time windows, the total routing and scheduling costs include notonly the total travel distance and time costs considered for routing problems, but also the cost of waiting time incurred when a vehicle amves too early at a customer location or when the vehicle is loaded or unloaded. The VRSPTW has emerged as an important area for progress in handling realistic complications and generalizations of the basic routing model (Schrage 1981, Bodin et al.). Time…
