The splittable pickup and delivery problem with reloads
European J of Industrial EngineeringPublished 1 January 2008
Hervé Kerivin, Mathieu Lacroix, Ali Ridha Mahjoub, Alain Quilliot
Citations32
SJR quartileQ2
SJR score0.39
SNIP0.50
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.
Abstract
In this paper, we consider a variant of the Pickup and Delivery Problem (PDP), where any demand may be dropped off elsewhere other than its destination, picked up later by the same or another vehicle, and so on until it has reached its destination. We discuss the complexity of this problem and present two mixed-integer linear programming formulations based on a space-time graph. We describe some valid inequalities for the problem along with separation routines. Based on these results, we develop a branch-and-cut algorithm for the problem, and present some computational results. [Received 31 January 2007; Revised 08 August 2007; Accepted 02 October 2007]
Keywords
Engineering
Management ScienceThe Truck Dispatching Problem
4,873 Citations1959George B. Dantzig, J. H. Ramser
A procedure based on a linear programming formulation is given for obtaining a near optimal solution to the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal.
Algorithms and combinatoricsGeometric Algorithms and Combinatorial Optimization
3,487 Citations1988Martin Grötschel, László Lovász +1 more
This paper presents a meta-modelling framework for estimating the running time of Oracle Algorithms, and some examples show how this framework can be modified for more efficient and scalable solutions to NP-Completeness problems.
INFORMS Journal on ComputingTSPLIB—A Traveling Salesman Problem Library
2,570 Citations1991Gerhard Reinelt
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties.
Transportation ScienceThe General Pickup and Delivery Problem
1,034 Citations1995Martin Savelsbergh, María Sol
Several characteristics that distinguish pickup and delivery problems from standard vehicle routing problems are discussed and a survey of the problem types and solution methods found in the literature is presented.
GPS: Theory, Algorithms and Applications
376 Citations2003Guochang Xu, Yan Xu
This reference and handbook describes theory, algorithms and applications of the Global Positioning System (GPS/Glonass/Galileo/Compass) based on source-code descriptions of the KSGsoft program developed at the GFZ in Potsdam.
IBM Journal of Research and DevelopmentThe Common Optimization INterface for Operations Research: Promoting open-source software in the operations research community
374 Citations2003Robin Lougee-Heimer
The Common Optimization INterface for Operations Research, an initiative to promote open-source software for the operations research community, is reviewed, and the goals and status of COIN-OR are presented.
Repository Technological University of Pereira (Technological University of Pereira)Construcción de aplicativo web para la gestión y prestación del servicio de ambulancias en la ciudad de Pereira, utilizando inteligencia artificial
351 Citations2021H. A. Eiselt, Michel Gendreau
Mathematical ProgrammingA recursive procedure to generate all cuts for 0–1 mixed integer programs
190 Citations1990George L. Nemhauser, Laurence A. Wolsey
It is shown how all valid inequalities for mixed 0–1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.
Mathematical ProgrammingMinimum cost capacity installation for multicommodity network flows
177 Citations1998Daniel Bienstock, Sunil Chopra +2 more
This paper considers the problem of minimum cost installation of capacity on the arcs to ensure that the required demands can be shipped simultaneously between node pairs and describes two classes of strong valid inequalities.
Mathematical ProgrammingThe convex hull of two core capacitated network design problems
150 Citations1993Thomas L. Magnanti, Prakash Mirchandani +1 more
This paper studies two core subproblems of the NLP: a three node network and a multiple commodity, single arc capacitated network design problem; in both cases, families of facets are developed and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems.
SIAM Journal on OptimizationNetwork Design Using Cut Inequalities
146 Citations1996Francisco Barahona
The network loading problem, with and without bifurcations, is studied, and a relaxation based on the cut condition for multicommodity flows is used, which results in feasible solutions and bounds for the gap from optimality.
IEEE Transactions on Circuit TheoryOn feasibility conditions of multicommodity flows in networks
126 Citations1971Kenji Onaga, Osamu Kakusho
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.
Operations Research LettersExact solution of multicommodity network optimization problems with general step cost functions
112 Citations1999Virginie Gabrel, Arnaud Knippel +1 more
The proposed procedure may be viewed as a specialization of the well-known BENDERS partitioning procedure, leading to iteratively solving an integer 0-1 linear programming relaxed subproblem which is progressively augmented through constraint generation.
European Journal of Operational ResearchPlanning models for long-haul operations of postal and express shipment companies
102 Citations2000Tore Grünert, Hans‐Jürgen Sebastian
Important planning tasks which have to be addressed at postal and express shipment companies are identified and corresponding optimization models are defined.
Mathematical ProgrammingOn splittable and unsplittable flow capacitated network design arc-set polyhedra
90 Citations2002Alper Atamtürk, Deepak Rajan
Kölner Universitäts PublikationsServer (Universität zu Köln)Routing with Reloads
17 Citations2001Peter Oertel