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

作者：Wang, Zheng^*; Li, Ying; Hu, Xiangpei

来源：COMPUTERS & INDUSTRIAL ENGINEERING, 2015, 89: 162-176.

DOI：10.1016/j.cie.2014.11.004

• Vehicle routing problem
• Heterogeneous multi-type fleet
• Time windows
• Incompatible loading constraint
• Ruin-recreate heuristic
• 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.

• 出版日期2015-11
• 单位大连理工大学