考虑多种运输方式的第四方物流路径优化算法

李贵华,黄 敏

(1.东北大学信息科学与工程学院流程工业综合自动化国家重点实验室,沈阳110819;

2.沈阳工业大学管理学院,沈阳110870)

考虑多种运输方式的第四方物流路径优化算法

李贵华1,2,黄 敏1

(1.东北大学信息科学与工程学院流程工业综合自动化国家重点实验室,沈阳110819;

2.沈阳工业大学管理学院,沈阳110870)

综合运用不同运输方式的技术和经济特点实施联合运输,是满足货主降低运输费用和时间要求的有效措施。为此,针对不同运输主体,提出多种运输方式的优化组合算法,以实现在满足客户运输要求的前提下,综合选择运输方式、第三方物流服务商及运输路径。将不同第三方物流服务商多种运输方式的优化选择与路径选择相结合,建立单源点到单目地点完成多项任务的第四方物流路径优化模型,设计模型求解的最大最小蚂蚁系统。实例计算结果表明,该算法能方便有效地求解考虑多种运输方式的第四方物流路径问题,为第四方物流企业决策提供参考。

路径优化;最大最小蚂蚁系统;第四方物流;多种运输方式;蚁群优化算法

1 概述

第四方物流(the fourth Party Logistics,4PL)是从外协的第三方物流(the third Party Logistics,3PL)演变成分享协作而出现的一种新的物流形式。4PL服务商通过有效整合供应链中的各种资源,能增加供应链的价值［1］。

4PL服务商在整合供应链资源进行优化决策时,其中的关键问题是运输路径选择、运输方式选择及3PL服务商的选择。许多学者在这一领域进

行了相关的研究［2-4］,但这些研究一部分只是考虑了3PL服务商的单一运输方式,忽略了不同运输方式所具有不同的技术经济特点。如文献［5］采用遗传算法求解了单一运输方式的第四方物流路径问题;文献［6］建立了考虑单一运输方式的单任务的4PL路径优化模型并运用免疫算法进行了求解。另一部分是仅从多式联运的角度进行研究,未能综合考虑不同3PL服务商的服务能力及服务规模的效果。如文献［7］提出了一个启发式算法对利比亚半岛区域内的货物进行了公路运输和铁路运输的优化。文献［8］建立了具有模糊时间窗的多种运输模式联运的模型,并采用混合田口遗传算法进行了路径的优化。文献［9］也对基于多种传输方式的4PL路径问题进行了深入研究。这些研究针对其特定的问题均给出了求解方法,但上述研究难以从综合角度实现第四方物流的组合最优化。为此,本文在文献［9］研究的基础上,针对考虑多种运输方式的多任务4PL路径优化问题,提出一种优化组合算法。

2 问题描述与建模

2.1 第四方物流路径问题

假设4PL公司承接了多项运输任务,运输网络用多重图G(V,E)表示,如图1和图2所示。从源点v1到目的点v15,中途经过若干个城市,任意相邻的2个城市之间都可能存在多个3PL供应商,每个3PL供应商都可能有多种运输方式可供选择。当从一种运输方式转换到另一种运输方式时,需要一定的中转时间和中转费用,而且在整个运输过程中完成各项任务的时间不能超过其运输期限。在综合上述各种因素之后,确定最佳的3PL供应商和运输组合方式,使总运费最低。

图1 第四方物流路径问题的多重图模型

图2 基于多种运输方式的两点间多重图模型

2.2 模型建立

设在任意2个城市间只能选择一个4PL服务商的一种运输方式,运输方式的转换只能在城市所对应的节点处发生。模型参数及变量描述如下:

表示i,j两点间供应商的数量(i,j=1,2,…,n);

Df为任务f的货运量;K为客户要求的信誉;Tf为任务f的时间期限。

建立的数学模型如下:

在上述模型中,式(1)为目标函数,表示实现整个运输过程中的运输总成本的最小化,其中运输成本由运费和中转费用2个部分组成;式(2)表明完成每一任务的货物运输必须在规定期限Tf内运到;式(3)表示对于完成各项任务所选择的物流公司的该种运输方式的运输能力应大于客户要求的运输能力Df;式(4)表明对于完成各项任务所选择路径的节点的吞吐能力应大于客户要求的能力Df;式(5)表示完成各项任务所选择的物流公司的信誉指标应大于客户要求的指标K;式(6)保证Rf是一条以vs为起点,vt为终点的合法路径。

3 最大最小蚂蚁系统

