Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Operations ResearchPublished 1 April 1987
Marius M. Solomon
Citations4,181
SJR quartileQ1
SJR score2.56
SNIP1.83
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Abstract
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with 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 the problems, 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.
Keywords
Engineering
Operations ResearchScheduling of Vehicles from a Central Depot to a Number of Delivery Points
3,846 Citations1964Graham Clarke, J. W. Wright
An iterative procedure is developed that enables the rapid selection of an optimum or near-optimum route and has been programmed for a digital computer but is also suitable for hand computation.
Journal of the ACMInteger Programming Formulation of Traveling Salesman Problems
1,994 Citations1960Casey Miller, A. W. Tucker +1 more
The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known “Travelling Salesman Problem” in integer programming terms.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
Operations ResearchA Heuristic Algorithm for the Vehicle-Dispatch Problem
1,157 Citations1974Billy E. Gillett, Leland R. Miller
The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell’s and is slightly less so than Christ ofides andEilon's.
NetworksA generalized assignment heuristic for vehicle routing
1,060 Citations1981Marshall L. Fisher, Ramchandran Jaikumar
This paper presents a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost and shows that it has outperformed the best existing heuristics on a sample of standard test problems.
Transportation Research Part B MethodologicalA heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows
515 Citations1986Jang-Jei Jaw, Amedeo R. Odoni +2 more
A heuristic algorithm is described for a time-constrained version of the advance-request, multi-vehicle, many-to-many Dial-A-Ride Problem (DARP).
NetworksImplementing vehicle routing algorithms
332 Citations1977B. L. Golden, Thomas L. Magnanti +1 more
This work considers heuristic algorithms for vehicle routing, comparing techniques of Clarke and Wright, Gillett and Miller, and Tyagi, and presenting modifications and extensions which permit problems involving hundreds of demand points to be solved in a matter of seconds.
NetworksState‐space relaxation procedures for the computation of bounds to routing problems
325 Citations1981Nicos Christofides, Aristide Mingozzi +1 more
This paper gives a survey of a general relaxation procedure whereby the state-space associated with a given dynamic programming recursion is relaxed in such a way that the solution to the relaxed recursion provides a bound which could be embedded in general branch and bound schemes for the solution of the problem.
Transportation ScienceAn Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time Windows
286 Citations1983Harilaos N. Psaraftis
This paper modifies the exact Dynamic Programming algorithm developed by the author for the single vehicle many-to-many immediate request Dial-A-Ride problem to solve the problem where each customer has specified upper and lower bounds for his pickup and delivery times.
NetworksFormulation and structure of more complex/realistic routing and scheduling problems
174 Citations1981Linus Schrage
This work classifies the features that seem to be encountered in real vehicle routing problems and indicates which features cause the greatest difficulty and which modeling approaches allow to represent the greatest range of practical considerations or features.
Transportation ScienceOptimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling
162 Citations1985Thomas R. Sexton, Lawrence Bodin
A heuristic routing and scheduling algorithm is shown to produce high quality solutions in reasonable computation time by testing on moderately sized real data bases from both Gaithers-burg, Maryland, and Baltimore, Maryland.
Operations ResearchTechnical Note—An Exact Algorithm for the Time-Constrained Traveling Salesman Problem
127 Citations1983Edward K. Baker
The dual of the formulation is shown to be a disjunctive graph model, which is well known from scheduling theory, and a longest path algorithm is used to obtain bounding information for subproblems in a branch and bound solution procedure.
Management ScienceScheduling School Buses
82 Citations1984Arthur J. Swersey, Wilson Ballard
Two integer programming formulations of the scheduling problem are presented and applied to actual data from New Haven, Connecticut for two different years, as well as to 30 randomly generated problems, finding that the few fractional values can be adjusted to integer values without increasing the number of buses needed.
An Effective Heuristic for the M-Tour Traveling Salesman Problem with Some Side Conditions
75 Citations1977Robert A. Russell
Decision SciencesA SIMULATION AND STATISTICAL ANALYSIS OF STOCHASTIC VEHICLE ROUTING WITH TIMING CONSTRAINTS
64 Citations1978Thomas M. Cook, Robert A. Russell
This paper examines a generalization of the vehicle-dispatch problem in which time constraints as well as stochastic demand and travel times are considered, and an effective heuristic is tested on single-estimate travel times.
The Computer JournalA computer application to a transport scheduling problem
60 Citations1967H. G. M. Pullen
Journal of the Operational Research SocietyVehicle Scheduling with Timed and Connected Calls: A Case Study
50 Citations1968Kenneth Knight, J. P. Hofer
A manual method for scheduling the vehicle fleet of a contract transport undertaking was developed and resulted in about 15 per cent of vehicle time being made available for additional revenue-earning work without increase in fleet size.
LARGE SCALE IMPLEMENTATION OF A TIME ORIENTED VEHICLE SCHEDULING MODEL
2 Citations1982Edward K. Baker, Sara F. Rushinek
The authors state that although the current implementation of the time oriented vehicle scheduling algorithm has been developed to meet the operational requirements of the scheduling module of theCARSD/MIS system, delays in the CARSD/ MIS project prevented the required operational interface and testing.