Abstract
In this paper, we deal with the Pickup and Delivery Problem with Transfers, and focus on the way a new request can be inserted into a current solution. This problem may be viewed as the search for a specific collection of constraints related to the nodes of a Time Expanded Network. It has most often been addressed in a very empirical way, and our goal here is to formalize it and handle it in an exact way through an adaptation of the A* algorithm that involves constraint propagation. We also present an empirical Dijkstra algorithm that computes tentative solutions whose consistence is then checked through constraint propagation. We conclude by comparing the behavior and performance of those algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Figueroa JL, Quilliot A, Toussaint H, Wagler A. Optimal 1-Request Insertion for the Pickup and Delivery Problem with Transfers and Time Horizon. Paper presented at the 11th International Conference on Operations Research and Enterprise Systems (ICORES), 3–5 February 2022.
Gouveia L, Leitner M, Ruthmair M. Layered graph approaches for combinatorial optimization problems. Comput Oper Res. 2019;102:22–38.
Bsaybes S, Quilliot A, Wagler AK. Fleet management for autonomous vehicles using flows in time-expanded networks. TOP. 2019;27:288–311.
Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G. Static pickup and delivery problems: a classification scheme and survey. TOP. 2007;15(2):1–31.
Parragh S, Doerner K, Hartl R. A survey on pickup and delivery problems: part II: transportation between pickup and delivery locations. Journal für Betriebswirtschaft. 2008;58:81–117.
Berbeglia G, Cordeau J-F, Laporte G. Dynamic pickup and delivery problems. Eur J Oper Res. 2010;202(1):8–15.
Toth P, Vigo D. Vehicle Routing. Philadelphia: Society for Industrial and Applied Mathematics; 2014.
Laporte G, Mitrović-Minić S. The pickup and delivery problem with time windows and transshipment. INFOR. 2006;44(3):217–27.
Thangiah S, Fergany A, Awan S. Real-time split-delivery pickup and delivery time window problems with transfers. Cent Eur J Oper Res. 2007;15:329–49.
Contardo C, Cortès C, Matamala M. The pickup and delivery problem with transfers: formulation and a branch-and-cut solution method. Eur J Oper Res. 2010;200(2):711–24.
Bouros P, Sacharidis D, Dalamagas T, Sellis T. Dynamic pickup and delivery with transfers. In: Pfoser D, Tao Y, Mouratidis K, Nascimento MA, Mokbel M, Shekhar S, Huang Y, editors. Advances in spatial and temporal databases. Berlin: Springer; 2011. p. 112–29.
Ho SC, Kuo Y-H, Leung JMY, Petering M, Szeto WY, Tou TWH. A survey of dial-a-ride problems: literature review and recent developments. Transport Res Part B. 2018;111:395–421.
Masson R, Lehuédé F, Péton O. A tabu search algorithm for the dial-a-ride problem with transfers. Proceedings of the IESM 2011 Conference 2011.
Masson R, Lehuédé F, Péton O. The dial-a-ride problem with transfers. Comput Oper Res. 2014;41:12–23.
Deleplanque S, Quilliot A. Dial-a-ride problem with time windows, transshipments, and dynamic transfer points. IFAC Proc Volumes. 2013;46(9):1256–61 (7th IFAC Conference on Manufacturing Modelling, Management, and Control).
Lehuédé F, Masson R, Péton O. Efficient feasibility testing for request insertion in the pickup and delivery problem with transfers. Oper Res Lett. 2013;41(3):211–5.
Reinhardt LB, Clausen T, Pisinger D. Synchronized dial-a-ride transportation of disabled passengers at airports. Eur J Oper Res. 2013;225(1):106–17.
Schönberger J. Scheduling constraints in dial-a-ride problems with transfers: a metaheuristic approach incorporating a cross-route scheduling procedure with postponement opportunities. Public Transp. 2017;9:243–72.
Xue G. A two-stage heuristic solution for multi-depot collaborative pickup and delivery network with transfers to reduce carbon emissions. J Clean Prod. 2022;373: 133839.
Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern SSC. 1968;4(2):100–7.
Acknowledgements
Part of this work has been carried out in the context of the H2020 Marie Skłodowska-Curie Research and Innovation Staff Exchange European project 691161 “GEO-SAFE”.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
On behalf of all authors, the corresponding author states that there is no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article is part of the topical collection “Advances on Operations Research and Enterprise Systems” guest edited by Marc Demange, Federico Liberatore and Greg H. Parlier.
This is an extension of the work presented in [1]; we follow similar guidelines, but we also present a more generic framework to extend our models and algorithms for handling an insertion problem involving a more general cost function. We also provide arguments about the complexity of the algorithms described, and an analysis of the results obtained from computational experiments.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Figueroa, JL., Quilliot, A., Toussaint, H. et al. Optimal Paths with Impact on a Constraint System: An Application to the 1-Request Insertion for the Pickup and Delivery Problem with Transfers. SN COMPUT. SCI. 4, 79 (2023). https://doi.org/10.1007/s42979-022-01486-2
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s42979-022-01486-2