Decomposition-based Matheuristics for Green Vehicle Routing Problems

The fast development of logistics industries has encouraged an increase in the sharing of logistics resources as well as in the reduction of environmental pollution in freight transport. Although transportation companies are relevant drivers of economic growth, they are one of the leading causes of carbon dioxide emissions. The transportation of goods impairs local air quality, produces noise and vibration, and contributes significantly to global warming. This circumstance has been widely studied in green logistics, which considers the efficient use of resources within logistics activities and the modification of distribution strategies. The central purpose is to minimize energy use, reduce waste, and properly manage its treatment in order to achieve an eco-friendly, respectful, and sustainable transport scheme that reduces environmental and social impacts within logistic operations.

Nowadays, many companies still need to efficiently address the transportation of pickup or/and delivery of goods over the routes. The complexity of planning routes that optimize transportation costs by satisfying a large number of restrictions generates challenging problems that involve vehicle fleets in the industry. Moreover, adopting environmental aspects in transport plans requires extensive analysis to harmonize environmental costs and financial costs. This encourages studying and developing optimization techniques involving mathematical programming models and algorithms to assist fleet managers and decision-makers when planning transportation operations.

This thesis is positioned within green logistics and computational logistics areas, especially in problems related to green vehicle routing problems (GVRP) and resolution hybrid algorithms. The GVRPs are characterized by incorporating factors concerning the environment, such as energy consumption, emission reduction, and noise mitigation. In order to fully grasp and map the GVRP variants and how the algorithms have been used to solve them, an in-depth study of heuristics and hybrid algorithms for solving GVRPs considering emissions is presented. For each variant of GVRP, we discussed how the emissions are addressed by presenting the main characteristics related to the compositions of the restrictions, objectives, emission models, and types of emissions. Also, we reported the heuristics’ main features and heuristics hybridizations developed for solving these problems by highlighting the leading strategies and methodologies employed in each solution method. Lastly, we indicated a detailed description of the benchmark instances proposed in the related literature and used it to assess the algorithms’ performance.

Based on the study carried out, we proposed two studies that consider novel emerging GVRP variants. The first study defined the cumulative vehicle routing problem with time windows (CumVRP-TW), intending to minimize a given cumulative cost function while respecting customers’ time window constraints. The CumVRP-TW considered two types of time windows, i.e., soft time windows (CumVRPSTW) and hard time windows (CumVRP-HTW). For each version, we formulated a mathematical model for solving small-sized instances of the problem, while a matheuristic decomposition algorithm was presented for solving all instances’ sizes. The last approach was based on a cluster first-route second approach by considering the integration of a greedy randomized adaptive search procedure (GRASP) with each mathematical model. The solution approaches are tested on instances proposed in the literature as well as on a new benchmark suite proposed for assessing the soft time windows variant. The computational results show that the mathematical formulations provide optimal solutions for scenarios of 10, 20, and several 50 customers within suitable computational times. Nevertheless, the same performance is not observed for several medium as well as for all large scenarios. In those cases, the proposed matheuristic algorithm is able to report feasible and improved routes for those instances where the exact solver does not report good results. Moreover, we verify that fuel consumption and carbon emissions are reduced when the violation of the time windows is allowed in the case of soft time windows.

The second study proposed the multi-depot green vehicle routing problem with pickup and delivery operations (MDGVRP-PD), where the objective was to construct a set of vehicle routes considering multiple depots and one-to-one pickup and delivery operations that minimize emissions through fuel consumption. The way emissions were determined during the route depended on weight and travel distance. To solve this problem, a mathematical model and a matheuristic approach based on a clustering procedure and a partial optimization metaheuristic under special intensification conditions (POPMUSIC) framework were proposed. To validate the previous approaches, we proposed modified benchmark instances based on the literature on pickup and delivery VRPs and addressed inherent characteristics related to real locations considering pickup and delivery partner association in multi-depot contexts.

The results show that if the weight carried on the routes as part of the fitness measure is considered, our matheuristic approach provides an average percentage improvement in emissions of 30.79%, compared to a fitness measure that only takes into account the distances of the routes. The results shown in this thesis indicate that the management of green routing problems by means of decomposition approaches is beneficial for reducing emissions while showing competitive time performance. In this regard, the literature analysis reports the relevant impact that the matheuristic methods, such as those proposed in this thesis, have on solving different variants of GVRPs. Furthermore, the definition of new GVRPs permits evaluating the impact of cumulative cost through arcs and the soft and hard time windows concerning fuel consumption. Lastly, the results on decomposition matheuristics indicate that they are suitable and comprehensive solution approaches to solve GVRPs.