多堆场集装箱卡车路径规划的混合蚁群算法
发布时间:04-15-19

张建同,宋玉坚,叶春明

《工业工程与管理》第22卷第2期 2017年4月

推荐理由

集装箱运输作为一种高效率高质量的运输方式,已经迅速普及成为海运业务的主要运输模式。这项研究以进口为主的港口为背景,通过研究多堆场集装箱卡车运输路径规划问题,提出了一种融合动态规划算法的改进蚁群算法求解策略,以促进集装箱运输系统的运营效率提升和成本节约。

作者简介

张建同:同济大学经济与管理学院教授,博士生导师,研究方向为工业流程优化与管理。
宋玉坚:同济大学经济与管理学院
叶春明:上海理工大学管理学院

关键词

集装箱卡车运输 图建模 动态规划 改进蚁群算法

内容简介

世界经济的发展及其国际贸易规模的不断扩大,极大推动了作为其派生需求的运输服务业的发展,特别是承担国际贸易约80%的货物运输量的海运已经成为了世界经济的大动脉。集装箱卡车运输作为整个集装箱运输流程一部分,是指港口、内陆堆场和终端客户之间相对短距离但只能由卡车完成的运输环节,其运作效率会严重影响整个运输系统的绩效。同时,据统计短距离的集装箱卡车运输单位成本远远高于长距离的海上航线,并且集装箱卡车运输成本占集装箱总运输成本的30%。因此,为了提高整个运输系统的运营效率以及节省运作成本,有必要对集装箱卡车运输路径进行优化。

相关领域的专家学者针对集装箱卡车运输路径问题在模型构建和算法设计方面展开了一系列的研究。本研究则创新性地通过图建模将问题转化为非对称多旅行商问题,其次建立了带时限约束的以最小化总工作时间为目标的线性混合整数规划数学模型,并鉴于问题的复杂性,提出了一种融合动态规划算法的改进蚁群算法求解策略。该算法采用动态规划算法对给定访问序列进行分割,通过蚁群算法搜索最优访问序列。

为了提升算法优化性能,本文从初始解构造、优选列表、信息素更新机制和局部搜索策略4个方面改进了基本蚁群算法。首先采用最近邻法生成初始解,提高初始解的质量;其次设计蚂蚁优选列表提高计算资源利用率;然后改进信息素更新机制防止算法过早收敛陷入局部最优;最后针对问题特点设计了局部搜索策略提高解的质量。数值实验的对比分析结果验证了算法及其改进策略的有效性。