{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T18:03:40Z","timestamp":1774721020480,"version":"3.50.1"},"reference-count":20,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2018,5,10]],"date-time":"2018-05-10T00:00:00Z","timestamp":1525910400000},"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 (VRP) is one of the most optimized tasks studied and it is implemented in a huge variety of industrial applications. The objective is to design a set of minimum cost paths for each vehicle in order to serve a given set of customers. Our attention is focused on a variant of VRP, the capacitated vehicle routing problem when applied to natural gas distribution networks. Managing natural gas distribution networks includes facing a variety of decisions ranging from human resources and material resources to facilities, infrastructures, and carriers. Despite the numerous papers available on vehicle routing problem, there are only a few that study and analyze the problems occurring in capillary distribution operations such as those found in a metropolitan area. Therefore, this work introduces a new algorithm based on the Saving Algorithm heuristic approach which aims to solve a Capacitated Vehicle Routing Problem with time and distance constraints. This joint algorithm minimizes the transportation costs and maximizes the workload according to customer demand within the constraints of a time window. Results from a real case study in a natural gas distribution network demonstrates the effectiveness of the approach.<\/jats:p>","DOI":"10.3390\/a11050069","type":"journal-article","created":{"date-parts":[[2018,5,11]],"date-time":"2018-05-11T03:42:48Z","timestamp":1526010168000},"page":"69","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A Multi-Stage Algorithm for a Capacitated Vehicle Routing Problem with Time Constraints"],"prefix":"10.3390","volume":"11","author":[{"given":"Lucia","family":"Cassettari","sequence":"first","affiliation":[{"name":"DIME\u2014Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Melissa","family":"Demartini","sequence":"additional","affiliation":[{"name":"DIME\u2014Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Mosca","sequence":"additional","affiliation":[{"name":"DIME\u2014Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Revetria","sequence":"additional","affiliation":[{"name":"DIME\u2014Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Flavio","family":"Tonelli","sequence":"additional","affiliation":[{"name":"DIME\u2014Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,5,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.procir.2017.03.343","article-title":"Investigating flexibility as a performance dimension of a Manufacturing Value Modeling Methodology (MVMM): A framework for identifying flexibility types in manufacturing systems","volume":"63","author":"Burger","year":"2017","journal-title":"Procedia CIRP"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1080\/09537287.2011.609647","article-title":"Production planning of mixed-model assembly lines: A huristic mixed integer programming based approach","volume":"24","author":"Tonelli","year":"2013","journal-title":"Prod. Plan. Control"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Demartini, M., Orlandi, I., Tonelli, F., and Anguitta, D. (2017). A Manufacturing Value Modeling Methodology (MVMM): A value mapping and assessment framework for sustainable manufacturing. International Conference on Sustainable Design and Manufacturing, Springer.","DOI":"10.1007\/978-3-319-57078-5_10"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/S0927-0507(06)14006-2","article-title":"Chapter 6 Vehicle Routing","volume":"Volume 14","author":"Cordeau","year":"2007","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"ref_5","first-page":"303","article-title":"A framework for assessment and implementation of product-service systems strategies: Learning from an action research in the health-case sector","volume":"6","author":"Tonelli","year":"2009","journal-title":"WSEAS Trans. Bus. Econ."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10776-016-0319-y","article-title":"Data Gathering in Wireless Sensor Networks Using Unmanned Aerial Vehicles","volume":"23","author":"Mazayev","year":"2016","journal-title":"Int. J. Wirel. Inf. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.adhoc.2017.09.003","article-title":"Interest-aware energy collection & resource management in machine to machine communications","volume":"68","author":"Tsiropoulou","year":"2018","journal-title":"Ad Hoc Netw."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Tsiropoulou, E.E., Paruchuri, S.T., and Baras, J.S. (2017, January 22\u201324). Interest, energy and physical-aware coalition formation and resource allocation in smart IoT applications. Proceedings of the 51st Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA.","DOI":"10.1109\/CISS.2017.7926111"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1016\/j.energy.2016.11.090","article-title":"Optimization of a natural gas distribution network with potential future extensions","volume":"125","author":"Haikarainen","year":"2017","journal-title":"Energy"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1080\/07408170701745378","article-title":"A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty","volume":"40","author":"Sungur","year":"2008","journal-title":"IIE Trans."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.apenergy.2014.06.042","article-title":"Optimization for design and operation of natural gas transmission networks","volume":"133","year":"2014","journal-title":"Appl. Energy"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/j.compchemeng.2016.06.006","article-title":"Multi-objective design optimization of natural gas transmission networks","volume":"93","author":"Alves","year":"2016","journal-title":"Comput. Chem. Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.compchemeng.2014.02.002","article-title":"Stochastic optimal control model for natural gas networks","volume":"64","author":"Zavala","year":"2014","journal-title":"Comput. Chem. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.jngse.2016.05.017","article-title":"Layout optimization of natural gas network planning: Synchronizing minimum risk loss with total cost","volume":"33","author":"An","year":"2016","journal-title":"J. Nat. Gas Sci. Eng."},{"key":"ref_15","first-page":"1","article-title":"Field services design and management of natural gas distribution networks: A class of vehicle routing problem with time windows approach","volume":"56","author":"Paolucci","year":"2017","journal-title":"Int. J. Prod. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0927-0507(05)80108-2","article-title":"Chapter 4 Analysis of vehicle routing and inventory-routing problems","volume":"Volume 8","author":"Federgruen","year":"1995","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"413","DOI":"10.48084\/etasr.292","article-title":"An Improved Clarke and Wright Algorithm to Solve the Capacitated Vehicle Routing Problem","volume":"3","author":"Caccetta","year":"2013","journal-title":"Technol. Appl. Sci. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Pan, H., and Li, W. (2009, January 20\u201322). Hybrid Genetic-Saving Algorithm and Its Application in Vehicle Routing Problem. Proceedings of the International Conference on Management and Service Science, Wuhan, China.","DOI":"10.1109\/ICMSS.2009.5305361"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1016\/j.procs.2016.07.127","article-title":"A Discrete Hybrid Invasive Weed Optimization Algorithm for the Capacitated Vehicle Routing Problem","volume":"91","author":"Zhao","year":"2016","journal-title":"Procedia Comput. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/trsc.1030.0056","article-title":"Vehicle Routing Problem with Time Windows, Part I\u202f: Route Construction and Local Search Algorithms","volume":"39","author":"Gendreau","year":"2005","journal-title":"Transp. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/69\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:04:10Z","timestamp":1760195050000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/5\/69"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,10]]},"references-count":20,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2018,5]]}},"alternative-id":["a11050069"],"URL":"https:\/\/doi.org\/10.3390\/a11050069","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,10]]}}}