An analysis of the vehicle routing problem for logistics distribution

The vehicle routing problem (VRP) is a combinatorial optimization and integer-programming problem formulated to answer the following question: “What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?”. In logistics distribution, VRP is frequently encountered and because it is a non-polynomial (NP)-hard problem of operational research, trying to solve it for optimality is non-trivial and there are limited instances of the problems that can actually be solved optimally. In this paper, we carried out a simulation study whose aim is to estimate the length of the optimal tour (i.e. shortest tour) bypassing the need for solving the Traveling Salesman Problem (TSP). To this end, we introduced two dimensionless coefficients (k1 and k2). Both coefficients are computed starting from a simple tour (i.e. the “round trip” tour). The coefficients describe the ratio between the length of the “round trip” tour and the tour obtained by applying the CW savings algorithm (k1) or the “optimal” tour (k2). By analyzing a number of retail stores (RS) from 1 to 11, we plan to derive a trend for k1 and k2 as a function of N so that, for higher N values, one can directly compute the length of the tour using these coefficients (k2 in particular) and the length of the round trip tour, without solving the TSP. The analysis carried out will be exploited to support the design of a reverse logistics channel to recover food waste from RSs, which is the aim of a research project currently in process at the University of Parma and targeting the Emilia-Romagna region