多堆场集装箱卡车路径规划的混合蚁群算法

Hybrid Ant Colony Algorithm for Multi-Depot Container Truck Transportation Problems

为提升集装箱运输系统的运输效率,以进口港口为背景,研究了多堆场集装箱卡车运输路径规划问题。通过图建模将问题转化为非对称多旅行商问题,建立了带时限约束的以最小化总工作时间为目标的线性混合整数规划数学模型。鉴于问题的复杂性,提出了给定序列的动态规划分割算法以及生成序列的改进蚁群算法,以此构造了求解该问题的混合蚁群算法。数值实验表明,混合蚁群算法在优化性能上明显优于禁忌算法和遗传算法,是求解该类问题的有效算法。

In order to boost the efficiency of container truck transportation, the multi-depot container truck transportation problems were investigated for the import-dominated container terminal. The original problem was initially transformed into an equivalent multi-traveling salesman problem by means of graph modeling, and then was formulated as a linear mixed-integer programming with the objective of minimizing total completion time in the presence of time constraints. For the resolution, a hybrid ant colony algorithm was developed, which exploits an improved ant colony algorithm to attain a set of visiting sequences and designs a dynamic programming to partition the derived sequences to get feasible schedules. Computation experiments demonstrate that the proposed algorithm is advantageous over tabu search and genetic algorithm and thus can be applied to efficiently solve the problem.