An improved label heuristic algorithm for multi-attribute vehicle routing problem

In this paper, we propose a new algorithm Label based Ant Colony System (LACS) based on the multi-attribute label (MAL) algorithm and multi ant colony system (MACS) algorithm to address the multi-attribute vehicle routing problem with heterogeneous fleet, backhaul and mixed-load (MAHVRPBM). Leveraging the object-oriented principle, we build multi-attribute labels for various customers (demands), vehicles and routes. And then, we construct a hierarchical objective structure which minimizes the number of vehicles required and minimizes the total travel length. To evaluate the efficiency of the LACS, we compare it with the other optimization algorithms using Solomon benchmark problems and random number data sets based on the benchmark extensions. Our results show that the LACS algorithm has significant advantages in achieving the objectives as well as computing time. In addition, a numerical simulation using the actual data from a China Post office in Guangzhou demonstrates the practicality of the LACS for solving a real world problem.