可折叠集装箱接驳运输问题的建模与优化

对一类带时间窗的可折叠箱接驳运输问题进行了研究,其中使用可折叠箱在堆场与客户之间集散货物,一辆集卡可装载一个满箱或多个空箱,目标为集卡总工作时间的最小化.借鉴确定的活动在顶点上的图的思想,将该问题分解为满箱子问题和空箱子问题,其中满箱子问题类似于带时间窗的多旅行商问题,空箱子问题因客户的货物量可为负值而显著区别于车辆路径问题,且两个子问题之间存在访问时间耦合等关联.进而建立了问题的数学描述,设计了问题的主动禁忌搜索(reactive tabu search,RTS)求解算法,并基于随机生成的大量算例验证了算法的有效性.结果表明,相比于使用CPLEX等优化软件,RTS算法可以在更短的时间内求得问题的更优解;相比于使用标准箱的情形,使用可折叠箱可节省约13%的接驳成本.

Modeling and optimization of a drayage problem with foldable containers

This paper investigates a drayage problem with foldable containers and time windows. In this problem, foldable containers are used to collect and distribute freight between customers and the depot, and a truck could carry one loaded container or several (folded) empty containers. The objective of this problem is to minimize the total working time of trucks. Inspired by the determined-activities-on-vertex graph, the problem is decomposed into a loaded container sub-problem and an empty container sub-problem. The former one is similar to multi-traveling salesman problem with time windows. The latter one differs from vehicle routing problem because the amount of freight of customers could be negative. Furthermore, they couple each other in several aspects such as the visiting time of customers. The problem is mathematically formulated and then solved based on reactive tabu search (RTS) algorithm. A large number of randomly generated instances validate the model and algorithm presented above. The results indicate that the RTS algorithm can provide much better solutions of the problem in a much shorter time than typical optimization software such as CPLEX and that the use of foldable containers can save approximately 13% of drayage costs compared to the use of standard containers.