Abstract: The container drayage transportation problem is one hot point in international academic fields. A type of container drayage transportation problem considering multi-size containers is studied. Using a state-transition-based modeling method, this problem is formulated as a sequence-dependent multiple-traveling salesman problem with social constraints. Given the fact that personal computers with multiple cores of CPUs, including the computers with multiple CPUs, have been applied very widely, we design a multi-phase parallel reactive tabu search (PRTS) algorithm. The algorithm is validated extensively based on randomly generated instances. Results indicate that, compared with classical serial-implemented reactive tabu search algorithms, the PRTS algorithm can provide better solutions in shorter running time under the same computational environment.

Key words: Parallel, reactive tabu search, container drayage transportation, mathematical modeling

摘要： 集装箱接驳运输问题是目前国际学术界的一个研究热点，对一类考虑多尺寸集装箱的接驳运输问题进行了研究。基于状态转换的方法，该问题可被描述为一类带社会约束的序列依赖的多旅行商问题。考虑到多核计算机（包括多处理器计算机）的应用日益广泛，设计了一种多阶段并行主动式禁忌搜索算法，基于大量随机生成的算例对算法的性能进行了测试。结果表明：与经典的串行主动式禁忌搜索相比，该算法可以在现有计算环境下在更短的时间内求得更好的解。

关键词: 并行, 主动式禁忌搜索, 集装箱接驳, 数学模型