A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint. (November 2015) - Wang, Zheng; Li, Ying; Hu, Xiangpei
Highlights: Presenting the vehicle routing problem with an incompatible loading constraint. Integrating an insertion-based idea into the saving-based method. Developing a ruin-recreate heuristic and a threshold tabu search. Abstract: A generalization of the traditional vehicle routing problem – the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint (HVRPTW-ILC), is studied in this paper. Besides the common constraints of heterogeneous multi-type fleets and time windows, the incompatible loading constraint is also an important and unavoidable problem in a large number of deliveries to supermarket chains and department stores. This constraint originates from the fact that logistics companies often use heterogeneous multi-type fleets, like refrigerated and non-refrigerated vehicles, to transport various goods, some of which should be transported by a certain type of vehicles while others should not. To our knowledge, this is the first time that such constraint is addressed. To solve this problem, we develop a mathematical model, a ruin-recreate heuristic algorithm, and a threshold tabu search method. Furthermore, we conduct a series of experiments over a set of existing vehicle routing problem with time windows (VRPTW) instances, as well as analyze a real case in China to evaluate and demonstrate the effectiveness of the two proposed algorithms.