蚁群算法是意大利学者Dorigo等人提出的一种模拟蚂蚁群体觅食行为方式的仿生优化方法,该方法及其改进算法解决了许多复杂优化和经典NP-C问题。文献［10］提出了基于选路优化的改进蚁群算法,该算法通过减少基本蚁群算法中的选路次数,提高算法的执行效率。文献［11］运用最大最小蚁群算法求解了带时间窗的车辆路线问题。文献［12］提出了简化蚁群算法解决了最大最小蚁群算法中信息素下界难以确定的问题,并通过旅行商问题验证算法的有效性。在众多的改进蚁群算法中,最大最小蚂蚁系统(Max-Min Ant System,MMAS)是其中应用比较广泛蚁群算法,在实际的应用中也取得了很好的效果。为此,本文采用MMAS求解单源点到单目地点的多任务的考虑多种运输方式的第四方物流路径优化问题。

3.1 MMAS数学模型

信息素全局更新公式为:

其中,Const为一常数,表示蚂蚁循环一周在经过的路径上所释放的信息素总量;Z(q∗)代表本代中费用最低的最优蚂蚁组所经过路径的总费用。

其含义为:当得到的值小于0时,取0;得到的值大于零时则取其实际差值。

3.2 蚁群算法步骤

蚁群算法步骤如下:

Step2将F×Q只蚂蚁放在初始节点上。

Step3循环次数Nc←Nc+1。

Step4令蚂蚁禁忌表索引号q=1,f=1。

Step5令t=0,把初始节点依次放入到Tabuqf和路径表Rqf中。

Step6t=t+1。

Step7根据状态转移概率式(7)计算第q组完成任务f的蚂蚁从节点i到节点j选择第k供应商的第l种运输方式的概率(以弧的选择概率来确定节点的选择概率)。

Step8选择具有最大状态转移概率的弧对应的节点,将蚂蚁移动到该节点,并把该节点计入禁忌表Tabuqf中;将选择的弧和节点顺序计入路径表Rqf中。

Step9若禁忌表Tabuqf中包含了目的节点,在路径表Rqf中会获得一条完成某一任务的可行路径,转到Step10;否则转到Step6。

Step10令f=f+1,如果f≤F,转到Step5;否则,转到Step11。

Step11令q=q+1,如果q≤Q,转到Step5,否则,转到Step12。

Step12在所有生成的可行解中,找出目标函数最优解和最优蚂蚁组。

Step13对最优蚂蚁组经过的路径,根据式(8)～式(12)进行信息素的更新。

Step15若Nc＜Ncmax,则清空禁忌表和路径记录表转到Step3;否则,停止迭代输出最优路径及结果。

4 算例验证

为了验证本文提出的模型和算法的有效性,设计了一个仿真算例对其进行验证,算法用Virtual studio 2008,Access 2003实现,并在3.4 GHz Intel Core PC机上运行。

假设某第四方物流公司承接了4项运输任务,要求将货物从城市1送到城市15,运输网络如图1、图2所示,所选定的2个供应商分别能提供3种运输方式可供选择,假设4项任务的运量和时间期限分别为:5和40;6和45;10和50;15和43,其他数据经过预处理如图3和图4所示。

图3 运输网络图中相邻节点间弧的数据

图4 各种运输方式间的转换费用和时间

图3中形如a/b/c的数据,a为单位费用,b为时间,c为能力;图4中数据的分子为转换费用,分母为转换时间。

通过多次试验,各参数取值分别为Q,Nc,α,β,Const,ρ=(10,400,3,3,100,0.35)时,得到的最优路径是:

任务1:R1={1,23,3,13,5,13,10,13,14,13,15};

任务2:R2={1,23,2,13,8,13,12,22,15};

任务3:R3=1,12,2,12,8,12,12,21,15};

任务4:R4={1,13,3,22,7,22,11,12,15}。

其中,R1所需作业时间为36;R2所需作业时间为38;R3所需作业时间为50;R4所需作业时间为41,完成4项任务所需的总运费为3 417。计算结果表明基于本文建立的模型及优化算法,可以在满足客户运输时间要求的前提下,得到最经济的运输路径、运输方式和3PL供应商的组合,可以为4PL服务商提供决策依据。

5 结束语

