A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints
European Journal of Operational ResearchPublished 24 June 2005
Zhihai Xiang, Chengbin Chu, Haoxun Chen
Citations109
SJR quartileQ1
SJR score2.24
SNIP2.62
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 presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints, and a properly organized local search strategy and a diversification strategy are used to improve initial solutions.
Abstract
International audience
Keywords
Engineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
Society for Industrial and Applied Mathematics eBooksThe Vehicle Routing Problem
4,000 Citations2002Paolo Toth, Daniele Vigo
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.
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
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.
International Transactions in Operational ResearchClassical and modern heuristics for the vehicle routing problem
705 Citations2000G. Laporte, Michel Gendreau +2 more
This article is a survey of heuristics for the Vehicle Routing Problem which contains well-known schemes such as, the savings method, the sweep algorithm and various two-phase approaches and tabu search heuristic which have proved to be the most successful metaheuristic approach.
Transportation Research Part B MethodologicalA tabu search heuristic for the static multi-vehicle dial-a-ride problem
676 Citations2003Jean‐François Cordeau, Gilbert Laporte
A tabu search heuristic for the dial-a-ride problem with the following characteristics is described: users specify transportation requests between origins and destinations, and side constraints relate to vehicle capacity, route duration and the maximum ride time of any user.
European Journal of Operational ResearchThe pickup and delivery problem with time windows
641 Citations1991Yvan Dumas, Jacques Desrosiers +1 more
This paper presents an exact algorithm which solves the pickup and delivery problem when transporting goods using a column generation scheme with a constrained shortest path as a subproblem.
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.
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).
INFORMS Journal on ComputingThe Vehicle Routing Problem with Time Windows: Minimizing Route Duration
449 Citations1992Martin Savelsbergh
This work investigates the implementation of edge-exchange improvement methods for the vehicle routing problem with time windows with minimization of route duration as the objective and shows how this effort can be reduced to a constant.
Transportation Research Part B MethodologicalSolving the pickup and delivery problem with time windows using reactive tabu search
374 Citations2000William Paul Nanry, J. Wesley Barnes
A reactive tabu search approach is presented to solve the pickup and delivery problem with time windows using three distinct move neighborhoods that capitalize on the dominance of the precedence and coupling constraints.
Operations ResearchDrive: Dynamic Routing of Independent Vehicles
334 Citations1998Martin Savelsbergh, M Marc Sol
DRIVE (Dynamic Routing of Independent VEhicles), a planning module to be incorporated in a decision support system for the direct transportation at Van Gend and Loos BV, has produced very encouraging results.
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.
American Journal of Mathematical and Management SciencesA Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-A-Ride Problem with Time Windows
236 Citations1986Jacques Desrosiers, Yvan Dumas +1 more
The single-vehicle dial-a-ride problem with time window constraints for both pick-up and delivery locations, and precedence and capacity constraints, is solved using a forward dynamic programming algorithm.
Transportation ScienceSolving a Practical Pickup and Delivery Problem
224 Citations2003Hang Xu, Zhi-Long Chen +2 more
Column generation based solution approaches to a pickup and delivery vehicle routing problem commonly encountered in real-world logistics operations that involves a set of practical complications that have received little attention in the vehicle routing literature are proposed.
International series in management science/operations research/International series in operations research & management scienceGuided Local Search
212 Citations2010Christos Voudouris, Edward Tsang +1 more
This chapter describes the principles of Guided Local Search (GLS) and Fast Local Search and surveys their applications and provides guidance for implementing and using GLS and FLS.
Transportation ScienceHeuristic Algorithms for the Handicapped Persons Transportation Problem
209 Citations1997Paolo Toth, Daniele Vigo
A fast and effective parallel insertion heuristic algorithm which is able to determine good solutions for real-world instances of the problem in a few seconds on a personal computer is described.
Journal of HeuristicsSolving Vehicle Routing Problems Using Constraint Programming and Metaheuristics
178 Citations2000Bruno De Backer, Vincent Furnon +3 more
A method for using local search techniques within a Constraint Programming framework, and applies this technique to vehicle routing problems, and has coupled its local search method with a meta-heuristic to avoid the search being trapped in local minima.
Transportation ScienceA Request Clustering Algorithm for Door-to-Door Handicapped Transportation
154 Citations1995Irina Ioachim, Jacques Desrosiers +3 more
A new approximate method to mini-clustering that involves solving a multi-vehicle pick-up and delivery problem with time windows by column generation and a heuristic to reduce the size of the network, while incurring only small losses in solution quality is presented.
Computers & Operations ResearchComparing descent heuristics and metaheuristics for the vehicle routing problem
126 Citations2001Alex Van Breedam
A comparison of the best solution independent of computing times is fundamentally wrong because metaheuristics have no unambiguous stopping criteria, as opposed to traditional descent implementations.
European Journal of Operational ResearchA new extension of local search applied to the Dial-A-Ride Problem
104 Citations1995Patrick Healy, Robert N. Moll
A cheap yet effective extension to the traditional local improvement algorithm that yields significant improvements over its plain local improvement counterpart without adversely affecting the algorithm's running time is proposed.
Engineering Applications of Artificial IntelligenceArtificial intelligence heuristics in solving vehicle routing problems with time window constraints
98 Citations2001Kay Chen Tan, Loo Hay Lee +1 more
Different hybridizations of artificial intelligence based techniques including simulated annealing, tabu search and genetic algorithm are explored for better performance in VRPTW to near optimal solutions.
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.
Operations Research LettersEfficient feasibility testing for dial-a-ride problems
74 Citations2002Brady Hunsaker, Martin Savelsbergh
It is demonstrated that it is possible to efficiently determine, given a sequence of pickups and deliveries, whether a feasible schedule exists, and that this can be done in linear time.
Journal of HeuristicsA Heuristic for the Vehicle Routing Problem with Time Windows
61 Citations2001Roberto Cordone, Roberto Wolfler Calvo
A heuristic algorithm to solve the Vehicle Routing Problem with Time Windows is proposed, a smart combination of three simple procedures: the classical k-opt exchanges improve the solution, an ad hoc procedure reduces the number of vehicles and a second objective function drives the search out of local optima.
Calhoun: The Naval Postgraduate School Institutional Archive (Naval Postgraduate School)The Multi-Vehicle Subscriber Dial-A-Ride Problem
48 Citations1983Bodin, Lawrence D., Sexton, Thomas R.