{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T12:20:16Z","timestamp":1778156416650,"version":"3.51.4"},"reference-count":34,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,28]],"date-time":"2020-12-28T00:00:00Z","timestamp":1609113600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The objective of this paper is to consider the vehicle routing problem with time windows under two uncertainties: service and travel times. We introduce new resolution approaches for the robust problem and an efficient parallel procedure for the generation of all possible scenarios. The best robust solution of each scenario can be achieved by using a parallel adaptive large neighborhood search metaheuristic. Through our analysis, we expect to find the best compromise between the reduced running time and a best good solution, which leads to four distinct combinations of parallel\/sequential approaches. The computational experiments are performed and tested on Solomon\u2019s benchmark and large randomly generated instances. Furthermore, our results can be protected against delay in service time in a reasonable running time especially for large instances.<\/jats:p>","DOI":"10.3390\/sym13010036","type":"journal-article","created":{"date-parts":[[2020,12,28]],"date-time":"2020-12-28T20:03:03Z","timestamp":1609185783000},"page":"36","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Multithreading Parallel Robust Approach for the VRPTW with Uncertain Service and Travel Times"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5827-1992","authenticated-orcid":false,"given":"Mehdi","family":"Nasri","sequence":"first","affiliation":[{"name":"National School of Applied Sciences Khouribga, Sultan Moulay Slimane University, 23052 Beni Mellal, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Imad","family":"Hafidi","sequence":"additional","affiliation":[{"name":"National School of Applied Sciences Khouribga, Sultan Moulay Slimane University, 23052 Beni Mellal, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdelmoutalib","family":"Metrane","sequence":"additional","affiliation":[{"name":"National School of Applied Sciences Khouribga, Sultan Moulay Slimane University, 23052 Beni Mellal, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1016\/j.cie.2009.05.009","article-title":"The vehicle routing problem: A taxonomic review","volume":"57","author":"Eksioglu","year":"2009","journal-title":"Comput. Ind. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/j.cie.2015.12.007","article-title":"The Vehicle Routing Problem: State of the Art Classification and Review","volume":"99","author":"Braekers","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/j.ejor.2019.10.010","article-title":"A concise guide to existing and emerging vehicle routing problem variants","volume":"286","author":"Vidal","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1287\/trsc.1030.0057","article-title":"Vehicle Routing Problem with time windows, Part II: Metaheuristics","volume":"39","author":"Gendreau","year":"2005","journal-title":"J. Transp. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/0-387-25486-2_3","article-title":"Vehicle Routing Problem with Time Windows","volume":"1","author":"Kallehauge","year":"2005","journal-title":"Column Gener."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0377-2217(86)90242-0","article-title":"Stochastic vehicle routing with modified savings algorithm","volume":"23","author":"Dror","year":"1986","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","first-page":"183","article-title":"Vehicle Routing with Stochastic Demands and Restricted Failures","volume":"37","author":"Dror","year":"1993","journal-title":"ZOR-Model. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0377-2217(95)00050-X","article-title":"Stochastic vehicle routing","volume":"88","author":"Gendreau","year":"1996","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","first-page":"1","article-title":"A robust approach for solving a vehicle routing problem with time windows with uncertain service and travel times","volume":"11","author":"Nasri","year":"2020","journal-title":"Int. J. Ind. Eng. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.ajsl.2018.06.014","article-title":"A Robust Metaheuristic for the Rail Shuttle Routing Problem with Uncertainty: A Real Case Study in the Le Havre Port","volume":"34","author":"Rouky","year":"2018","journal-title":"Asian J. Shipp. Logist."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.cie.2017.05.029","article-title":"A new robust criterion for the vehicle routing problem with uncertain travel time","volume":"112","author":"Wu","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_12","unstructured":"Gutin, G., and Punnen, A. (2002). The Traveling Salesman Problem and Its Variations, Springer Science & Business Media."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2002). An overview of vehicle routing problems. 9 of SIAM Monographs on Discrete Mathematics and Applications, SIAM.","DOI":"10.1137\/1.9780898718515.ch1"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02601637","article-title":"Simulated annealing metaheuristics for the vehicle routing problem with time windows","volume":"63","author":"Chiang","year":"1996","journal-title":"Ann. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Afifi, S., Dang, D.C., and Moukrim, A. (2013). A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints. International Conference on Learning and Intelligent Optimization, Science Springer. Lecture Notes in Computer.","DOI":"10.1007\/978-3-642-44973-4_27"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Hansen","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1016\/j.procs.2016.05.473","article-title":"A VNS-based Heuristic for Solving the Vehicle Routing Problem with Time Windows and Vehicle Preventive Maintenance Constraints","volume":"80","author":"Dhahri","year":"2016","journal-title":"Procedia Comput. Sci."},{"key":"ref_18","unstructured":"Gambardella, L.M., Taillard, E., and Agazzi, G. (1999). MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. New Ideas in Optimization, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/11816102_4","article-title":"Ant Colony System for Optimizing Vehicle Routing Problem with Time Windows (VRPTW)","volume":"Volume 4115","author":"Tan","year":"2006","journal-title":"Computational Intelligence and Bioinformatics. ICIC 2006"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Thangiah, S. (1995). Vehicle routing with time windows using genetic algorithms. Application Handbook of Genetic Algorithms: New Frontiers, Artificial Intelligence Lab., Slippery Rock Univ.","DOI":"10.1201\/9781420050073.ch11"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1287\/ijoc.8.2.158","article-title":"The vehicle routing problem with time windows part I: Tabu search","volume":"8","author":"Potvin","year":"1996","journal-title":"INFORMS J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1287\/trsc.31.2.170","article-title":"A tabu search heuristic for the vehicle routing problem with soft time windows","volume":"31","author":"Taillard","year":"1997","journal-title":"Transp. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02579017","article-title":"Tabu Search heuristics for the Vehicle Routing Problem with Time Windows","volume":"10","author":"Gendreau","year":"2002","journal-title":"Top J."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1685","DOI":"10.1016\/j.cor.2003.11.023","article-title":"A cooperative parallel meta-heuristic for the vehicle routing problem with time windows","volume":"32","author":"Bouthillier","year":"2005","journal-title":"Comput. Oper. Res."},{"key":"ref_25","unstructured":"R\u00f8pke, S. (2009, January 13\u201316). PALNS\u2014A software framework for parallel large neighborhood search. Proceedings of the 8th Metaheuristic International Conference CDROM, Metaheuristic International Conference, Hamburg, Germany."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.ejor.2014.11.024","article-title":"Sequential and Parallel Large Neighborhood Search Algorithms for the Periodic Location Routing Problem","volume":"243","author":"Hemmelmayer","year":"2002","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1525","DOI":"10.1007\/s11590-012-0567-4","article-title":"A parallel matheuristic for the technician routing and scheduling problem","volume":"7","author":"Pillac","year":"2013","journal-title":"Optim. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ord\u00f3\u00f1ez, F. (2010). Robust Vehicle Routing. Tutorials in Operations Research, Institue for Operations Research and the Management Sciences (INFORMS).","DOI":"10.1287\/educ.1100.0078"},{"key":"ref_29","first-page":"769","article-title":"Robust convex optimization","volume":"23","author":"Nemirovski","year":"1998","journal-title":"Oper. Res. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0167-6377(99)00016-4","article-title":"Robust solutions of uncertain linear programs","volume":"25","author":"Nemirovski","year":"1999","journal-title":"Oper. Res. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1287\/opre.1030.0065","article-title":"The price of robustness","volume":"52","author":"Bertsimas","year":"2004","journal-title":"Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1287\/trsc.1050.0135","article-title":"An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows","volume":"40","author":"Pisinger","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the Vehicle Routing and Scheduling Problem with time Window Constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Oper. Res. J."},{"key":"ref_34","unstructured":"Gehring, H., and Homberger, J. (1999). A Parallel Hybrid Evolutionary Metaheuristic for the Vehicle Routing Problem with Time Windows. Proceedings of EUROGEN99, Springer. Available online: http:\/\/sintef.no\/projectweb\/top\/vrptw\/Homberger-benchmark\/."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/1\/36\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:47:03Z","timestamp":1760179623000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/1\/36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,28]]},"references-count":34,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["sym13010036"],"URL":"https:\/\/doi.org\/10.3390\/sym13010036","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,28]]}}}