{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,31]],"date-time":"2026-08-31T15:00:50Z","timestamp":1788188450307,"version":"build-2803163510"},"reference-count":16,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,8,3]],"date-time":"2019-08-03T00:00:00Z","timestamp":1564790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the vehicle routing problem with simultaneous pickup and delivery (VRPSPD), customers demanding both delivery and pickup operations have to be visited once by a single vehicle. In this work, we propose a fast randomized algorithm using a nearest neighbor strategy to tackle an extension of the VRPSPD in which the fleet of vehicles is heterogeneous. This variant is an NP-hard problem, which in practice makes it impossible to be solved to proven optimality for large instances. To evaluate the proposal, we use benchmark instances from the literature and compare our results to those obtained by a state-of-the-art algorithm. Our approach presents very competitive results, not only improving several of the known solutions, but also running in a shorter time.<\/jats:p>","DOI":"10.3390\/a12080158","type":"journal-article","created":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T03:25:22Z","timestamp":1564975522000},"page":"158","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Fast Randomized Algorithm for the Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0734-4688","authenticated-orcid":false,"given":"Napole\u00e3o","family":"Nepomuceno","sequence":"first","affiliation":[{"name":"Graduate Program in Applied Informatics, University of Fortaleza, 60811-905 Fortaleza, Cear\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8666-2712","authenticated-orcid":false,"given":"Ricardo","family":"Barboza Saboia","sequence":"additional","affiliation":[{"name":"Graduate Program in Applied Informatics, University of Fortaleza, 60811-905 Fortaleza, Cear\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1718-1712","authenticated-orcid":false,"given":"Pl\u00e1cido","family":"Rog\u00e9rio Pinheiro","sequence":"additional","affiliation":[{"name":"Graduate Program in Applied Informatics, University of Fortaleza, 60811-905 Fortaleza, Cear\u00e1, Brazil"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.cor.2004.07.009","article-title":"A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service","volume":"33","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1693","DOI":"10.1016\/j.cor.2008.04.003","article-title":"A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery","volume":"36","author":"Ai","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3215","DOI":"10.1016\/j.cor.2009.02.017","article-title":"An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup","volume":"36","author":"Gajpal","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1899","DOI":"10.1016\/j.cor.2009.10.011","article-title":"A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery","volume":"37","author":"Subramanian","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6809","DOI":"10.1016\/j.eswa.2010.03.045","article-title":"A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery","volume":"37","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1016\/j.orl.2011.06.012","article-title":"Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery","volume":"39","author":"Subramanian","year":"2011","journal-title":"Oper. Res. Lett."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.cie.2012.01.005","article-title":"A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery","volume":"65","author":"Goksal","year":"2013","journal-title":"Comput. Ind. Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.cie.2015.02.002","article-title":"An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries","volume":"83","author":"Avci","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.eswa.2016.09.017","article-title":"An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery","volume":"66","author":"Kalayci","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_10","unstructured":"Kececi, B., Altiparmak, F., and Kara, I. (2014, January 14\u201316). The heterogeneous vehicle routing problem with simultaneous pickup and delivery: A hybrid heuristic approach based on simulated annealing. Proceedings of the CIE 2014\u201444th International Conference on Computers and Industrial Engineering, Istanbul, Turkey."},{"key":"ref_11","first-page":"183","article-title":"A heuristic algorithm for vehicle routing problem with heterogeneous fleet, simultaneous pickup and delivery","volume":"35","author":"Tian","year":"2015","journal-title":"Syst. Eng. Theory Pract."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Chicano, F., Hu, B., and Garc\u00eda-S\u00e1nchez, P. (2016). A Hybrid Constructive Mat-heuristic Algorithm for the Heterogeneous Vehicle Routing Problem with Simultaneous Pick-up and Delivery. Evolutionary Computation in Combinatorial Optimization, Springer International Publishing.","DOI":"10.1007\/978-3-319-30698-8"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/j.eswa.2016.01.038","article-title":"A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery","volume":"53","author":"Avci","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons.","DOI":"10.2307\/2582681"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0166-218X(01)00195-0","article-title":"Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP","volume":"117","author":"Gutin","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.disopt.2004.03.007","article-title":"When the greedy algorithm fails","volume":"1","author":"Gutin","year":"2004","journal-title":"Discret. Optim."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/158\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:13:09Z","timestamp":1760188389000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/158"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,3]]},"references-count":16,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080158"],"URL":"https:\/\/doi.org\/10.3390\/a12080158","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,3]]}}}