Path and Speed Optimization for Conflict-Free Pickup and Delivery Under Time Windows

Tommaso Adamo (), Tolga Bektaş (), Gianpaolo Ghiani (), Emanuela Guerriero () and Emanuele Manni ()
Additional contact information
Tommaso Adamo: Department of Engineering for Innovation, Università del Salento, 73100 Lecce, Italy
Tolga Bektaş: Centre for Operational Research, Management Science and Information Systems, Southampton Business School, University of Southampton, Southampton, Highfield SO17 1BJ, United Kingdom
Gianpaolo Ghiani: Department of Engineering for Innovation, Università del Salento, 73100 Lecce, Italy
Emanuela Guerriero: Department of Engineering for Innovation, Università del Salento, 73100 Lecce, Italy
Emanuele Manni: Department of Engineering for Innovation, Università del Salento, 73100 Lecce, Italy

Transportation Science, 2018, vol. 52, issue 4, 739-755

Abstract: This article introduces a variant of the conflict-free pickup and delivery problem with time windows in which speeds can be regulated. The problem arises in several areas of transportation and logistics including routing and scheduling of automated guided vehicles in port terminals and coordination of unmanned aerial vehicles in controlled airspace. A particular aspect of this problem is that at most one vehicle can traverse an arc of the transportation network at any time. The problem studied in this paper is to determine the vehicle paths and speeds on each arc of the path in such a way that no conflicts arise, the time windows are met, and the total energy consumption is minimized. A branch-and-bound algorithm is described in which a lower bound is obtained by solving a separable nonlinear problem in quadratic time. If the solution of the relaxation is not conflict free, a set of space-based and time-based branching constraints are generated to resolve the detected conflicts. Computational experiments show that, when compared with a state-of-the-art approach, the proposed method is able to generate a larger number of feasible solutions (42% on average) and reduce the computation time by an order of magnitude. Moreover, the approach results in an average energy savings of around 70%.

Keywords: pickup and delivery; speed optimization; conflict-free routing (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0816 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:52:y:2018:i:4:p:739-755

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().