A Hybrid Meta-heuristic For The Heterogeneous Fleet Capacitated Vehicle Routing Problem With Two-dimensional Loading Constraints

With rapid development of economics, logistics has become a new value-added service industry with broad prospect, which has obvious impact on economic activity of the world day by day. The key part of logistics is transportation and delivery, which takes more than half of the logistics cost. The objective of the vehicle routing problem (VRP), which researches on how to optimize the vehicle routes, is to save the transportation cost. In the past fifty years, vehicle routing problem has attracted much research interest. Many research results have been obtained.This paper mainly addresses the heterogeneous fleet capacitated vehicle routing problem with two-dimensional loading constrains(2L-HFCVRP). The2L-HFCVRP is a combination of the two most important problems in distribution logistics, which are the capacitated vehicle routing problem (CVRP), and the well-known two-dimensional bin packing problem (2BPP). Since both of the problems are NP-hard problems, it is obvious that it’s difficult to solve the2L-HFCVRP. A hybrid meta-heuristic algorithm, which is a combination of Artificial Bee Colony (ABC) algorithm and Artificial Immune System (AIS) algorithm, to solve the2L-HFCVRP is presented in this paper. This paper adopts a heuristic packing algorithm based on score rule to check the feasibility of loading constrains. When constructing the initial solution, a quick method is used. While the hybrid meta-heuristic algorithm is running, the legal solution space and illegal solution space are both allowed. The extensive computational results prove the effectiveness of the algorithm. The proposed algorithm can provide better solution than other known algorithms.The proposed hybrid meta-heuristic algorithm is also applied to the two-dimensional loading capacitated vehicle routing problem (2L-CVRP), which can be treated as a special case of2L-HFCVRP. The2L-CVRP is proposed earlier and studied well. The meta-heuristic algorithm framework, with revised the initial solution constructing method and the objective function, is developed to solve2L-CVRP. The experiment results demonstrate that the proposed algorithm is efficient.