关键词: 迭代局部搜索, 多行程, 不相容货物, 辅助分割过程

Abstract: In order to solve the multi-trip vehicle routing problem with time windows and incompatible commodities, it is necessary to make a routing planning to serve a set of customers that require products belonging to incompatible commodities. Vehicles are allowed to perform several trips during the working days. The objective is to minimize the number of used vehicles. Through the creation of giant tour, this paper proposes an auxiliary segmentation process and an improved iterated local search algorithm to obtain the solution. Under the limitation of multiple related constraints, the vehicles have realized the goods delivery with the minimum quantity and the shortest trips within the given time window. Moreover, the paper conducts an analysis on the advantages that can be obtained from the multi-trip aspect at the fleet dimension level. Results on classical VRPTW instances show that, in some cases, the fleet can be halved to reduce the operational cost to maximum extent.

Key words: iterated local search, multi-trip, incompatible commodities, auxiliary segmentation process