Classic formulations of the two-echelon vehicle routing problem (2E-VRP) reflect the perspective of a single provider. The lack of coordination between providers executing their individual schedules and, consequently, the lack of a holistic approach to urban traffic may cause further problems. Various stakeholders may have conflicting objectives. This chapter presents a multi-objective formulation of a multi-provider heterogeneous vehicle 2E-VRP from a city government perspective, demonstrating the potential benefit of this approach to all parties involved, simultaneously considering conflicting objectives. Additionally, the design and development of a multi-objective evolutionary algorithm (MOEA) for the formulated problem is presented. An experimental evaluation considering real data from Ecuadorian cities is presented to validate the proposed MOEA, demonstrating that it is capable to find good quality solutions, is scalable, and its solutions are improved throughout its execution.
TopIntroduction
Current trends of urbanization and growing economies bring with them rising levels of traffic congestion in cities, especially if the potential development of urban infrastructure is limited, due to costs, popular resistance to large-scale construction projects, or natural accidents such as mountains, estuaries, or rivers (e.g. Guayaquil). If the infrastructure cannot be adequately expanded to absorb the rise in traffic, national and city governments need new strategies that optimize vehicle routing to deal with such problems (Cattaruzza et al., 2017). One possible strategy, already employed by individual businesses and transportation companies, is multi-level distribution of urban goods. This chapter presents a framework using the Two-Echelon Vehicle Routing Problem (2E-VRP) in order to design a multi-level distribution strategy from a holistic perspective, useful for city governments Eitzen et al., 2017; Lopez-Pires et al., 2018).
The classic Vehicle Routing Problem (VRP) consists in serving a number of customers located at distinct geographic points, and to do so, a central depot and a fleet of vehicles are provided. To solve this problem, routes must be assigned, meaning ordered sets of clients, to the vehicles in the most optimal way possible, usually striving for the minimal cost to cover the demand, which is in most cases resumed to a total travel distance minimization (Toth and Vigo, 2014). However, distance minimization is not the most suitable approach in city logistics, where travel times, but also cost and pollution issues are more important criteria for both public and private stakeholders (Gonzalez-Feliu, 2018a, 2019).
Under certain circumstances there may be reasons to use multi-stage distribution systems, i.e. to not to serve the clients directly from the central depot but to use intermediary platforms (in the form of city distribution centers (CDCs), proximity delivery areas or other forms of urban logistics spaces). This can happen for example if there are large trucks that leave the central depot but should not (or are even forbidden to) enter a certain zone, such as the inner city, and CDCs are set up outside or on the edges of these restricted areas where the large trucks unload their freight and smaller vehicles deliver the freight to the customers within the restricted areas (Crainic et al., 2004). In this case, it can be said that there are two layers or echelons of vehicles and locations, giving rise to the 2E-VRP.
The most studied approach for the 2E-VRP considers a multi-level distribution scenario for products of a single provider (Gonzalez-Feliu, 2011, 2013; Cuda et al., 2015). However, each provider in a city solving its own routing problem separately and independently of the others could result in suboptimal solutions for the city as a whole. Furthermore, a city government may have the goal of reducing traffic congestion and pollution, requiring a holistic perspective of Urban Goods Transport (Cattaruzza et al., 2015), considering all stakeholders contributing to city traffic (Gonzalez-Feliu, 2018a,b).
For this reason, one can consider the 2E-VRP as a multi-level distribution scenario with multiple providers and products, also known as multi-commodity (Hernandez-Perez and Salazar-Gonzalez, 2014). This holistic approach that reflects the diverse nature of urban traffic is better adapted to tackle the global problem of urban traffic congestion. In this way, instead of solving several parallel 2E-VRP instances that are not aware of each other, one for each provider or product, a city government can unify these instances by having all (or several) providers share all (or several) CDCs, from where (possibly independent) smaller, greener second-echelon vehicles carry diverse freight to serve the demand of clients in restricted areas.