A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint

• 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.

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.