{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,29]],"date-time":"2026-08-29T15:36:50Z","timestamp":1788017810611,"version":"build-2784847793"},"reference-count":55,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2020,9,26]],"date-time":"2020-09-26T00:00:00Z","timestamp":1601078400000},"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>The Vehicle Routing Problem with Time Windows (VRPTW) is an NP-Hard optimization problem which has been intensively studied by researchers due to its applications in real-life cases in the distribution and logistics sector. In this problem, customers define a time slot, within which they must be served by vehicles of a standard capacity. The aim is to define cost-effective routes, minimizing both the number of vehicles and the total traveled distance. When we seek to minimize both attributes at the same time, the problem is considered as multiobjective. Although numerous exact, heuristic and metaheuristic algorithms have been developed to solve the various vehicle routing problems, including the VRPTW, only a few of them face these problems as multiobjective. In the present paper, a Multiobjective Large Neighborhood Search (MOLNS) algorithm is developed to solve the VRPTW. The algorithm is implemented using the Python programming language, and it is evaluated in Solomon\u2019s 56 benchmark instances with 100 customers, as well as in Gehring and Homberger\u2019s benchmark instances with 1000 customers. The results obtained from the algorithm are compared to the best-published, in order to validate the algorithm\u2019s efficiency and performance. The algorithm is proven to be efficient both in the quality of results, as it offers three new optimal solutions in Solomon\u2019s dataset and produces near optimal results in most instances, and in terms of computational time, as, even in cases with up to 1000 customers, good quality results are obtained in less than 15 min. Having the potential to effectively solve real life distribution problems, the present paper also discusses a practical real-life application of this algorithm.<\/jats:p>","DOI":"10.3390\/a13100243","type":"journal-article","created":{"date-parts":[[2020,9,27]],"date-time":"2020-09-27T22:24:42Z","timestamp":1601245482000},"page":"243","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["A Multiobjective Large Neighborhood Search Metaheuristic for the Vehicle Routing Problem with Time Windows"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5447-0399","authenticated-orcid":false,"given":"Grigorios D.","family":"Konstantakopoulos","sequence":"first","affiliation":[{"name":"Sector of Industrial Management and Operational Research, School of Mechanical Engineering, National Technical University of Athens, 15780 Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7524-0215","authenticated-orcid":false,"given":"Sotiris P.","family":"Gayialis","sequence":"additional","affiliation":[{"name":"Sector of Industrial Management and Operational Research, School of Mechanical Engineering, National Technical University of Athens, 15780 Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9466-6185","authenticated-orcid":false,"given":"Evripidis P.","family":"Kechagias","sequence":"additional","affiliation":[{"name":"Sector of Industrial Management and Operational Research, School of Mechanical Engineering, National Technical University of Athens, 15780 Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgios A.","family":"Papadopoulos","sequence":"additional","affiliation":[{"name":"Sector of Industrial Management and Operational Research, School of Mechanical Engineering, National Technical University of Athens, 15780 Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilias P.","family":"Tatsiopoulos","sequence":"additional","affiliation":[{"name":"Sector of Industrial Management and Operational Research, School of Mechanical Engineering, National Technical University of Athens, 15780 Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Dantzig, G.B., and Ramser, J.H. (1959). The truck dispatching problem. Manag. Sci., 6.","DOI":"10.1287\/mnsc.6.1.80"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1016\/j.eswa.2013.07.107","article-title":"Survey of Green Vehicle Routing Problem: Past and future trends","volume":"41","author":"Lin","year":"2014","journal-title":"Expert Syst. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Konstantakopoulos, G.D., Gayialis, S.P., and Kechagias, E.P. (2020). Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Oper. Res. Int. J.","DOI":"10.1007\/s12351-020-00600-7"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ju\u00e1rez P\u00e9rez, M., P\u00e9rez Loaiza, R.E., Quintero Flores, P.M., Atriano Ponce, O., and Flores Peralta, C. (2019). A Heuristic Algorithm for the Routing and Scheduling Problem with Time Windows: A Case Study of the Automotive Industry in Mexico. Algorithms, 12.","DOI":"10.3390\/a12050111"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1016\/j.cor.2009.06.022","article-title":"A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows","volume":"37","author":"Nagata","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ait Haddadene, S., Labadie, N., and Prodhon, C. (2019). Bicriteria Vehicle Routing Problem with Preferences and Timing Constraints in Home Health Care Services. Algorithms, 12.","DOI":"10.3390\/a12080152"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.cor.2014.07.005","article-title":"A vehicle routing problem with flexible time windows","volume":"52","author":"Jabali","year":"2014","journal-title":"Comput. Oper. Res."},{"key":"ref_8","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_9","doi-asserted-by":"crossref","unstructured":"Iqbal, S., and Rahman, M.S. (2012, January 20\u201322). Vehicle routing problems with soft time windows. Proceedings of the 2012 7th International Conference on Electrical and Computer Engineering, Dhaka, Bangladesh.","DOI":"10.1109\/ICECE.2012.6471630"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"19643","DOI":"10.1109\/ACCESS.2019.2894681","article-title":"Brainstorming-Based Ant Colony Optimization for Vehicle Routing with Soft Time Windows","volume":"7","author":"Wu","year":"2019","journal-title":"IEEE Access"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2271","DOI":"10.1016\/j.dam.2006.04.009","article-title":"The vehicle routing problem with flexible time windows and traveling times","volume":"154","author":"Hashimoto","year":"2006","journal-title":"Discret. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1287\/trsc.26.2.69","article-title":"An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints","volume":"26","author":"Koskosidis","year":"1992","journal-title":"Transp. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.cor.2018.02.007","article-title":"What makes a VRP solution good? The generation of problem-specific knowledge for heuristics","volume":"106","author":"Arnold","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_14","unstructured":"Ibaraki, T., Kubo, M., Masuda, T., Uno, T., and Yagiura, M. (2001, January 16\u201320). Effective local search algorithms for the vehicle routing problem with general time window constraints. Proceedings of the MIC, Porto, Portugal."},{"key":"ref_15","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_16","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.jksus.2010.03.002","article-title":"Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods","volume":"22","year":"2010","journal-title":"J. King Saud Univ. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/trsc.1030.0056","article-title":"Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the vehicle routing and scheduling problems with time window constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Maher, M., and Puget, J.-F. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. Principles and Practice of Constraint Programming\u2014CP98, Proceedings of the International Conference on Principles and Practice of Constraint Programming, Pisa, Italy, 26\u201330 October 1998, Springer.","DOI":"10.1007\/3-540-49481-2"},{"key":"ref_20","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":"Ropke","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"992","DOI":"10.1016\/j.ress.2005.11.018","article-title":"Multi-objective optimization using genetic algorithms: A tutorial","volume":"91","author":"Konak","year":"2006","journal-title":"Reliab. Eng. Syst. Saf."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10589-005-3070-3","article-title":"A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem","volume":"34","author":"Tan","year":"2006","journal-title":"Comput. Optim. Appl."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/s10489-006-6926-z","article-title":"Multi-objective genetic algorithms for vehicle routing problem with time windows","volume":"24","author":"Ombuki","year":"2006","journal-title":"Appl. Intell."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.cor.2013.11.014","article-title":"A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows","volume":"45","author":"Chiang","year":"2014","journal-title":"Comput. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/j.cor.2010.05.004","article-title":"An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows","volume":"38","author":"Bullinaria","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1016\/j.cie.2013.01.007","article-title":"A hybrid meta-heuristic for multi-objective Vehicle Routing Problems with Time Windows","volume":"65","author":"Ortega","year":"2013","journal-title":"Comput. Ind. Eng."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10898-015-0314-3","article-title":"Generation of Pareto optimal solutions using generalized DEA and PSO","volume":"64","author":"Yun","year":"2016","journal-title":"J. Glob. Optim."},{"key":"ref_28","unstructured":"Ehrgott, M. (2005). Multicriteria Optimization, Springer Science & Business Media. [2nd ed.]."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/j.ejor.2012.06.044","article-title":"An adaptive large neighborhood search heuristic for the Pollution-Routing Problem","volume":"223","author":"Demir","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","unstructured":"(2020, September 18). Transportation Optimization Portal\/VRPTW. Available online: https:\/\/www.sintef.no\/projectweb\/top\/vrptw\/homberger-benchmark\/."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1096","DOI":"10.1016\/j.asoc.2010.04.001","article-title":"Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm","volume":"10","author":"Ghoseiri","year":"2010","journal-title":"Appl. Soft Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1287\/opre.40.2.342","article-title":"A new optimization algorithm for the vehicle routing problem with time windows","volume":"40","author":"Desrochers","year":"1992","journal-title":"Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Tavares, J., Pereira, F.B., Machado, P., and Costa, E. (2003, January 9\u201312). On the influence of GVR in vehicle routing. Proceedings of the SAC, Melbourne, FL, USA.","DOI":"10.1145\/952532.952679"},{"key":"ref_34","unstructured":"Lau, H.C., Lim, Y.F., and Liu, Q.Z. (2001, January 8\u201310). Diversification of search neighborhood via constraint-based local search and its applications to VRPTW. Proceedings of the 3rd International Workshop on Integration of AI and OR Techniques (CP-AI-OR), Kent, UK."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1464","DOI":"10.1016\/j.cor.2004.11.002","article-title":"Lagrangean duality applied on vehicle routing with time windows","volume":"33","author":"Kallehauge","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_36","unstructured":"Cook, W., and Rich, J.L. (1999). A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows, Rice University."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.eswa.2010.06.082","article-title":"A hybrid algorithm for vehicle routing problem with time windows","volume":"38","author":"Yu","year":"2011","journal-title":"Expert Syst. Appl."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF02430370","article-title":"Probabilistic diversification and intensification in local search for vehicle routing","volume":"1","author":"Rochat","year":"1995","journal-title":"J. Heuristics"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Kohl, N., Desrosiers, J., Madsen, O.B.G., Solomon, M.M., and Soumis, F. (1999). 2-Path Cuts for the Vehicle Routing Problem with Time Windows. Transp. Sci., 33.","DOI":"10.1287\/trsc.33.1.101"},{"key":"ref_40","unstructured":"Shaw, P. (2020, September 25). A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.51.1273&rep=rep1&type=pdf."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1561","DOI":"10.1016\/j.cor.2005.07.025","article-title":"A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows","volume":"34","author":"Alvarenga","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0377-2217(02)00486-1","article-title":"Local search with annealing-like restarts to solve the VRPTW","volume":"150","author":"Li","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1287\/ijoc.8.2.165","article-title":"The Vehicle Routing Problem with Time Windows Part II: Genetic Search","volume":"8","author":"Potvin","year":"1996","journal-title":"INFORMS J. Comput."},{"key":"ref_44","first-page":"297","article-title":"Two evolutionary metaheuristics for the vehicle routing problem with time windows","volume":"37","author":"Homberger","year":"1999","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1023\/A:1013661617536","article-title":"Using constraint-based operators to solve the vehicle routing problem with time windows","volume":"8","author":"Rousseau","year":"2002","journal-title":"J. Heuristics"},{"key":"ref_46","unstructured":"Thangiah, S.R., Osman, I.H., and Sun, T. (1994). Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows, Computer Science Department, Slippery Rock University. Technical Report No. SRU CpSc-TR-94-27."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1051\/ro:2008021","article-title":"A memetic algorithm for the vehicle routing problem with time windows","volume":"42","author":"Labadi","year":"2008","journal-title":"RAIRO-Operations Res."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1016\/j.eswa.2005.12.014","article-title":"A multi-parametric evolution strategies algorithm for vehicle routing problems","volume":"32","author":"Mester","year":"2007","journal-title":"Expert Syst. Appl."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.neucom.2014.06.033","article-title":"A cooperative population learning algorithm for vehicle routing problem with time windows","volume":"146","author":"Barbucha","year":"2014","journal-title":"Neurocomputing"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s10479-008-0487-y","article-title":"A hybrid search method for the vehicle routing problem with time windows","volume":"180","author":"Vasconcelos","year":"2010","journal-title":"Ann. Oper. Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/S0377-2217(03)00031-6","article-title":"Design of an IT-driven decision support system for vehicle routing and scheduling","volume":"152","author":"Gayialis","year":"2004","journal-title":"Eur. J. Oper. Res."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Gayialis, S.P., Konstantakopoulos, G.D., Papadopoulos, G.A., Kechagias, E., and Ponis, S.T. (2018, January 26\u201330). Developing an Advanced Cloud-Based Vehicle Routing and Scheduling System for Urban Freight Transportation. Proceedings of the IFIP International Conference on Advances in Production Management Systems, Seoul, Korea.","DOI":"10.1007\/978-3-319-99707-0_24"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1080\/01441647.2017.1297869","article-title":"Requirements from vehicle routing software: Perspectives from literature, developers and the freight industry","volume":"38","author":"Waterson","year":"2018","journal-title":"Transp. Rev."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"J\u00e1rmai, K., and Boll\u00f3, B. (2017). Intelligent Transportation Systems to Support Production Logistics. Proceedings of the Vehicle and Automotive Engineering, Springer International Publishing.","DOI":"10.1007\/978-3-319-51189-4"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Kechagias, E.P., Gayialis, S.P., Konstantakopoulos, G.D., and Papadopoulos, G.A. (2020). An Application of a Multi-Criteria Approach for the Development of a Process Reference Model for Supply Chain Operations. Sustainability, 12.","DOI":"10.3390\/su12145791"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/243\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:14:01Z","timestamp":1760177641000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,26]]},"references-count":55,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2020,10]]}},"alternative-id":["a13100243"],"URL":"https:\/\/doi.org\/10.3390\/a13100243","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,26]]}}}