2007/03/07 by Stefan Ropke, Stefan Røpke, Jean‐François Cordeau +1 · 1 citation
Computer Science · Engineering · #Robotic Path Planning Algorithms #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · doi:10.1002/net.20177
crossref issued 2007/03/07 · crossref published 2007/03/07 · crossref published-online 2007/03/07 · openalex publication_date 2007/03/07 · crossref created 2007/03/07 · crossref published-print 2007/07/01 · crossref deposited 2023/11/15 · openalex created_date 2025/10/10 · crossref indexed 2026/07/31 · openalex updated_date 2026/08/01
Abstract In the pickup and delivery problem with time windows (PDPTW), capacitated vehicles must be routed to satisfy a set of transportation requests between given origins and destinations. In addition to capacity and time window constraints, vehicle routes must also satisfy pairing and precedence constraints on pickups and deliveries. 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. Several families of valid inequalities are introduced to strengthen these two formulations. These inequalities are used within branch‐and‐cut algorithms which have been tested on several instance sets for both the PDPTW and the DARP. Instances with up to eight vehicles and 96 requests (194 nodes) have been solved to optimality. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 258–272 2007