不同的运输方式有不同的技术和经济特点,综合运用不同运输主体的各种运输方式,对降低货物运输的成本、保障货物运输的质量和时间要求具有重要的意义。本文建立了考虑多种运输方式的单源点到单目地点的多任务第四方物流路径优化模型,提出了求解该问题的MMAS,并通过算例验证了该算法求解第四方物流路径优化问题的有效性。但本文未考虑同时承担多项运输任务的费用折扣问题,这有待今后进一步研究。

［1]Christopher M.Logistics and Supply Chain Management［M］.New York,USA:Free Press,1994.

［2]陈建清,刘文煌,李 秀.第四方物流中决策支持系统及物流方案的优化［J］.计算机工程,2004,30(5):150-153.

［3]王 涛,王 刚.一种多式联运网络运输方式的组合优化模式［J］.中国工程科学,2005,7(10):46-50.

［4]范志强,庄佳芳.基于多维权有向图的多式联运中运输方式的选择研究［J］.物流技术,2006,25(5):47-48.

［5]Chen J Q,WangS,LiX,etal.DirectedGraph Optimization Model and Its Solving Method Based on Genetic Algorithm in Fourth Party Logistics［C］// ProceedingsofIEEEInternationalConferenceon System,Man and Cybernetics.Washington D.C.,USA: IEEE Press,2003:1961-1966.

［6]Min Huang,Wei Tong,Qing Wang.Immune Algorithm BasedRoutingOptimizationinFourth-partyLogistics［C］//ProceedingsofIEEEWorldCongresson Computational Intelligence.Washington D.C.,USA:IEEE Press,2006:3029-3034.

［7]Arnold P,Peeters D,Thomas I.Modeling a Rail/Road Intermodal Transportation System［J］.Transportation Research,Part E,2004,40:255-270.

［8]熊桂武.具有模糊时间窗的多模式联运建模及优化［J］.工业工程,2012,15(4):7-11

［9]李贵华,柴伟莉,玄 雪.基于多种运输方式的第四方物流路径问题研究［J］.物流技术,2010,29(1):72-74.

［10]张 毅,梁艳春.基于选路优化的改进蚁群算法［J］.计算机工程与应用,2007,43(2):60-63.

［11]陈 琪,宁 博.MMAS在带时间窗的车辆路线问题中的应用［J］.江苏科技大学学报:自然科学版,2009, 23(3):263-266.

［12]张兆军,冯祖仁,陈竹青.简化蚁群算法［J］.控制与决策,2012,27(9):1325-1330.

编辑 金胡考

The Fourth Logistics Routing Optimization Algorithm Considering Multiple Transportation Modes

LI Guihua1,2,HUANG Min1
(1.State Key Laboratory of Synthetical Automation for Process Industries,
College of Information Science and Engineering,Northeastern University,Shenyang 110819,China;
2.School of Management,Shenyang University of Technology,Shenyang 110870,China)

To use comprehensively different transport modes and combined transport are effective to decrease transportation cost and time.Therefore,this paper provides a solution for the combinational optimization of multiple transport modes.The solution selects comprehensively transport modes,logistics suppliers and transport routes on the premise of meeting transportation need.This paper integrates the optimization selection of multiple transport modes and path selection,establishes the route optimization model for multitasking from one origination to one destination in the fourth Party Logistics(4PL),and proposes the solution of Max-Min Ant System(MMAS).The results of experiments show that,the route optimization problem based on the selection of multiple transport modes in the 4PL can be solved by MMAS conveniently and effectively,which can be consulted by 4PL companies.

path optimization;Max-Min Ant System(MMAS);the fourth Party Logistics(4PL);multiple transportation modes;Ant Colony Optimization(ACO)algorithm

李贵华,黄 敏.考虑多种运输方式的第四方物流路径优化算法［J］.计算机工程,2015,41(3):273-277.

英文引用格式:Li Guihua,Huang Min.The Fourth Logistics Routing Optimization Algorithm Considering Multiple Transportation Modes［J］.Computer Engineering,2015,41(3):273-277.

1000-3428(2015)03-0273-05

:A

:TP29

10.3969/j.issn.1000-3428.2015.03.051

国家自然科学基金资助项目(71071028);国家杰出青年科学基金资助项目(71325002,61225012);高等学校博士学科点专项科研基金资助项目(20120042130003,20110042110024);中央高校基本科研业务费专项基金资助项目(N110204003,N120104001);流程工业综合自动化国家重点实验室基础科研业务费基金资助项目(2013ZCX11)。

李贵华(1973-),女,副教授、硕士,主研方向:物流系统优化;黄 敏,教授、博士。

2014-04-04

:2014-05-19E-mail:gao_yining@126.com