多式联运路径优化模型与方法研究

1 引言 随着全球的经济发展，单一运输方式已不能满足运输市 场的需求，只有多式联运才能够很好的解决来自全球运输市 场的多方面的需求。多式联运是采用两种或者两种以上的运 输方式把货物从起始地运送到目的地。它是综合运输体系的 核心，在我国交通运输体系中发挥着重要的作用。多式联运的 路径优化有助于节省运输费用或节约运输时间，从而对提高 运输服务水平、竞争能力、社会综合效益具有重大意义。 随着物流技术的发展，以及多式联运需求的增加,国内外 学者对多式联运的路径优化研究也逐步深入。其中, Angelica Lozano等研究了多式联运下的最短可行路径问题,并通过顺序 算法进行求解 [1]；张建勇等从实现总成本最小化的原则出发, 建立了一种多式联运网络的最优分配模型,从定量角度分析了 多式联运系统的合理组织模式[2]；王涛等对多种运输方式的运 输特性进行分析后,提出了运输方式组合优化模型,并给出求 解算法[3]；王云鹏等对基于扩展 Petri网的多式联运流程进行了 研究[4]；Michel Beuthe研究了 10种货物类别在公 - 铁 - 内陆 水运组成的多式联运网络中成本最小的运输优化问题 [5]；刘 诚等研究了带软时间窗物流配送车辆路径问题的并行遗传算 法[6]；魏众等提出最短时间路径 - 运输费用模型[7]；Herminia I. Calvete研究了带软时间窗车辆路径问题, 提出了求解该问题 的目标规划法[8]；孙华灿等提出合理路径概念，建立了一个含 路径合理性约束的联合运输路径优化模型，指出除了运输效 益最大化外，合理的换装序列和换装次数限制是联合运输路 径选择和优化必须要考虑的因素[9]。上述研究构建的多式联运 网络模型是从不同的层面考虑的，存在着一定的局限性，有些 模型中仅以运输时间、运输成本或服务水平为单目标的情况 下，寻求满足条件的最优多式联运路径。没有考虑不同时间段 会引起运输时间和运输费用的改变，也没有考虑到交通流量 对运输的影响。有些研究忽略了货物换装的成本计算和货物 运到期限的约束，并假定运量在运输节点处不可分割，但在实 际中，如果某运输节点对某种货物有运输需求，则运量会在节 点处发生变化。为此，本文研究运量在某运输节点发生变化情 况下，如何进行多式联运路径的优化，运用双目标整数规划理 多式联运路径优化模型与方法研究 佟 璐，聂 磊，付慧伶 （北京交通大学 交通运输学院， 北京 100044） [摘 要]考虑到多式联运路径的选择受到运输成本、运输时间、运输质量和服务水平等相关因素的影响，将多式联运的路径 优化问题转化成为一个广义最短路径问题，以成本和时间为优化目标建立了适应运量变化情况下的多式联运路径优化数学模 型，并选择蚁群算法对实际问题进行了求解验证。 [关键词]多式联运；路径优化；最短路径；蚁群算法 [中图分类号]F224.0 [文献标识码]A [文章编号]1005- 152X（2010）05- 0057- 04 Research on Optimization Model and Method of Multi-modal Transportation Routing TONGLu, NIE Lei, FUHui- ling (School of Traffic &Transportation, Beijing JiaotongUniversity, Beijing 100044, China) Abstract: Taking into consideration the impact on route selection of multi- modal transportation by factors such as the cost, time, quality and service level of transportation, etc., the paper converts the routing problem into the general problem of the shortest path and establishes the methametical model for the problem that aims at the optimization of cost and time with varying transport volume, whose solution is realized through ant colony algorithm. Keywords: multi- modal transportation; route optimization; shortest path; ant colony algorithm [收稿日期]2009- 12- 30 [基金项目]国家自然科学基金项目（60870012）；铁道部科技研究开发计划项目（2008X027- A） [作者简介]佟璐（1983-），女，内蒙古乌兰浩特人，北京交通大学交通运输学院博士，主要研究方向为交通运输规划与管理；聂磊（1970-）， 女，湖南长沙人，北京交通大学交通运输学院教授，博士。 佟璐，等：多式联运路径优化模型与方法研究 技术与方法 doi:10.3969/j.issn.1005-152X.2010.05.019 57- - 物流技术 2010年 3月刊（总第 212期） 论和方法构建多式联运路径优化模型，最后通过运用启发式 算法对模型进行求解分析，为今后的相关研究工作提供理论 依据和工作基础。 2 多式联运路径决策模型 在多式联运网络中，运输费用、运输时间、运输质量、运输 服务水平是影响多式联运路径选择的几个重要因素。其中，运 输费用包括各区段的运费、中转费等，运输时间包括各区段的 运输时间、中转站的中转时间等。服务水平主要包括设施条 件、手续便捷度、运输信息畅通度和港口、场站的服务质量等。 为了描述多式联运路径选择过程，构建如图 1所示的多式联 运网络图，构建方式采用文献[10]的方法。 构建如图 1所示的多式联运网络图。无向图 G=(N,E)，N 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示网络中的所有节点（仓库、中转站或城市等），N={N k i }其中 i=1,2,…,n时表示节点站，k=1,2,…,m时表示各种运输方式，一 般情况下取 m=4，即 k表示铁路、公路、水运、航空；E表示所 有连接边，包括运输弧和方式之间的换装弧；运输弧是相同运 输方式不同节点间的连线，连线的权值为货物在两节点间耗 费的运输费用；换装弧是相同节点不同运输方式间连线，连线 的权值为货物在节点处的换装费用。货物在多式联运网络运 输过程中，在换装节点处的费用包括不同方式间的换装费用 和货物等待引起的额外费用。如果两节点间不提供某种运输 方式或不发生换装，则该边的权值取无穷大。 图 1 多式联运网络图 2.1 网络最短路数学模型 建立多式联运网络的数学模型如下： ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼ 上述模型中，目标函数⑴为多式联运总成本，由货物流动 总成本、中转总成本和卸货总成本组成；目标函数⑵为最小化 多式联运时间，其中货物实际到达时间由线路运输时间和换 装时间组成；约束⑶表示运输能力约束；约束⑷表示运输弧段 的货物量为总运输量与所经节点总需求量的差值；约束⑸表 示两个节点之间只能选择一种运输方式；约束⑹表示在某个 节点处只能发生转换；约束⑺表示如果在节点 i运输方式由 k 转换为 l，则从节点 i- 1到节点 i，运输方式为 k，从节点 i到节 点 i+1，运输方式采用 l；约束⑻为决策变量为 0或 1变量；约 束⑼为变量为非负性约束。 2.2 网络最短路模型参数说明 ：节点 i,i+1之间第 k种运输方式单位运输成本； ：在节点 i，货物从第 k种运输方式转换到第 l种运输 方式的中转成本； Si：在节点 i由于需求卸货产生的单位成本； ：从节点 i,i+1之间第 k种运输方式货物运输时间； ：在节点 i处，运输方式由 k转换到 l时的转运时间； wi：在节点 i处由于需求卸货产生的单位卸货时间； ：节点 i,i+1之间第 k种运输方式的运输能力； Q：货物总需求量； qi：为节点 i的货物需求量； qi,i+1：为节点 i,i+1之间货物运输量。 3 求解多式联运路径优化的蚁群算法 蚁群算法(Ant colony Algorithm, ACA)是一种新型的模拟进 化算法，由意大利学者 M.Dorigo、V.Maniezzo和 A.Colorini等人 在 20世纪 90年代首先提出，称之为蚁群系统(Ant colony sys- tem)。它是受到人们对自然界中真实的蚁群集体行为研究成果 的启发而提出的一种基于种群的模拟进化算法。生物学研究 表明一群互相协作的蚂蚁能够找到食物源和巢之间的最短路 径，而单只蚂蚁则不能。蚂蚁间相互协作的方法是它们在运动 过程中，能够在所经过的路径上留下一种称之为外激素 (Pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够 感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁 组成的蚁群集体行为便表现出一种信息正反馈现象：某一路 径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，该 算法已成功的解决了多种组合优化问题。 3.1 解的构造 在求解多式联运路径优化问题的蚁群算法中，本文采用 技术与方法 58- - k只蚂蚁共同构造一个可行解，蚂蚁之间通过信息素值来交换 信息，合作求解并不断优化，同时为该蚂蚁分配一个子周游列 表 Hi（i为蚂蚁编号），该表记录了这只蚂蚁访问过的点；之后 引入另一只蚂蚁遵循第一只蚂蚁的行为在剩下的点中继续搜 索。每只蚂蚁是一个独立的用于构造解的过程，蚂蚁的任务是 在有着多方面约束下，依次寻找连通节点，并在连通节点弧上 留下信息素。使用弧的信息素以及启发式信息来决定指派的 次序，应用局部优化进行信息素更新，在所有的 k个蚂蚁都构 造完解后，再应用全局信息素更新。 3.2 蚂蚁的路径选择 τij(t)表示 t时刻在点 i,j连线上残留的信息素。初始时刻， 各条边上的信息素相等，设τij(t=0)=C（C为一常数），蚂蚁 k在 运动过程中根据各条边上的信息素大小决定转移方向。pij k 表 示在 t时刻蚂蚁 k由点 i转移到点 j的概率： （10） 其中，ηij为启发式信息，表示蚂蚁从点 i转移到点 j的期 望程度，本文中取ηij=1/dij（dij表示点 i到点 j的距离），α 为 在路径 ij上残留信息的重要程度，β为启发式信息的重要程 度，集合 tabuk为禁忌表， 。 3.3 信息素更新 每一组的所有蚂蚁周游完成后，该组中的蚂蚁所经过的 路径上的信息素要根据下式进行调整： （11） 其中，γ表示信息素的蒸发系数，△τij为本次周游中边 ij上的信息素增加量，如果边 ij没有被任何一只蚂蚁走过则 △τij取零；否则令△τij=QL ，L为该组所有蚂蚁所经过的边长 之和。 4 求解多式联运路径问题的蚁群算法步骤 Step1:读入各节点之间可以选择运输方式的信息数据，包 括：各种方式的运输时间、运输距离、运输量、各种方式间的中 转时间、中转运费、卸货费用。定义各参数值：α；β；γ；Q；最 大迭代次数 NC_max。蚂蚁结构定义：节点间运输成本信息、运 输成本、中转成本、运输时间、中转换装时间、货物到达终点站 总时间、中转记录、线路选择信息。 Step2:初始化蚂蚁，蚂蚁结构中所有信息为零。初始化信 息素矩阵，认为满足约束条件的两个结点单向连通，不连通的 结点间的信息素为零。对于连通的结点间的信息素初始值相 同，令τij=C（C为常数）。 Step3:设置第 k只蚂蚁的禁忌表，将 m只蚂蚁随机分配到 n个节点，使得蚂蚁从任意结点开始搜寻满足约束条件的最大 连通图。 Step4:寻找连通图，设蚂蚁 k此时到达 Ni k 点，然后搜寻满 足跟 Ni k 接续的后序节点 N={Ni k ,…，Nn k }并记录 Ni k 到 N中所有 元素的信息素，将其归一化 P={p1,p2,p3,p4,…,pn}后作为选择下 一节点 Ni k 的概率，按公式（10）。为了防止达到局部最优解，设 定一个阈值 P，随机生成一个数ω，如果ω＞p则选择概率最 大的节点，否则将概率累计求和，大于随机数ω的节点作为 选择的下一个节点。蚂蚁 k移动到 Nk点时，Ni和 Nk从蚂蚁 k 的周游列表中删除，并对弧上信息素按公式⑾进行更新。 Step5:当蚂蚁完成一次循环后，记录蚂蚁的结构中所有信 息，每条弧上的总费用和即为第一个目标函数的评价值。 Step6:全局信息素更新，选择到目前为止连通图总费用最 少的蚂蚁作为信息素更新的依据。 Step7:计算评价值，如果第一个目标的评价值有所改进， 则保留当前解为最好解，在此基础上计算第二个目标的评价 值。否则，信息素采用上次最好解的信息素。 Step8:迭代次数 NC=NC+1，如果 NC小于设定的迭代次数 NC_max，则转至 Step2，否则转入 Step9。 Step9:输出最优解及目标函数值。 5 算例分析 某运输企业想运一批货物从城市 O到城市 E, 途经 A、B、 C、D四个城市,而且相邻两个城市之间可选择的运输方式在表 1中给出,其有关参数见表 1和表 2,各城市货物需求量见表 3， 单位搬卸费为 1元，单位搬卸时间为 6min。在运量变化下，如 何选择多式联运路径, 使运输企业既可以节省运输总费用,又 可以缩短运输总时间？ 表 1 各个城市之间的单位运费和运输时间表 注：分母为运输时间（h），分子为单位运费（元），M为不存在某种运输方式。 表 2 不同运输方式之间的单位中转费用和中转时间表 注：分母为单位中转运费（元），分子为中转时间（h）。 表 3 各个城市货物需求量表 用MATLAB开发的蚁群算法程序对问题进行求解，蚁群 佟璐，等：多式联运路径优化模型与方法研究 技术与方法 59- - 物流技术 2010年 3月刊（总第 212期） （上接第 48 页）某项作业的时间消耗，从而揭示了消耗时间较 多的作业，对于这些作业，企业可以考虑采取设施、设备更新 或作业外包等方式来压缩作业消耗时间，降低作业成本；另一 方面，作业时间等式的构造以及企业随时掌握的作业消耗资 源情况，使企业更容易发现作业流程优化的重点，并加以改造。 6 结束语 时间驱动作业成本法有着先进的科学理论作为指导，为 企业成本核算提供了更加合理、精准、便捷的方法和模型。但 是，该方法是否能够在企业实际操作中得到广泛应用，目前还 有待观察。 时间驱动作业成本法比传统作业成本法能够提供更准确 的成本信息，又具有更经济、功能更强大的创新性，符合应用 条件的企业应采用时间驱动作业成本法，加强成本核算，提供 有效控制决策，提高企业乃至整个社会的经济效益。 [参考文献] [1]Robert S Kaplan, Steven R Anderson. Time - Driven Activity - Based Costing[J].HarvardBusinessReview, 2005，（1）: 18- 23. [2]杨头平.基于时间驱动作业成本法的企业物流成本核算 - 基于时间 驱动作业成本法[J].当代经济(下半月),2008，（12）：144- 146. [3]闵亨锋.基于时间驱动作业成本法下的物流成本核算[J].物流科技, 2007，（6）：93- 95. [4]姚 霏.时间驱动作业成本法与传统作业成本法的区别及改进[J].科 技情报开发与经济,2006，（7）：133- 134. [5]钱爱民,于守华.成本管理会计[M].北京：清华大学出版社,2007. [6]白胜.时间驱动作业成本法研究[J].财会通讯,2009,（23）：155- 156. 日 文 规模为 50,信息素重要程度为 1,启发式因子重要程度为 0.2,信 息素蒸发为 0.1，最大迭代数为 1 000,得到运输方案为: O→A 选择公路，A→B选择水运，B→C选择铁路，C→D选择水运， D→E选择水运，运输总费用为 3 482元,运输总时间为 84h,目 标函数变化曲线如图 2所示。 图 2 蚁群算法进化曲线图 从算例的实验结果可以看出，运输费用和运输时间本身 是两个矛盾的目标，如何使两者平衡，取决于企业的决策。本 文的解法是在追求企业费用最小的目标下，再寻求企业运输 时间的最小化。另外，可以设目标一为 f1，目标二为 f2，将多目 标转为单目标 F=f1*f2来进行求解。 在 LINGO 8.0中编程求解，求得结果如图 3所示，图中只 显示了两个目标的取值，由于篇幅有限，其它部分省略。其中 f1=3 482元，f2=84h，求得结果与设计的蚁群算法相同。 图 3 LINGO 8.0计算结果 6 结论 多式联运路径优化问题是多因素的综合规划问题，多种 运输方式的有效结合才能使运营企业进行最优成本控制的同 时，以最快的速度将货物运送至目的地。本研究在分析多式联 运网络基础上，采用系统规划建模的方法，运用蚁群算法寻找 满足网络约束条件下的最短路径。蚁群算法具有并行搜索的 特性，可以快速找出多个较优联运路线，并在蚂蚁的比较中找 出问题的最优解。多式联运路径优化问题是一类比较复杂的 问题，本文只对流量变化情况提出其数学模型，在成本和时间 计算中，没有考虑货物在每个时间窗内由于延误所产生延误 费用和时间的部分。同时，在蚁群算法中可以设计合理运输方 式间转换的启发式因子来加速算法的求解效率。这些问题可 以在以后的研究中进一步考虑。 [参考文献] [1]LozanoA, Storchi G. Shortest viable path algorithminmultimodal networks [J].TransportationResearchPartA,2001,35 :225～241. [2]张建勇，郭耀煌.一种多式联运网络的最优分配模式研究[J].铁道学 报，2002，24 (4)：114～116． [3]王涛，王刚.一种多式联运网络运输方式的组合优化模式研究[J].中 国工程科学，2005，7 (10)：46～50． [4]王云鹏，王占中，赵颖，等．基于扩展 Petri网的多式联运流程研究 [J].工业技术经济，2005，24 (4)：77～79． [5]Beuthe M. Freight transportation demand elasticities: a geographic multi- modal transportation networks analysis [J]. TransportationResearch Part E. 2001,37 (4):253- 266. [6]刘诚，陈治亚，封全喜.带软时间窗物流配送车辆路径问题的并行遗 传算法[J].系统工程，2005，23 (10)：72～11． [7]魏众，申金升，等.多式联运的最短时间路径－运输费用模型研究[J]. 中国工程科学，2006，8（8）． [8]Calvete H I. A goal programming approach to vehicle routing problemwith soft timewindows[J]. European Journal ofOperational Research, 2007, 177 (3):1720- 1733. [9]孙华灿，李旭宏，陈大伟，等.综合运输网络中合理路径优化模型[J]. 东南大学学报，2008，38（5）． [10]张运河，林柏梁，梁栋，等.优化多式联运问题的一种广义最短路方 法研究[J].铁道学报，2006，28（4）． 技术与方法 60- -