DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.17

Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities

Authors: Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract

When a transportation service accommodates both people and goods, operators sometimes opt for vehicles that can be dynamically reconfigured for different demands. Motivated by air service in remote communities in Canada’s north, we define a pickup-and-delivery problem in which aircraft can add or remove seats during a multi-stop trip to accommodate varying demands. Given the demand for people and cargo as well as a seat inventory at each location, the problem consists in finding a tour that picks up and delivers all demand while potentially reconfiguring the vehicle capacity at each location by adding or removing seats. We develop a total of six models using three different approaches: constraint programming, mixed integer programming, and domain-independent dynamic programming. Our numerical experiments indicate that domain-independent dynamic programming is able to substantially outperform the other technologies on both solution quality and run-time on a set of randomly generated instances spanning the size of real problems in northern Canada.

Cite as

Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck. Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{golestanian_et_al:LIPIcs.CP.2023.17,
  author =	{Golestanian, Arnoosh and Bianco, Giovanni Lo and Tao, Chengyu and Beck, J. Christopher},
  title =	{{Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.17},
  URN =		{urn:nbn:de:0030-drops-190542},
  doi =		{10.4230/LIPIcs.CP.2023.17},
  annote =	{Keywords: Pickup and delivery, Dial-a-ride problem, Optimization}
}

Search Results

Documents authored by Tao, Chengyu

Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities

Abstract

Cite as

Thanks for your feedback!

Could not send message