A label based ant colony algorithm for heterogeneous vehicle routing with mixed backhaul

• Vehicle routing with fleet heterogeneity, mixed delivery and pickup, and time windows.
• Proposing a two-stage, meta-heuristic ant colony system algorithm.
• Jointly optimizing the vehicle type, the vehicle number, and the travel routes.
• A heterogeneous fleet may result in larger cost savings than a homogenous fleet.

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.

Figure optionsDownload as PowerPoint slide