A Branch-and-Cut Algorithm for the Dial-a-Ride Problem

By Jean-François Cordeau. Operational Research, 2006

744 citations recorded by the source corpus.

Subfields: Automotive Engineering, Building and Construction, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/12bcd428a4d47a9f3c775d84e9d73033740f8bd6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Building and Construction

In Industrial and Manufacturing Engineering

Citations in the corpus

T-share: A large-scale dynamic taxi ridesharing service (2013, background): “Since the general DARP is NP-hard [15], only small instances (involving only a few cars and dozens of queries) can be solved optimally (often by resorting to integer programming techniques, see [9][17]).”
Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care (2013, neutral): “…et al., 1991) (M. Savelsbergh and Sol, 1998) (Xu, et al., 2003) (Sigurd and Pisinger, 2004) used branch and price schemes for the PDPTW. ( J.-F. Cordeau, 2006) (Ropke, et al., 2007) developed branch and cut approach for the PDPTW. (Ropke and Cordeau, 2009) introduced a new branch and cut and…”
Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows (2007, positive): “More recently, Cordeau [6] has developed a branch-and-cut algorithm for the DARP, based on a three-index formulation with a polynomial number of constraints.”
The dial-a-ride problem: models and algorithms (2006, methodology): “ Cordeau (2006) formulates the DARP on a directed graph G = (V , A) .T he vertex setV is partitioned into {{0, 2n + 1} ,P,D } where 0 and 2n + 1 are two copies of the depot, P ={ 1 ,...,n } is the set of pickup vertices and D ={ n + 1 ,..., 2n} is the set of delivery vertices.”
Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on State-space-time Network Representations (2015, methodology): “The constructed networks are able to conveniently represent the complex pickup and delivery time windows without adding the extra constraints typically needed for the classical PDPTW formulation (e.g. Cordeau, 2006).”
Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows (2009, methodology): “If k 1 = i and k ρ = n + i for some i ∈ P and the path is infeasible because of time windows then Cordeau (2006) has observed that the inequality can be strengthened to”