دانلود رایگان مقاله الگوریتم کلونی مورچه مبتنی بر اتیکت برای مسیریابی وسیله نقلیه ناهمگن

Abstract

Vehicle heterogeneity and backhaul mixed-load problems are often studied separately in existing literature. This paper aims to solve a type of vehicle routing problem by simultaneously considering fleet heterogeneity, backhaul mixed-loads, and time windows. The goal is to determine the vehicle types, the fleet size, and the travel routes such that the total service cost is minimized. We propose a multi-attribute Label-based Ant Colony System (LACS) algorithm to tackle this complex optimization problem. The multi-attribute labeling technique enables us to characterize the customer demand, the vehicle states, and the route options. The features of the ant colony system include swarm intelligence and searching robustness. A variety of benchmark instances are used to demonstrate the computational advantage and the global optimality of the LACS algorithm. We also implemented the proposed algorithm in a real-world environment by solving an 84-node postal shuttle service problem for China Post Office in Guangzhou. The results show that a heterogeneous fleet is preferred to a homogenous fleet as it generates more cost savings under variable customer demands.

6. Conclusion

This paper formulates and solves a class of vehicle routing problems considering vehicle heterogeneity, backhauls, mixed-load, and time windows. Both linehauls and backhauls can be served in random order. Our study intends to fill the research gap where vehicle heterogeneity and backhaul mixed-loads are often handled separately. A two-stage label-based ant colony optimization algorithm is developed to minimize the total travel cost. That is, in stage one we optimize the vehicle type and vehicle quantity, and in stage two we further optimize the travel routes based on the previous stage decision. The proposed hybrid algorithm possesses the multi-attribute labeling features and the swarm intelligence, and its advantages are demonstrated in terms of global optimality and computational time. The real-world case study in China Post of Guangzhou shows that a heterogeneous fleet of vehicles can lower the service cost up to 9.2% than a homogeneous fleet. As of future research efforts, we want to extend the algorithm to more general situations including periodic vehicle assignment, and simultaneous pickup and delivery in a multi-depot environment. We also wantto tackle the problem by using directly multi-objective evolutionary algorithm to obtain the non-dominant solution set, and the results can be further compared with the ant colony algorithm in terms of computational time and global optimality.