基于动态蚁群算法的集装箱国际多式联运路径优化研究，本文主要内容关键词为：集装箱论文,算法论文,路径论文,多式论文,动态论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
一、引言
多式联运是一种先进的交通运输组织形式，能够有机地集成多种运输方式的综合优势，形成高效、便捷和安全的运输服务网络，为货主提供“门到门”的物流服务。特别是以集装箱为载体的多式联运不仅大幅降低了国际物流成本、提高了运输效率，更重要的是它能够通过物流系统各环节无缝衔接，使国际产业链高效运行，更好地满足物流需求向快速化、准时化趋势发展的要求。
快速增长的国际集装箱量和国际物流服务品质要求的提高，给多式联运的运营提出了一系列新的挑战，如何按照现代物流的发展要求，为货主寻找最佳的运输线路，设计符合其需求的联运方案，提供低成本、高效率的方式组合，以更好地提高顾客满意度，已成为多式联运发展中面临的核心问题。而与其他优化问题相比，多式联运的最优路线选择面临变量较多和网络高复杂性的困扰，以往研究采用的层次分析法[1]、区间权重法[2]、组合优化法[3]等大多仅适用于小范围网络的求解，近年来也出现了一些采用智能算法如遗传算法的研究[4-6]，但大多是基于算法的概念性应用，与现实运作存在一定差距，亟需开发相关的优化方法为多式联运的规划和设计提供支撑。
蚁群算法(Ant System algorithm)是由M.Dorigo等(1991)首先提出的一种模拟蚂蚁群体觅食行为的新型仿生类随机型搜索算法[7]。该方法能够将一些离散系统优化中的困难问题用蚁群在搜索食物源的过程中所体现出来的寻优能力进行有效解决。较之以往的启发式算法，在搜索效率和算法的时间复杂性上都取得了令人满意的效果。因此蚁群算法诞生仅20多年就在TSP问题[8]、网络中的负载平衡问题[9]、车辆路径问题[10]等领域得到广泛应用。本文对传统蚁群算法进行改进，通过权系数、信息素残留和挥发系数的动态化，建立了适用于国际多式联运这一特殊复杂系统的路径优化动态蚁群算法模型，有效改善了模型的寻优过程，并采用天津港—墨西哥城的集装箱运输实际数据进行实证分析和验证。
二、集装箱国际多式联运的网络系统构成
目前的集装箱国际多式联运主要是以大型集装箱枢纽港为中心，通过铁路、公路、内河水路等多种运输方式，将集装箱货流的吸引范围延伸到港口的内陆腹地，在取得规模运输效益的同时，实现“门到门”的物流服务。其实际流程是首先把分散的货主处的小批量货流汇集到若干内陆集装箱中转站，组成大批量货源后，通过铁路或汽车运送到各起运港的集装箱码头堆场，再通过大型集装箱船舶以海运的形式运到各个目的港集装箱码头，在目的港卸下后通过各种方式将集装箱运到沿海的支线港或内陆的集装箱中转站，经过若干次转运后，最后配送到收货人手中。
国际多式联运网络是一个庞大且复杂的系统，不仅涉及到由多种方式构成的运输过程，同时涉及到在港口、码头/堆场、中转站等各种节点的方式转换过程，此外还受到不同国别通关、检验检疫、贸易壁垒等多重因素的影响。因此，多式联运网络相较于一般运输网络具有更高的复杂性。具体可以归纳为：
1.运输网络都是由点与弧构成的，节点之间通过有向弧相关联，弧长一般由路线上的距离、运费或时间来表示。以往的运输网络分析通常仅考虑一种运输方式，弧长为单一固定值。但在多式联运网络中，由于多种运输方式的存在，节点之间通过多重有向弧相关联，弧长也由于不同方式费用和时间的差别而不等。
2.以往关于运输网络的研究中，节点处的费用或忽略不计、或为某一固定的中转费用，而在多式联运网络中，由于涉及到不同方式转换，并考虑到在不同国别之间单证手续等诸多因素影响，不同的方式、不同的路线之间的转换费用也各不相同。
因此，本文将国际多式联运网络看作由多种运输方式组合交叉所共同构建的复杂网络结构。其抽象结构如图1所示。
图1 多式联运运输网络模型示意图
假设在某区域中，一批货物从起始点O运送至目的地D，途中共有n个多式联运节点可供选择，这些节点用a[,i](i＝1，2…，n)表示，每两个节点之间都有l种运输方式，加上两个起讫点就形成了图中所示的(n＋2)×l层结构的运输网络。每个节点均能够实现货物在不同方式之间的转换。转换的过程中会发生相应的转换费用，如果涉及到跨国运输，还包括相关的通关、检验检疫等费用。这一费用既可以理解为消耗的运输、仓储、单证等费用，也可以是所花费的时间，或是二者的叠加。因此，为了实现全程费用最小，承运人就需要从诸多的运输节点和各种运输方式中组合优化自己的流程。
三、动态蚁群算法的模型设计
(一)基本蚁群算法
意大利学者M.Dorigo等通过观察蚂蚁群体觅食的生态行为发现，蚂蚁之间是通过外激素——信息素(Pheromone)进行间接交流而达到合作目的的。蚂蚁可以在一定范围内察觉到这些信息素并由此影响它们以后的行为。它们会根据信息素的浓度在行进的途中选择路径，即信息素浓度越大的路径，被蚂蚁们选择的概率就越高，这条路径上被留下的信息素也越来越多，因此该路径的信息素强度将逐渐增大；另一方面，随着时间的推移，信息素会逐渐挥发，被蚂蚁很少选择的路径的信息素浓度将会越来越低。因此当大量蚂蚁进行这种觅食行为时，就会表现出一种信息正反馈的现象，并指导蚂蚁最终搜索到一条从蚁穴到食物源的最短路径。
本文采用典型的TSP(旅行商)问题来说明蚁群系统基本模型。TSP问题通过寻找将n个城市全部各通过一次并在最后回到出发地的最短路径，常常被用来证明某一算法的有效性。以最常用的蚁周模型(Ant-cycle System)为例，模型首先将m只蚂蚁随机置于n个城市上，位于城市i上的蚂蚁k在t时刻以
为概率选择下一个未访问城市j，这个概率由公式(1)决定
当蚂蚁完成环游，按公式(2)、(3)、(4)进行信息素更新，使下次搜索可以更关注最短路径。基本蚁群算法的信息素更新包括局部更新和全局更新，而实验表明，全局更新比局部更新有更好的效果[11]。因为全局更新考虑了所有蚂蚁在每次循环后的结果，隐含了信息反馈，使得算法更容易趋于最优，因此本文的模型中也取消了局部更新，仅当全部蚂蚁完成整个一次循环再计算信息量增量，从而使算法较快地收敛到全局最优解，避免后期大量的无效搜索。
(二)动态蚁群算法的最短路径模型
在基本蚁群算法中，在蚁群个体数目较少的情况下，早期发现的较好解在正反馈的作用下将以递增的概率引导蚁群走向局部最优解，而这条可能是离最优解相差很远的路径，由于最优路径上的信息得不到应有的增强，会阻碍以后的蚂蚁发现更好的全局最优解，从而容易陷入局部最优。而且由于模型中主要参数的设置大多凭借经验，一旦设计不当，则进一步加剧了局部最优解的正反馈效应。因此，一系列改进蚁群算法相应提出，如Stützles和Hoos(2000)提出的MMAS(maxmin Ant System)算法[13]，Dorigo和Gambardena(1997)提出的混合蚁群算法(HAS)[12]等。为了提高算法的全局收敛能力，本文设计采用动态蚁群算法对基本算法进行以下改进。另外，本文所探讨的联运路径优化问题无需像基本TSP问题遍历所有节点，因此可以归纳为从起始地到目的地的最短路问题，在路径设计中，也需对基本模型的搜寻规则进行一定调整。
1.权系数的动态调整
在基本蚁群模型和MMAS模型中，α、β均为固定参数，α的大小表明每个路段上的信息素量的受重视程度，其值越大，蚂蚁选择以前走过的路径的可能性越大，α值过大会使搜索过早陷于局部最优。β的大小反映了蚂蚁在路径搜索中先验性、确定性因素作用的强度，其值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中随机性减弱，也易陷入局部最优。由此可见，α值过大造成的局部收敛效果尤其会在循环后期作用加强，而β值过大的局部收敛效果在前期的作用较强。因此，α后期应较小，β前期应较小，故α与β的比值应随着时间的推移呈递减函数。为简化计算，设α＝1，而将β按迭代次数定义为如下分段函数：
其中IL为当前迭代次数，TotalIL为总迭代次数。
2.设计信息素动态调整的上下限
四、集装箱国际多式联运算法的实现及优化实例
(一)算法的具体实现步骤
在多式联运的网络系统中，由于涉及l种运输方式，使得多式联运的问题的节点数个数特征为一般网络问题的l倍，中途n个城市加上起讫点，则此问题节点数为(n＋2)×l个，如用传统网络算法，将这些节点均视为蚂蚁可自由选择的转移节点，则使得问题的复杂度大大增加，影响计算速度。因此，本文将此问题转化为两阶段来进行解决。问题的城市节点个数仍定义为n＋2个，而将每个方式下的l种方式视为其从属节点。节点选择的概率原理仍与公式(1)相同。但是每个蚂蚁从每个节点出发的过程需进行条件判别，设蚂蚁当前所在的运输方式为h1，如果方式不变，则可见度
步骤2 将m只蚂蚁随机置于起始点O的l个方式从属节点，将各蚂蚁的初始点O置于当前解集
(s)。
步骤3 对每个蚂蚁k(k＝1，2，3，…，m)，按公式(1)计算到其他节点的各方式从属节点的转移概率，如果方式相同的，用该方式下的两点间运费计算可见度；方式不同的，用该方式下两点间运费与方式转移费用之和计算可见度。
步骤4 根据转移概率采用轮盘赌法随机选择下一节点j，再将j置于当前解集(s)里。
步骤5 如果蚂蚁k抵达终点D，停止前进；如果蚂蚁k未抵达终点，重复实施步骤(3)，(4)，直到所有蚂蚁到达终点。
步骤6 求解并保留本次循环的最优解。
(二)天津港—墨西哥城多式联运路径优化实例
目前集装箱国际多式联运路线主要是以世界三大主干航线为核心的，即太平洋航线、大西洋航线和远东/西北欧/地中海。本文选取太平洋航线中两个新兴地区间的多式联运路线作为代表，起点是中国的北方航运中心——天津港，终点是拉丁美洲北部城市——墨西哥城。由于墨西哥城位于内陆，并且加勒比海周边区域港口和内陆中转节点众多，这一路线具有明显的多式联运特征。由于新兴经济体的崛起，这一路线集装箱量近年来迅猛增长，即便是在金融危机期间全球集装箱量负增长的环境下，这一线路依然保持一定的增幅。
在这一运输过程中，多式联运路径重点考察了墨西哥城周边可选择的港口和内陆中转站，包括曼萨尼略、拉查罗卡地那斯、巴尔博亚、危地马拉城、圣何塞、哈瓦娜和维拉克鲁兹。加上天津港和墨西哥城，共9个城市节点。运输方式主要考虑三种，即水运、公路和铁路。在多式联运下总物流费用既包括方式从属节点间的运输费用，也包括在节点上方式转换过程中由于装卸、堆存和报关等所发生的费用。因而，在既定的运费结构下合理进行路径和方式节点的选择是降低全程物流费用的关键。各城市的方式从属节点间物流费用矩阵(包括了运费以及节点上的报关费、装卸费、堆场服务费等)如表1。某些节点由于地理条件限制，可能仅有一或两种运输方式，其他方式则在表中省略，故表中罗列了9个城市和12个方式从属节点。表中“－－”表示在网络中部分节点之间不具备通行条件的路径，在程序中将其设置为极大惩罚值
处理。
基于上述动态蚁群算法，采用Matlab编写程序，在步骤(1)完成算法的参数设置：蚂蚁数量m等于各城市方式从属节点个数12，总迭代次数TotalIL＝200次，信息素量初始值C＝100，信息素增量Q＝10，
＝0.1，根据表1设置
矩阵；在步骤(2)中建立用于蚂蚁在12个方式从属节点间行走记录的矩阵，并设定初始节点；在步骤(3)中按照公式(1)计算每只蚂蚁访问剩余节点的概率，并在步骤(4)中采用轮盘赌选择法，通过随机数与累计概率的比较来确定目的节点，保证在步骤(3)中计算得出的访问概率较大的节点能够有较大的概率被选择为目的地；在步骤(5)中使蚂蚁重复步骤(2)、(3)直到12只蚂蚁全部抵达终点；在步骤(6)中计算各个蚂蚁的行走长度并找出本轮循环的最短路径；在步骤(7)中根据公式(2)结合信息素和挥发因子的限定条件进行信息素的更新；在步骤(8)中进行全局循环的设定，并根据全局循环次数更新β值，直到达到循环上限后，终止计算并输出最优解。
得出从天津港到墨西哥城的集装箱运输最优路径为：天津港—海运—拉查罗卡地那斯(海运)—方式转换—拉查罗卡地那斯(铁路)—墨西哥城。最后得到的最优路径的全程费用为2400美金/标准集装箱。本文对动态蚁群算法和基本蚁群算法对全程运费的迭代过程进行了比较，如图2所示。基本蚁群算法由于参数的固定性，收敛速度较快，但收敛过程较为突兀。在运算100次的结果中，平均最低运费为2415，得到最优路径的比例为85％，得出优化结果的平均步骤为72.3。而动态蚁群算法收敛速度相对较慢，得到优化结果的平均步骤为88.5，但结果稳定性较高，100次运算中平均最低运费为2403，得到最优路径的比例高达96％。由此可见，对于多式联运路径的优化问题采用动态蚁群算法能够大大提高算法的寻优能力。
五、结语
本文针对集装箱国际多式联运网络路径的特点，采用动态蚁群算法模型，较好地解决了多式联运问题中如何选择运输路径和运输方式以达到全程最小运费的问题。由于多式联运网络的复杂性，需对基本蚁群模型蚂蚁节点转移的方式进行改进，并设计动态蚁群算法对α、β、ρ关键参数进行动态调整。文章采用了天津港——墨西哥城的集装箱运输实际数据进行实证分析，结果表明，该算法能够有效找到全程费用最小的运输路径和运输方式，并且相较于基本蚁群模型，显著提高了寻优精度。但由于实证数据资料的限制，模型验证未能囊括更多的多式联运节点，当网络节点数目增多时，该方法还需进一步探讨验证。