An Evolutionary Local Search for the Capacitated Vehicle Routing Problem Minimizing Fuel Consumption Under Three-dimensional Loading Constraints

This paper introduces and solves a new practical variant of integrated routing and loading problem called the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints (3L-FCVRP). This problem requires to design routes for a fleet of homogeneous vehicles located at the central depot to serve all customers, whose demand are formed by a set of three-dimensional, rectangular, weighted items. Different from the well-studied problem: capacitated vehicle routing problem with 3D loading constraints (3LCVRP) in literature, the objective of 3L-FCVRP is to minimize the total fuel consumption instead of travel distance. The fuel consumption rate is assumed to be proportionate to the total weight of the vehicle. A route is feasible only if a feasible loading plan to load the demanded items into the vehicle exists and the loading plan must satisfy a set of practical constraints. To solve this problem, the evolutionary local search (ELS) framework incorporating with recombination method is employed to explore the solution space and an open space based heuristic is used to examine the feasibility of solutions. To verify the effectiveness of our approach, we first test ELS on the instances of 3L-CVRP, which can be seen as a special case of 3L-FCVRP. The results demonstrate that ELS outperforms all existing approaches on average and improves the best known solutions for most of the instances. Then, we generated data for 3L-FCVRP and reported the detailed results of ELS for future comparisons.