The Dial-A-Ride Problem with Transfers
Computers & Operations ResearchPublished 30 July 2013Open access
Renaud Masson, Fabien Lehuédé, Olivier Péton
Citations174
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
A solution method based on an Adaptive Large Neighborhood Search (ALNS) metaheuristic is provided and how to check the feasibility of a request insertion is explained and experiments show that savings due to transfers can be up to 8% on real-life instances.
Abstract
International audience
Keywords
Engineering
Transportation ScienceAn Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows
2,392 Citations2006Stefan Røpke, David Pisinger
This paper presents a heuristic for the pickup and delivery problem based on an extension of the large neighborhood search heuristic previously suggested for solving the vehicle routing problem with time windows that is very robust and is able to adapt to various instance characteristics.
Artificial IntelligenceTemporal constraint networks
1,800 Citations1991Rina Dechter, Itay Meiri +1 more
It is shown that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time and the applicability of path consistency algorithms as preprocessing of temporal problems is studied, to demonstrate their termination and bound their complexities.
Computers & Operations ResearchA general heuristic for vehicle routing problems
1,394 Citations2005David Pisinger, Stefan Røpke
A unified heuristic which is able to solve five different variants of the vehicle routing problem and shown promising results for a large class of vehicle routing problems with backhauls as demonstrated in Ropke and Pisinger.
Lecture notes in computer scienceUsing Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
1,274 Citations1998Paul Shaw
This work uses a local search method that is analogous to the shuffling technique of job-shop scheduling, and so meshes well with constraint programming technology, to solve vehicle routing problems.
Annals of Operations ResearchThe dial-a-ride problem: models and algorithms
866 Citations2007Jean‐François Cordeau, Gilbert Laporte
The main features of the problem are described and a summary of the most important models and algorithms is provided.
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 ResearchDynamic pickup and delivery problems
659 Citations2009Gerardo Berbeglia, Jean‐François Cordeau +1 more
This article surveys the subclass of problems called dynamic pickup and delivery problems, in which objects or people have to be collected and delivered in real-time, and discusses some general issues as well as solution strategies.
Transportation ScienceSynchronization in Vehicle Routing—A Survey of VRPs with Multiple Synchronization Constraints
499 Citations2012Michael Drexl
A survey of vehicle routing problems with multiple synchronization constraints, which presents a classification of different types of synchronization and discusses the central issues related to the exact and heuristic solution of such problems.
European Journal of Operational ResearchA parallel route building algorithm for the vehicle routing and scheduling problem with time windows
416 Citations1993Jean‐Yves Potvin, Jean‐Marc Rousseau
This paper describes an insertion algorithm for the Vehicle Routing and Scheduling Problem with Time Windows that builds routes in parallel and uses a generalized regret measure over all unrouted customers to select the next candidate for insertion.
International series in management science/operations research/International series in operations research & management scienceLarge Neighborhood Search
383 Citations2018David Pisinger, Stefan Røpke
International series in management science/operations research/International series in operations research & management scienceLarge Neighborhood Search
314 Citations2010David Pisinger, Stefan Røpke
An overview of very large scale neighborhood search methods is given and recent variants and extensions like variable depth search and adaptive large neighborhood search are discussed.
NetworksModels and branch‐and‐cut algorithms for pickup and delivery problems with time windows
310 Citations2007Stefan Røpke, Jean‐François Cordeau +1 more
This paper introduces two new formulations for the PDPTW and the closely related dial‐a‐ride problem (DARP) in which a limit is imposed on the elapsed time between the pickup and the delivery of a request.
European Journal of Operational ResearchThe pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method
222 Citations2009Cristián E. Cortés, Martı́n Matamala +1 more
A strict formulation of a generalization of the classical pickup and delivery problem is presented, and it is concluded that there exist some configurations in which a scheme allowing transfers results in better quality optimal solutions.
Computers & Operations ResearchVariable neighborhood search for the dial-a-ride problem
209 Citations2009Sophie N. Parragh, Karl F. Doerner +1 more
This paper proposes a competitive variable neighborhood search-based heuristic, using three classes of neighborhoods, based on the ejection chain idea, which exploits the existence of arcs where the vehicle load is zero, giving rise to natural sequences of requests.
Transportation ScienceAn Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers
208 Citations2012Renaud Masson, Fabien Lehuédé +1 more
This paper addresses a variant of the PDP where requests can change vehicle during their trip and proposes new heuristics capable of efficiently inserting requests through transfer points embedded into an Adaptive Large Neighborhood Search.
Journal of the ACMDeciding Linear Inequalities by Computing Loop Residues
182 Citations1981Robert E. Shostak
V R Pratt has shown that the real and integer feastbdlty of sets of linear mequallUes of the form x _< y + c can be decided quickly by examining the loops of certain graphs.
Transportation ScienceScheduling Dial-a-Ride Transportation Systems
156 Citations1978David M. Stein
An analytic investigation into the fundamental aspects of scheduling “Dial-a-Ride” transportation systems is conducted and a class of algorithms is derived for which performance can be measured in a precise asymptotic probabilistic sense.
Computers & Operations ResearchHybrid column generation and large neighborhood search for the dial-a-ride problem
134 Citations2012Sophie N. Parragh, Verena Schmid
A hybrid column generation and large neighborhood search algorithm is proposed and different hybridization strategies are compared on a set of benchmark instances from the literature.
INFOR Information Systems and Operational ResearchThe Pickup And Delivery Problem With Time Windows And Transshipment
122 Citations2006Snežana Mitrović-Minić, Gilbert Laporte
An empirical study on usefulness of transshipment points in such a conlexl, allowing vehicles to move through entire service area in order to evaluate the usefulness ofTransshipment, identifying circumstances under which transshipments may be beneficial.
Computers & Industrial EngineeringQuality of service in dial-a-ride operations
116 Citations2008Julie Paquette, Jean‐François Cordeau +1 more
The dimensions and attributes of various scales of measurement used by researchers in dial-a-ride studies are reviewed and the impact on quality of various elements, like the size and type of organization and the operational rules used, are discussed.
European Journal of Operational ResearchSolving a school bus scheduling problem with integer programming
106 Citations2007Armin Fügenschuh
An integer programming model for the integrated coordination of the school starting times and the public bus services is presented and it is shown that in test counties a much lower number of buses would be sufficient if the schools start at different times.
Computers & Operations ResearchA GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment
98 Citations2011Yuan Qu, Jonathan F. Bard
The circumstances under which measurable cost saving can be achieved when one aircraft transports a request from its origin to an intermediate point and a second aircraft picks it up and delivers it to its final destination are identified.
Lecture notes in computer sciencePrinciples and Practice of Constraint Programming – CP 2011
94 Citations2011Lee, Jimmy, CP 2011 Perugia
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.
Transportation Research Record Journal of the Transportation Research BoardDesign and Operational Concepts of High-Coverage Point-to-Point Transit System
72 Citations2002Cristián E. Cortés, R. Jayakrishnan
Preliminary simulations show that under a variety of acceptable demand levels, the system can operate with high cost-effectiveness, and the design proposed is effectively geared toward a decomposed solution using detailed rules that achieve vehicle selection and route planning.
Computers & Industrial EngineeringMulticriteria pickup and delivery problem with transfer opportunity
66 Citations1996Jen S. Shang, Carolyn K. Cuff
A concurrent scheduling approach, which allocates customers to more than one vehicle and assigns more thanOne customer to a vehicle at a time is proposed, which is a one-phase heuristic that can be reiterated when necessary.
Central European Journal of Operations ResearchReal-time split-delivery pickup and delivery time window problems with transfers
44 Citations2007Sam R. Thangiah, Adel Fergany +1 more
The design and implementation of heuristics for solving split-delivery pickup and delivery time window problems with transfer (SDPDTWP) of shipments between vehicles for both static and real-time data sets are presented.
Operations Research LettersAnalysis of the dial-a-ride problem of Hunsaker and Savelsbergh
41 Citations2010Murat Fırat, Gerhard J. Woeginger
It is shown that this feasibility test for a dial-a-ride problem under maximum wait time and maximum ride time constraints can be expressed as a shortest path problem in vertex-weighted interval graphs, which leads to a simple linear time algorithm.
HAL (Le Centre pour la Communication Scientifique Directe)Proceedings of the International Conference on Industrial Engineering and Systems Management
36 Citations2015José M. Framiñán, Paz Pérez-González +1 more
Lecture notes in computer scienceThe Pickup and Delivery Problem with Cross-Docking Opportunity
35 Citations2011Hanne Løhmann Petersen, Stefan Røpke
This paper considers the pickup and delivery problem with cross-docking opportunity (PDPCD) from an industry application, and solves the problem using a Large Neighborhood Search (LNS) approach.
Transshipment and Time Windows in Vehicle Routing
35 Citations2006Christopher Mues, Stefan Pickl
Two approaches are developed for merged problems of transshipment problems and vehicle routing problems with time windows as a generalization of the VRPTW.
Lecture notes in computer scienceLarge Neighborhood Search for Dial-a-Ride Problems
33 Citations2011Siddhartha Jain, Pascal Van Hentenryck
Experimental evidence shows that the approach is competitive in finding best-known solutions and reaches high-quality solutions significantly faster than the state of the art.
European J of Industrial EngineeringThe splittable pickup and delivery problem with reloads
32 Citations2008Hervé Kerivin, Mathieu Lacroix +2 more
Lecture notes in computer scienceFeasibility Testing for Dial-a-Ride Problems
23 Citations2010Dag Haugland, Sin C. Ho
This work shows that the proposed algorithm for testing feasibility of a route in the solution to the dial-a-ride problem is incorrect and proves that by increasing the time complexity by only a logarithmic factor, a correct algorithm is obtained.
Lecture notes in computer scienceMinimum Makespan Multi-vehicle Dial-a-Ride
20 Citations2009Inge Li Gørtz, Viswanath Nagarajan +1 more
ACM Journal of Experimental AlgorithmicsShortest-path feasibility algorithms
19 Citations2009Boris V. Cherkassky, Loukas Georgiadis +3 more
This is an experimental study of algorithms for the shortest-path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists.
IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesWorst Case Analysis for Pickup and Delivery Problems with Transfer
16 Citations2008Yoshiaki Nakao, Hiroshi Nagamochi
The maximum travel cost that can be saved by introducing a transshipment point to the pickup and delivery problem (PDP) is analyzed and it is shown that the bounds are in proportion to square root of the number of cycles in an optimal PDPT solution and alsosquare root ofThe number of requests.
HAL (Le Centre pour la Communication Scientifique Directe)A tabu search algorithm for the Dial-a-Ride Problem with Transfers
8 Citations2011Renaud Masson, Fabien Lehuédé +1 more
A tabu search algorithm for the Dial-a-Ride Problem with Transfers (DARPT) with a special emphasis on checking whether a modication of the current solution is feasible or not is proposed.
Lecture notes in computer scienceSimple Temporal Problems in Route Scheduling for the Dial–a–Ride Problem with Transfers
7 Citations2012Renaud Masson, Fabien Lehuédé +1 more
This paper addresses a variant of the DARP where requests can change of vehicle during their trip, and proposes necessary and sufficient conditions to fasten the detection of unfeasible or feasible routes.