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