An Adaptive Variable Neighborhood Search for a Heterogeneous Fleet Vehicle Routing Problem with Three-Dimensional Loading Constraints

摘要

The paper addresses the heterogeneous fleet vehicle routing problem with three-dimensional (3D) loading constraints (3L-HFVRP), a new practical variant of the combined routing and loading problem. In this problem, the loads consist of a set of three-dimensional, rectangular shaped items. The fleet is composed of heterogeneous vehicles with different weight and space capacities. The objective is to serve all customers by selecting a set of vehicles such that the total transportation cost is minimized. The cost consists of the fixed cost of the selected vehicles and their travel cost. In addition, loading sequence related constraints frequently encountered in realistic applications are respected when loading and unloading the items. To solve this challenging problem, we develop an adaptive variable neighborhood search (AVNS) which utilizes an extreme point based first fit heuristic to find a feasible loading pattern for each route. We design two strategies to accelerate the loading and routing processes. The Trie data structure is used to record the loading information of routes already visited and to control the computational effort spent for each route. The Fibonacci heap data structure is used to maintain all of the possible moves and vehicle type assignments, which avoids the duplicated evaluation of some moves and unnecessary loading check of unpromising solutions. The robustness and effectiveness of the proposed algorithm is validated by computational tests performed both on some newly generated 3L-HFVRP instances and well-known benchmark instances from the literature for two simplified VRP variants: the capacitated vehicle routing problem with 3D loading constraints (3L-CVRP) and the pure heterogeneous fleet vehicle routing problem (HFVRP). The numerical experiments show that the proposed AVNS outperforms other algorithms in 3L-CVRP and improves several best known solutions reported in the literature. The results obtained for the pure HFVRP are very close to t- e best known solutions.