A column generation and Combinatorial Benders Decomposition algorithm for the Selective Dial-A-Ride-Problem
In Pickup-and-Delivery Problems (PDP), a set of vehicle routes that visit matching pickup and delivery locations must be designed. The Selective Dial-A-Ride Problem (SDARP) is a PDP which aims to serve as many pickup–delivery pairs as possible, where each pair has a time window and a maximum ride time. This paper introduces Extended Fragments to solve the SDARP. Extended Fragments stem from a subclass of vehicle routes which can be directly enumerated. An Extended Fragment formulation for the SDARP is proposed and solved using Combinatorial Benders Decomposition, augmented by a time discretisation and a novel variable-fixing technique. This algorithm, along with other recent ‘fragment’-based methods for PDP, is an a priori column generation method, combined with Combinatorial Benders Decomposition. The new method solves the existing benchmark for the SDARP, including 11 previously-unsolved instances.
- Record URL:
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/oclc/1793974
-
Supplemental Notes:
- © 2021 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
-
Authors:
- Rist, Yannik
-
0000-0001-7589-4705
- Forbes, Michael
-
0000-0002-2240-7245
- Publication Date: 2022-4
Language
- English
Media Info
- Media Type: Web
- Features: Figures; References; Tables;
- Pagination: 105649
-
Serial:
- Computers & Operations Research
- Volume: 140
- Issue Number: 0
- Publisher: Elsevier
- ISSN: 0305-0548
- Serial URL: https://www.sciencedirect.com/journal/computers-and-operations-research
Subject/Index Terms
- TRT Terms: Demand responsive transportation; Pickup and delivery service; Planning methods; Routing
- Subject Areas: Freight Transportation; Highways; Operations and Traffic Management;
Filing Info
- Accession Number: 01850136
- Record Type: Publication
- Files: TRIS
- Created Date: Jun 27 2022 5:16PM