Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints
American Journal of Mathematical and Management SciencesPublished 1 February 1986
Edward K. Baker, Joanne R. Schaffer
Citations81
SJR quartileQ3
SJR score0.35
SNIP0.78
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
Two test data sets for the vehicle routing and scheduling problem with time window constraints are studied and initial solutions are obtained using a variety of heuristics, then improved using branch exchange procedures modified to incorporate the timewindow constraints.
Abstract
SYNOPTIC ABSTRACTBranch exchange techniques, such as the well-known 2-opt and 3-opt procedures, are among the most powerful heuristics available for the solution of the classic vehicle routing problem. The imposition of time window constraints on customer delivery time within the vehicle routing problem, however, introduces several complexities that can reduce the power of these techniques. In this paper, two test data sets for the vehicle routing and scheduling problem with time window constraints are studied. Initial solutions are obtained using a variety of heuristics. These solutions are then improved using branch exchange procedures modified to incorporate the time window constraints.
Keywords
Engineering
Technological Forecasting and Social ChangeEuropean journal of operational research
5,378 Citations1990Carlos M. F. Dibb, Carlos M. F. Monteiro +2 more
It is proved the NP-completeness of the problem of minimizing the overhead for scheduling trees on m processors, and then an algorithm is proposed that provides optimal schedules when complete trees are considered.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
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.
NetworksComplexity of vehicle routing and scheduling problems
1,288 Citations1981Jan Karel Lenstra, A. H. G. Rinnooy Kan
The complexity of a class of vehicle routing and scheduling problems is investigated and known NP-hardness results are reviewed and compiled to compile the worst-case performance of approximation algorithms.
Transportation ScienceA Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem
588 Citations1980Harilaos N. Psaraftis
An investigation of the single-vehicle, many-to-many, immediate-request dial-a-ride problem is developed, with a Dynamic Programming approach which exhibits a computational effort which is asymptotically lower than the corresponding effort of the classical Dynamic Programming algorithm applied to a Traveling Salesman Problem of the same size.
INFORMS Journal on Applied AnalyticsImproving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer
496 Citations1983Walter J. Bell, Louis M. Dalberto +6 more
For Air Products and Chemicals, Inc., inventory management of industrial gases at customer locations is integrated with vehicle scheduling and dispatching, and the system has been saving between 6% to 10% of operating costs.
NetworksRouting with time windows by column generation
361 Citations1984Jacques Desrosiers, François Soumis +1 more
This work uses column generation on a set partitioning problem solved by simplex and branch-and-bound to determine the number of vehicles required, together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to thenumber of vehicles, and the travel costs between trips, are minimized.
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.
Journal of the Operational Research SocietyBases for Vehicle Fleet Scheduling
224 Citations1967T. J. Gaskell
The outcome is that no basis is superior to the others in all cases and that the suggestion of Clarke and Wright is a reasonable one to use.
NetworksCombinatorial optimization and vehicle fleet planning: Perspectives and prospects
161 Citations1981Thomas L. Magnanti
This discussion shows that prospects for applying exact methods, possibly in conjunction with heuristics, are far from fully realized and points to vehicle fleet planning as a tempting target of opportunity for further investigation.
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.
Operations ResearchTechnical Note—An Effective Heuristic for the <i>M</i>-Tour Traveling Salesman Problem with Some Side Conditions
123 Citations1977Robert A. Russell
This note presents a heuristic for determining very good solutions for the symmetric M-tour traveling salesman problem with some side conditions that pertain to load, distance and time, or sequencing restrictions.
NetworksOn the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
101 Citations1986Marius M. Solomon
Analysis of approximation methods for the vehicle routing and scheduling problem with time window constraints shows that their worst-case behavior on n customer problems is at least order of n for minimizing the number of vehicles used, the total distance traveled, and the total schedule time.
European Journal of Operational Researchk-Interchange procedures for local search in a precedence-constrained routing problem
95 Citations1983Harilaos N. Psaraftis
A method is developed which still finds the best k-interchange that can be produced from an initial feasible DARP tour in O(Nk) time, the same order of magnitude as in the Lin heuristic for the TSP.
An Effective Heuristic for the M-Tour Traveling Salesman Problem with Some Side Conditions
75 Citations1977Robert A. Russell
A I I E TransactionsEfficient Heuristic Solutions to an Airline Crew Scheduling Problem
53 Citations1979Edward K. Baker, Lawrence Bodin +2 more
It is demonstrated that near-optimal solutions to this class of very large airline crew scheduling problems may be obtained by using heuristic procedures similar to those used in vehicle routing and scheduling.
NetworksNew lower planes for the network design problem
9 Citations1987Ravindra K. Ahuja, V. V. S. N. Murty
Two new lower planes for the network design problems through combinatorial arguments are derived and one is of complexity O(n4) and produces a lower bound which is sharper than those of existing lower planes.