An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints. (December 2015)

• Record Type: Journal Article
• Authors: Zhang, Zhenzhen; Wei, Lijun; Lim, Andrew
• Is Part Of: Transportation research. Volume 82(2015)
• Page Start: 20
• Page End: 35
• Publication Date: 2015-12
• Subjects: Routing -- Loading -- Evolutionary local search -- 3L-CVRP -- 3L-FCVRP; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2015.10.001
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: We introduce and solve a combined routing and loading problem aiming at minimizing the fuel consumption. We employ an evolutionary local search for exploring the solution space. We propose a novel open space based heuristic to examine the loading constraints. We outperform all existing approaches in numerical tests on 3L-CVRP instances. We generate new data for the proposed problem and report the results. Abstract: This study introduces a new practical variant of the combined routing and loading problem called the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints (3L-FCVRP). It presents a meta-heuristic algorithm for solving the problem. The aim is to design routes for a fleet of homogeneous vehicles that will serve all customers, whose demands are formed by a set of three-dimensional, rectangular, weighted items. Unlike the well-studied capacitated vehicle routing problem with 3D loading constraints (3L-CVRP), the objective of the 3L-FCVRP is to minimize total fuel consumption rather than 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 the recombination method is used to explore the solution space, and a new heuristic based on open space is used to examine the feasibility of the solutions. In addition, two special data structures, Trie and Fibonacci heap, are adopted to speed up the procedure. To verify the effectiveness of our approach, we first test the ELS on the 3L-CVRP, which can be seen as a special case of the 3L-FCVRP. The results demonstrate that on average ELS outperforms all of the existing approaches and improves the best-known solutions for most instances. Then, we generate data for 3L-FCVRP and report the detailed results of the ELS for future comparisons.