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

摘要： 为了解决运送不相容货物的带时间窗的多行程车辆路径问题，需要制定一个明确的路径规划来服务一组客户，以满足客户运送不相容的大宗货物的需求。车辆在工作日期间允许执行多个行程，目的就是最大限度地减少使用车辆的数量。通过创建巨网结构并采用辅助分割过程和改进的迭代局部搜索算法获得解决方案，在多个相关约束条件限制下，车辆实现了以最少的数量、最短的行程在规定的时间窗内送达货物，并从车队不同规模的角度分别介绍了采用多行程方式送货的优势。最后通过典型的带时间窗的车辆路径问题的实例分析表明，该算法在某些情况下可以使车队规模减半，从而最大程度上减少了运行成本。

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