A Multi-Stage Algorithm for a Capacitated Vehicle Routing Problem with Time Constraints

Lucia Cassettari; Melissa Demartini; Roberto Mosca; Roberto Revetria; Flavio Tonelli

doi:10.3390/a11050069

Algorithms (May 2018)

A Multi-Stage Algorithm for a Capacitated Vehicle Routing Problem with Time Constraints

Lucia Cassettari,
Melissa Demartini,
Roberto Mosca,
Roberto Revetria,
Flavio Tonelli

Affiliations

Lucia Cassettari: DIME—Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy
Melissa Demartini: DIME—Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy
Roberto Mosca: DIME—Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy
Roberto Revetria: DIME—Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy
Flavio Tonelli: DIME—Department of Mechanical Engineering, Energetics, Management and Transportation, Polytechnic School, University of Genoa, 16145 Genoa, Italy

DOI: https://doi.org/10.3390/a11050069
Journal volume & issue: Vol. 11, no. 5
p. 69

Abstract

Read online

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.

vehicle routing problem (VRP), capacitated vehicle routing problem (CVRP), natural gas distribution networks

Published in Algorithms

ISSN: 1999-4893 (Online)
Publisher: MDPI AG
Country of publisher: Switzerland
LCC subjects: Technology: Technology (General): Industrial engineering. Management engineering; Science: Mathematics: Instruments and machines: Electronic computers. Computer science
Website: https://www.mdpi.com/journal/algorithms

About the journal

Abstract

Keywords