{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T09:45:38Z","timestamp":1786441538959,"version":"3.56.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008769","name":"Julius-Maximilians-Universit\u00e4t W\u00fcrzburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Intell"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the last decades, the classical Vehicle Routing Problem\u00a0(VRP), i.e., assigning a set of orders to vehicles and planning their routes has been intensively researched. As only the assignment of order to vehicles and their routes is already an NP-complete problem, the application of these algorithms in practice often fails to take into account the constraints and restrictions that apply in real-world applications, the so called rich VRP\u00a0(rVRP) and are limited to single aspects. In this work, we incorporate the main relevant real-world constraints and requirements. We propose a two-stage strategy and a Timeline algorithm for time windows and pause times, and apply a Genetic Algorithm\u00a0(GA) and Ant Colony Optimization\u00a0(ACO) individually to the problem to find optimal solutions. Our evaluation of eight different problem instances against four state-of-the-art algorithms shows that our approach handles all given constraints in a reasonable time.<\/jats:p>","DOI":"10.1007\/s10489-021-03035-5","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T21:11:51Z","timestamp":1641503511000},"page":"9476-9500","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Tackling the rich vehicle routing problem with nature-inspired algorithms"],"prefix":"10.1007","volume":"52","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7481-4099","authenticated-orcid":false,"given":"Veronika","family":"Lesch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilian","family":"K\u00f6nig","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9742-2063","authenticated-orcid":false,"given":"Samuel","family":"Kounev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1808-9758","authenticated-orcid":false,"given":"Anthony","family":"Stein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7275-0738","authenticated-orcid":false,"given":"Christian","family":"Krupitzer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"key":"3035_CR1","unstructured":"Transportleistung im Stra\u00dfeng\u00fcterverkehr 2019 $$\\vert$$ Statista (2021) https:\/\/de.statista.com\/statistik\/daten\/studie\/2979\/umfrage\/entwicklung-der-transportleistung-des-strassengueterverkehrs. [Online; acc. 3. Feb. 2021]"},{"key":"3035_CR2","doi-asserted-by":"publisher","first-page":"100802","DOI":"10.1016\/j.swevo.2020.100802","volume":"60","author":"M Alinaghian","year":"2021","unstructured":"Alinaghian M, Tirkolaee EB, Dezaki ZK, Hejazi SR, Ding W (2021) An augmented tabu search algorithm for the green inventory-routing problem with time windows. Swarm and Evolutionary Computation 60:100802. https:\/\/doi.org\/10.1016\/j.swevo.2020.100802","journal-title":"Swarm and Evolutionary Computation"},{"issue":"1-suppl","key":"3035_CR3","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1177\/0734242X18807001","volume":"37","author":"E Babaee Tirkolaee","year":"2019","unstructured":"Babaee Tirkolaee E, Abbasian P, Soltani M, Ghaffarian SA (2019) Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study. Waste Management & Research 37(1-suppl):4\u201313","journal-title":"Waste Management & Research"},{"issue":"11","key":"3035_CR4","doi-asserted-by":"publisher","first-page":"1089","DOI":"10.1177\/0734242X19865340","volume":"37","author":"E Babaee Tirkolaee","year":"2019","unstructured":"Babaee Tirkolaee E, Goli A, Pahlevan M, Malekalipour Kordestanizadeh R (2019) A robust bi-objective multi-trip periodic capacitated arc routing problem for urban waste collection using a multi-objective invasive weed optimization. Waste Management & Research 37(11):1089\u20131101","journal-title":"Waste Management & Research"},{"key":"3035_CR5","doi-asserted-by":"publisher","unstructured":"Barma PS, Dutta J, Mukherjee A, Kar S (2021) A multi-objective ring star vehicle routing problem for perishable items. J Ambient Intell Humaniz Comput 1\u201326. https:\/\/doi.org\/10.1007\/s12652-021-03059-2","DOI":"10.1007\/s12652-021-03059-2"},{"key":"3035_CR6","first-page":"219","volume-title":"Ant Colony Optimization and Its Application to the Vehicle Routing Problem with Pickups and Deliveries","author":"B \u00c7atay","year":"2009","unstructured":"\u00c7atay B (2009) Ant Colony Optimization and Its Application to the Vehicle Routing Problem with Pickups and Deliveries. Springer, Berlin, pp 219\u2013244"},{"issue":"1","key":"3035_CR7","doi-asserted-by":"publisher","first-page":"14656","DOI":"10.1016\/j.ifacol.2017.08.1906","volume":"50","author":"ZA Chami","year":"2017","unstructured":"Chami ZA, Manier H, Manier MA, Fitouri C (2017) A hybrid genetic algorithm to solve a multi-objective Pickup and Delivery Problem. IFAC-PapersOnLine 50(1):14656\u201314661 (20th IFAC World Congress)","journal-title":"IFAC-PapersOnLine"},{"key":"3035_CR8","doi-asserted-by":"crossref","unstructured":"Ch\u00e1vez JJS, Escobar JW, Echeverri MG (2016) A multi-objective Pareto ant colony algorithm for the Multi-Depot Vehicle Routing problem with Backhauls. Int J Ind Eng Comput 7:35\u201348","DOI":"10.5267\/j.ijiec.2015.8.003"},{"key":"3035_CR9","first-page":"761","volume":"8","author":"CH Chen","year":"2010","unstructured":"Chen CH, Ting CJ (2010) Applying two-stage ant colony optimization to solve the large scale vehicle routing problem. Journal of the Eastern Asia Society for Transportation Studies 8:761\u2013776","journal-title":"Journal of the Eastern Asia Society for Transportation Studies"},{"issue":"4","key":"3035_CR10","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1287\/opre.12.4.568","volume":"12","author":"G Clarke","year":"1964","unstructured":"Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Operations research 12(4):568\u2013581","journal-title":"Operations research"},{"key":"3035_CR11","doi-asserted-by":"crossref","unstructured":"Cordeau JF, Laporte G, Savelsbergh MW, Vigo D (2007) Chapter $$6$$ vehicle routing. In: Transportation, handbooks in operations research and management science, vol 14. Elsevier, pp 367 \u2013 428","DOI":"10.1016\/S0927-0507(06)14006-2"},{"issue":"4","key":"3035_CR12","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/opre.2.4.393","volume":"2","author":"G Dantzig","year":"1954","unstructured":"Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America 2(4):393\u2013410","journal-title":"Journal of the operations research society of America"},{"key":"3035_CR13","doi-asserted-by":"crossref","unstructured":"Desaulniers G, Desrosiers J, Erdmann A, Solomon MM, Soumis F (2002) 9. VRP with pickup and delivery. In: The vehicle routing problem, pp 225\u2013242, Society for Industrial and Applied Mathematics","DOI":"10.1137\/1.9780898718515.ch9"},{"key":"3035_CR14","unstructured":"Doerner K, Hartl RF, Reimann M (2000) Ant colony optimization applied to the pickup and delivery problem. Working papers SFB \u201cAdaptive Information Systems and Modelling in Economics and Management Science\u201d 76, Vienna"},{"issue":"1","key":"3035_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/3477.484436","volume":"26","author":"M Dorigo","year":"1996","unstructured":"Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 26(1):29\u201341","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)"},{"issue":"17","key":"3035_CR16","doi-asserted-by":"publisher","first-page":"13953","DOI":"10.1007\/s00521-020-04798-7","volume":"32","author":"J Dutta","year":"2020","unstructured":"Dutta J, Barma PS, Mukherjee A, Kar S, De T (2020) A multi-objective open set orienteering problem. Neural Computing and Applications 32(17):13953\u201313969","journal-title":"Neural Computing and Applications"},{"issue":"4","key":"3035_CR17","doi-asserted-by":"publisher","first-page":"417","DOI":"10.3934\/naco.2017026","volume":"7","author":"MBIM Erfan Babae Tirkolaee Alireza Goli","year":"2017","unstructured":"Erfan Babae Tirkolaee Alireza Goli MBIM (2017) A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization 7(4):417\u2013433","journal-title":"Numerical Algebra, Control & Optimization"},{"key":"3035_CR18","doi-asserted-by":"crossref","unstructured":"Espinoza-Nev\u00e1rez D, Ortiz-Bayliss JC, Terashima-Mar\u00edn H, Gatica G (2016) Selection and generation hyper-heuristics for solving the vehicle routing problem with time windows. In: Proceedings of the 2016 on genetic and evolutionary computation conference companion, GECCO \u201916 Companion, pp 139\u2013140","DOI":"10.1145\/2908961.2909051"},{"key":"3035_CR19","doi-asserted-by":"crossref","unstructured":"Fredericks EM, Gerostathopoulos I, Krupitzer C, Vogel T (2019) Planning as optimization: dynamically discovering optimal configurations for runtime situations. In: 2019 IEEE 13th International conference on self-adaptive and self-organizing systems (SASO), IEEE, pp 1\u201310","DOI":"10.1109\/SASO.2019.00010"},{"issue":"5","key":"3035_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F Glover","year":"1986","unstructured":"Glover F (1986) Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5):533\u2013549","journal-title":"Computers & Operations Research"},{"key":"3035_CR21","doi-asserted-by":"crossref","unstructured":"Golden BL, Raghavan S, Wasil EA (2008) The vehicle routing problem: latest advances and new challenges, vol 43. Springer Science & Business Media","DOI":"10.1007\/978-0-387-77778-8"},{"key":"3035_CR22","unstructured":"Hintsch T, Irnich S (2018) Exact solution of the soft-clustered vehicleRouting problem. Working papers 1813, gutenberg school of management and economics, johannes gutenberg-universit\u00e4t mainz"},{"issue":"1","key":"3035_CR23","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1038\/scientificamerican0792-66","volume":"267","author":"JH Holland","year":"1992","unstructured":"Holland JH (1992) Genetic Algorithms. Scientific American 267(1):66\u201373","journal-title":"Scientific American"},{"key":"3035_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2017\/7430125","volume":"2017","author":"A Hussain","year":"2017","unstructured":"Hussain A, Muhammad YS, Sajid MN, Hussain I, Shoukry AM, Gani S (2017) Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational Intelligence and Neuroscience 2017:1\u20137","journal-title":"Computational Intelligence and Neuroscience"},{"issue":"3","key":"3035_CR25","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.3934\/jimo.2020012","volume":"17","author":"B Ke\u00e7eci","year":"2021","unstructured":"Ke\u00e7eci B, Alt\u0131parmak F, Kara \u0130 (2021) A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial & Management Optimization 17(3):1069","journal-title":"Journal of Industrial & Management Optimization"},{"issue":"3","key":"3035_CR26","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0377-2217(92)90192-C","volume":"59","author":"G Laporte","year":"1992","unstructured":"Laporte G (1992) The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research 59(3):345\u2013358","journal-title":"European journal of operational research"},{"key":"3035_CR27","unstructured":"Lehman J, Stanley KO (2008) Exploiting open-endedness to solve problems through the search for novelty. In: ALIFE, pp 329\u2013336"},{"key":"3035_CR28","volume-title":"Surveys in combinatorial optimization","author":"S Martello","year":"2011","unstructured":"Martello S, Minoux M, Ribeiro C, Laporte G (2011) Surveys in combinatorial optimization. Elsevier"},{"issue":"1","key":"3035_CR29","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s10479-017-2520-5","volume":"259","author":"A Montero","year":"2017","unstructured":"Montero A, Jos\u00e9 Miranda-Bront J, M\u00e9ndez-D\u00edaz I (2017) An ILP-based local search procedure for the VRP with pickups and deliveries. Annals of Operations Research 259(1):327\u2013350","journal-title":"Annals of Operations Research"},{"key":"3035_CR30","doi-asserted-by":"publisher","unstructured":"Mukherjee A, Barma PS, Dutta J, Panigrahi G, Kar S, Maiti M (2021) A multi-objective antlion optimizer for the ring tree problem with secondary sub-depots. Oper Res 1\u201339. https:\/\/doi.org\/10.1007\/s12351-021-00623-8","DOI":"10.1007\/s12351-021-00623-8"},{"key":"3035_CR31","doi-asserted-by":"crossref","unstructured":"Pigden T (2013) Missing from the model: Orders, drivers, tractors and trailers and non-linear loading. In: Proceedings of the 15th annual conference companion on genetic and evolutionary computation, GECCO \u201913 Companion, p 1079-1084","DOI":"10.1145\/2464576.2482686"},{"issue":"3","key":"3035_CR32","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1080\/0952813X.2019.1652356","volume":"32","author":"B Rabbouch","year":"2020","unstructured":"Rabbouch B, Sa\u00e2daoui F, Mraihi R (2020) Empirical-type simulated annealing for solving the capacitated vehicle routing problem. Journal of Experimental & Theoretical Artificial Intelligence 32(3):437\u2013452","journal-title":"Journal of Experimental & Theoretical Artificial Intelligence"},{"issue":"2","key":"3035_CR33","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10100-016-0464-5","volume":"25","author":"SK Roy","year":"2017","unstructured":"Roy SK, Maity G, Weber GW (2017) Multi-objective two-stage grey transportation problem using utility function with goals. Central European Journal of Operations Research 25(2):417","journal-title":"Central European Journal of Operations Research"},{"issue":"1","key":"3035_CR34","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/s10479-016-2283-4","volume":"253","author":"SK Roy","year":"2017","unstructured":"Roy SK, Maity G, Weber GW, G\u00f6k SZA (2017) Conic scalarization approach to solve multi-choice multi-objective transportation problem with interval goal. Annals of Operations Research 253(1):599\u2013620","journal-title":"Annals of Operations Research"},{"issue":"12","key":"3035_CR35","doi-asserted-by":"publisher","first-page":"8593","DOI":"10.1007\/s00521-019-04431-2","volume":"31","author":"SK Roy","year":"2019","unstructured":"Roy SK, Midya S, Weber GW (2019) Multi-objective multi-item fixed-charge solid transportation problem under twofold uncertainty. Neural Computing and Applications 31(12):8593\u20138613","journal-title":"Neural Computing and Applications"},{"key":"3035_CR36","unstructured":"Shahdaei AM, Rahimi AM (2016) Solving vehicule routing problem with simultaneous pick-up and delivery with the application of genetic algirithm. 247\u2013259"},{"key":"3035_CR37","doi-asserted-by":"crossref","unstructured":"Tchoupo MN, Yalaoui A, Amodeo L, Yalaoui F, Lutz F (2017) Ant colony optimization algorithm for pickup and delivery problem with time windows. In: Springer proceedings in mathematics & statistics, Springer International Publishing, pp 181\u2013191","DOI":"10.1007\/978-3-319-67308-0_19"},{"issue":"1","key":"3035_CR38","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1111\/coin.12240","volume":"36","author":"EB Tirkolaee","year":"2020","unstructured":"Tirkolaee EB, Hadian S, Weber GW, Mahdavi I (2020) A robust green traffic-based routing problem for perishable products distribution. Computational Intelligence 36(1):80\u2013101","journal-title":"Computational Intelligence"},{"key":"3035_CR39","doi-asserted-by":"publisher","unstructured":"Tirkolaee, E.B., Hosseinabadi, A.A.R., Soltani, M., Sangaiah, A.K., Wang, J.: A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services. Sustainability 10(5) (2018). https:\/\/doi.org\/10.3390\/su10051366","DOI":"10.3390\/su10051366"},{"issue":"3","key":"3035_CR40","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1109\/TCYB.2015.2409837","volume":"46","author":"J Wang","year":"2016","unstructured":"Wang J, Zhou Y, Wang Y, Zhang J, Chen CLP, Zheng Z (2016) Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances, and algorithms. IEEE Transactions on Cybernetics 46(3):582\u2013594","journal-title":"IEEE Transactions on Cybernetics"},{"issue":"3","key":"3035_CR41","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1016\/j.ejor.2017.08.035","volume":"265","author":"L Wei","year":"2018","unstructured":"Wei L, Zhang Z, Zhang D, Leung SC (2018) A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research 265(3):843\u2013859","journal-title":"European Journal of Operational Research"},{"key":"3035_CR42","unstructured":"Zhang Y, Harman M, Ochoa G, Ruhe G, Brinkkemper S (2014) An empirical study of meta-and hyper-heuristic search for multi-objective release planning. RN 14(07):1\u201332"},{"issue":"1","key":"3035_CR43","first-page":"205","volume":"4","author":"M Zirour","year":"2008","unstructured":"Zirour M (2008) Vehicle routing problem: models and solutions. Journal of Quality Measurement and Analysis JQMA 4(1):205\u2013218","journal-title":"Journal of Quality Measurement and Analysis JQMA"}],"container-title":["Applied Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-021-03035-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10489-021-03035-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10489-021-03035-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T09:31:21Z","timestamp":1653903081000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10489-021-03035-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":43,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["3035"],"URL":"https:\/\/doi.org\/10.1007\/s10489-021-03035-5","relation":{},"ISSN":["0924-669X","1573-7497"],"issn-type":[{"value":"0924-669X","type":"print"},{"value":"1573-7497","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,6]]},"assertion":[{"value":"22 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}