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)

• Record Type: Journal Article
• Authors: Wang, Zheng; Li, Ying; Hu, Xiangpei
• Is Part Of: Computers & industrial engineering. Volume 89(2015)
• Page Start: 162
• Page End: 176
• Publication Date: 2015-11
• Subjects: Vehicle routing problem -- Heterogeneous multi-type fleet -- Time windows -- Incompatible loading constraint -- Ruin-recreate heuristic -- Threshold tabu search; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2014.11.004
• Languages: English
• ISSNs: 0360-8352

Abstract

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.