2. 武汉科技大学服务科学与工程研究中心, 湖北 武汉 430081;
3. 华中科技大学管理学院, 湖北 武汉 430074
2. Research Center of Service and Engineering, Wuhan University of Science and Technology, Wuhan 430081, China;
3. School of Management, Huazhong University of Science and Technology, Wuhan 430074, China
0 引言
近年来，在互联网和新一代信息技术的推动下，物流服务逐渐走入千家万户，如何在有限的资源下为客户提供准确、快速、高效的物流服务成为学术界和行业界共同关注的热点问题[1-2].同时，全球物流市场也逐渐从欧美等发达国家逐渐向中国、印度等发展中国家转移，为我国物流业振兴提供了良好的契机.然而，当前我国物流成本居高不下、物流服务水平提升缓慢，环节冗余、信息不对称、最后一公里配送是亟待解决的痛点问题.
为提高物流服务水平、降低物流成本，传统处理方式是将物流服务外包给专业的第三方物流(third party logistics，3PL)供应商.而逐渐加剧的市场竞争环境和不断提高的客户个性化需求表明，3PL资源整合能力匮乏，供应商间合作不够深入，互补性资源得不到充分利用，很难使社会物流整体达到效率最大化[3].第四方物流(fourth party logistics，4PL)[4]优化的本质是在集成供应链信息的基础上为客户提供一整套的供应链解决方案，具有广阔的应用前景[5].
路径问题是4PL优化中的关键问题[6].由于需要同时考虑路径选择优化和3PL供应商选择优化[7]，4PL路径问题(fourth party logistics routing problem，4PLRP)对传统的路径问题研究方法[8]提出了挑战. Li等[9]将4PLRP分解为2个子问题，分2个阶段求解：先选择路径，然后再在所选择路径上选择3PL供应商.该方法简单、易于实现，但2阶段同步困难，尤其是对较复杂的大规模问题，难以在较短时间内获得较好解.另外一些研究将路径优化和3PL供应商选择优化综合成一个问题进行求解[10]，使用多重图描述4PLRP，图中每条边表示一个在该路径上承担运输任务的3PL供应商，将路径优化和3PL供应商选择优化转化为基于多重图的最短路问题.该方法有效地将2个相关问题转化为1个问题进行求解，清晰地描述了4PLRP，同时降低了问题寻优难度. Chen等[11]将4PLRP描述为一个有向多重图，Bo等[12]将4PLRP描述为一个无向多重图，并分别设计算法对小规模问题求得最优解.崔妍等[6]从4PL管理中转运服务需要等待发车时间的角度，对单起点多终点的多任务4PLRP进行了研究.黄敏等[13]从同一个3PL供应商承接多项运输任务时存在打折现象角度对多起点多终点的多任务4PLRP进行了研究.薄桂华等[14]根据现实物流收货时间存在时间窗口特点研究了带时间窗的4PLRP. Tao等[15]从费用折扣角度对4PLRP建立了混合整数规划模型.
已有4PL研究大多针对确定性问题，很少考虑物流运作中普遍存在的不确定性. “互联网+”、云计算、大数据、物联网等新一代信息技术推动了现代物流业的发展，同时对物流服务提出了更高的要求，物流运作中的不确定性对物流企业竞争力起到决定性作用. Huang等[16]假设不确定环境下，物流企业没有历史数据，将运输时间描述为模糊变量，建立了4PLRP的模糊规划模型.任亮等[17]考虑不确定环境下客户对运输时间具有拖期厌恶行为特征，从前景理论角度对4PLRP进行了研究.然而，大数据背景下，现代物流往往具有明显的随机性，可以获得大量的历史数据.因此，本文基于随机理论将运输时间描述为随机变量，并结合客户往往对物流运输时间具有较高要求的特点，研究不确定环境下带有时间窗的4PLRP.首先分析了不确定环境下运输方案的服务水平，基于多重图的描述方式建立不确定环境下的机会模型；然后，将该机会模型进行清晰化处理，使之转化为带有确定时间的等价确定性模型，从而提高模型求解效率.根据模型结构和多重图特点，采用蚁群算法对确定性模型进行求解.算例分析表明，所提出的模型和算法可以在不确定环境下为客户提供快速、稳定、可靠的运输方案，说明了方法的有效性.
1 问题描述及数学模型 1.1 问题描述4PLRP需要同时考虑路径选择问题和3PL供应商选择问题，采用多重图的方法对不确定环境下带有时间窗的4PLRP进行研究.多重图用G(V，E)表示，如图 1所示.其中，V(|V|=n)表示节点集合，n表示节点个数，E表示边的集合；s表示运输任务的起始节点，即供应城市；e表示运输任务的目的节点，即需求城市；图中其它节点表示中转城市，即中转节点.每个节点具有费用、时间属性，分别表示运输任务经过该节点时所需要的运输费用和运输时间.需要注意的是，考虑到相邻城市间可能存在多个3PL供应商提供运输服务及每对节点间可能存在多条运输路径的特点，将图 1中每条边表示为在该段路径上提供运输服务的备选3PL供应商.每条边具有费用、时间、承载能力和信誉属性，分别表示该3PL供应商承担该项任务时所需要的费用、时间、本身所具有的承载能力和历史信誉水平.
|
| 图 1 4PLRP的多重图 Figure 1 Multi-graph of 4PLRP |
受复杂多变环境影响，假设3PL供应商(边)的运输时间存在一定的扰动，描述为随机变量.需要解决的问题是，在3PL供应商运输时间不确定的条件下，如何设计最优的运输方案，满足总运输费用要求，并最大化总运输时间满足客户时间窗要求的机会，即服务水平.
定义参数和变量：rij表示节点i和节点j之间边的数量；eijk表示节点i和节点j之间的第k条边；Cijk、Pijk、Dijk分别表示运输任务经过eijk时所需的费用、承载能力和历史信誉；C′i和T′i分别表示运输任务经过节点时所需要的费用和时间.运输任务经过eijk时所需的运输时间用Tijk+tijk表示，其中Tijk表示时间的期望值，tijk表示扰动，tijk为随机变量；[T1，T2]和α分别表示客户对运输任务的时间窗和置信水平要求；p和D分别表示运输任务对3PL供应商承载能力和历史信誉要求；R表示一条从起始节点出发并终止于目的节点的连通路径，如图 1中粗线所示的路径可表示为R=(vs，2，v2，1，v3，2，ve)；xijk(R)和yi(R)为决策变量.当运输任务经过eijk时，xijk(R)=1，否则xijk(R)=0；当运输任务经过节点vi时，yi(R)=1，否则，yi(R)=0.
1.2 机会模型根据参数和变量描述，建立不确定环境下的机会模型(UCM)：
|
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
其中，式(1)是模型的目标函数，Pr{·}为满足一定条件的概率，式(1)表示最大化总运输时间满足客户时间窗要求的机会，总运输时间包括节点和边上消耗的时间；式(2)是总运输费用约束，表示总运输费用满足客户要求；式(3)和式(4)是承载能力和信誉约束，要求提供运输服务的3PL供应商承载能力和历史信誉满足客户运输任务要求；式(5)和式(6)是模型决策变量，分别选择多重图中的边和节点；式(7)表示所选择路径必须是一条从起始节点出发并终止于目的节点的连通路径.
为便于论述及必要的数学简化，假设3PL供应商运输时间服从正态分布并且相互独立.因Tijk表示时间的期望值，设扰动tijk均值为0，即tijk~N(0，σijk2).
1.3 等价确定性模型所建立的UCM中仅目标函数式(1)包含随机变量，将式(1)作如下转化：
tijk服从正态分布且相互独立，根据随机理论可知：
|
式(1)可表示为
|
即：
|
其中，Φ(·)为标准正态分布的分布函数.可以看出，目标函数α中已经消去了随机变量tijk，完全由确定量组成.由图 1可知，当选定一条由起始节点至目的节点的通路R时，总运输时间满足时间窗口的机会(即目标函数α)易由式(1)进行计算.
因此，UCM转化后的等价确定性模型(EDM)为
|
(8) |
|
(9) |
|
(10) |
|
(11) |
|
(12) |
|
(13) |
|
(14) |
从图论角度看，所建立的EDM是在多重图上求解带有费用、承载能力和信誉约束的最短路问题，即当多重图退化为简单图时，EDM即转化为约束最短路问题. Hassin[18]提出约束最短路问题是NP-hard问题，因此所建立的EDM也是NP-hard问题，从智能优化算法角度设计求解.
2.2 蚁群算法蚁群算法(ant colony algorithm，ACA)是意大利学者Dorigo等模拟自然界中蚂蚁群体觅食行为提出的一种基于群体智能的启发式仿生进化算法[19]. ACA具有鲁棒性高、分布式计算、正反馈机制等特点，是智能计算领域的研究热点和前沿课题[20].考虑到ACA蚂蚁觅食与本问题起始节点到目的节点寻优的相似性，根据多重图特点设计ACA对EDM进行求解.
1) 编码机制.确定性模型EDM的解为一条从起始节点出发并终止于目的节点的连通路径R，R包括节点的集合和边的集合.图中eijk表示节点i和节点j之间的第k条边，可以看出，一条连通路径中边的集合可以唯一确定节点集合.因此，设计变长编码机制，种群中第m只蚂蚁所表示的解为
|
其中，Rm要求问题的解从起始节点s出发，终止于目的节点e，并且前后相邻的两条边需经过同一中转节点，从而保证路径的连通性.
2) 转移策略.种群中所有蚂蚁均从初始节点出发，向目的节点进行转移.每只蚂蚁在解空间中独立的搜索可行解，当其到达一个还没有经过的路口时，按照转移概率随机选择某条边前行.设蚂蚁当前位置为i，可行方向集合用allowedi表示，根据信息素启发信息和路径启发信息，其选择某条边eijk作为转移方向的概率如式(15)所示：
|
(15) |
其中，Ng表示当前迭代次数，Ng=1，2，…，NG；τijk(Ng)表示第Ng代时边eijk上的信息素浓度；ηijk表示路径启发信息，ηijk=1/Cijk；ω和φ分别表示信息素浓度启发因子和路径启发因子；arc表示可行集合allowedi中的边.
3) 信息素更新策略.蚂蚁开始搜索前，赋予每条边相同的初始信息素浓度τ0.随着算法的逐渐推进，当前最优解路径上的信息素浓度增加，同时所有边上的信息素浓度随着时间的流逝不断挥发，形成正反馈机制.每代所有蚂蚁搜索完成后，对多重图中所有边的信息素浓度进行更新，更新公式如式(16)和式(17)所示：
|
(16) |
|
(17) |
其中，τijk(Ng)表示第Ng代时边eijk上的信息素浓度，Δτijk表示其增量；ρ(0 < ρ < 1)表示信息素残留系数；R表示当前最优解，C为R上的总费用；Q为常量.
4) ACA简要流程.
步骤1 初始化种群规模NP、最大迭代次数NG、当前迭代次数Ng及初始信息素浓度τ0.
步骤2 将NP只蚂蚁置于初始节点，按照转移策略进行转移，直至到达目的节点.
步骤3 更新当前最优解R并根据R更新所有边上的信息素浓度.
步骤4 检验：若Ng=NG，则算法结束；否则Ng=Ng+1，转步骤2.
3 实验验证为验证所提出模型和算法的有效性，设计随机产生的7节点(E7)、15节点(E15)和30节点(E30)三种不同规模算例进行测试分析.算法使用Microsoft Visual Studio 2008编程实现，并在Core 2 3.20 GHz PC上运行.
假设某第四方物流公司承接了某一地区物流运输方案设计任务，需要将运输任务从起始节点运输到目的节点.不确定环境下，方案要求在一定总运输费用约束下，最大化总运输时间满足客户时间窗要求的机会.
3.1 算法测试分析对影响算法性能的参数，分别取不同取值对所测试问题反复实验，从而获得算法的最佳参数组合，测试过程简要描述为：
步骤1 在参数取值范围内随机产生一组参数组合.
步骤2 固定其它所有参数，对一个参数在其取值范围内从小到大按一定间隔进行取值并测试算法性能，获得当前状态下该参数的较优取值.
步骤3 重复步骤2依次对所有参数进行测试，获得一组当前较好的参数组合.
步骤4 根据所测试问题和算例对精度的要求，重复步骤2和步骤3，直至获得满意的参数组合.
对3种不同规模算例E7、E15和E30进行测试.时间窗口分别取值为[52，58]，[55，63]和[82，92]，总运输时间要求C0分别为95、125和250，每条边的变异系数cv(coefficient of variance)取0.1.
|
算法执行100次，“最好解”表示100次中所得最好解的目标函数值，即最好值；“最差解”表示最差解的目标函数值，即最差值；“均值”表示算法执行100次的平均值；“时间”表示算法执行一次平均所消耗的时间. ACA对E7、E15、E30三种不同规模算例结果如表 1所示.
| 算例 | NP | NG | τ0 | ρ | ω | φ | Q | m | τmin | τmax | 最好解 | 最差解 | 均值 | 时间/s |
| E7 | 20 | 10 | 0.7 | 0.9 | 1.0 | 1.5 | 5 | 3 | 0.1 | 2.0 | 0.850 2 | 0.850 2 | 0.850 2 | 0.1 |
| E15 | 50 | 20 | 0.9 | 0.9 | 1.0 | 1.5 | 5 | 3 | 0.1 | 2.0 | 0.905 0 | 0.902 6 | 0.904 9 | 0.5 |
| E30 | 100 | 50 | 0.9 | 0.9 | 1.0 | 1.5 | 15 | 3 | 0.1 | 2.0 | 0.910 8 | 0.839 0 | 0.899 1 | 9.8 |
从表 1可以看出，针对3种不同规模的算例，算法都能较有效地求解本文所提出的问题.当问题规模较小时，ACA能快速稳定地求得较好解.随着问题规模逐渐增大，ACA搜索的最差解和最好解稍有起伏，所需搜索时间也逐渐增大.针对所研究的问题，所采用算法具有一定有效性.
3.2 模型对比分析针对不确定性问题，传统的处理方法是建立期望值模型(EVM).为便于对比，不失一般性，假设客户在时间窗内希望总运输时间越小越好，此时，式(1)可表示为
|
(18) |
针对算例E7，将EDM和EVM进行对比，当时间窗口[T1，T2]变化时，两种模型对比结果如表 2所示.其中，EVM的解满足客户时间窗要求的机会用式(19)计算：
|
(19) |
| 模型 | 时间窗 | 算例 | 最好解 | 最差解 | 均值 | 时间/s |
| EVM | [50，56] | E7 | 0.485 5 | 0.485 5 | 0.485 5 | 0.1 |
| EDM | [50，56] | E7 | 0.849 4 | 0.849 4 | 0.849 4 | 0.1 |
| EVM | [52，58] | E7 | 0.642 1 | 0.642 1 | 0.642 1 | 0.1 |
| EDM | [52，58] | E7 | 0.850 2 | 0.850 2 | 0.850 2 | 0.1 |
| EVM | [54，60] | E7 | 0.583 6 | 0.583 6 | 0.583 6 | 0.1 |
| EDM | [54，60] | E7 | 0.857 6 | 0.857 6 | 0.857 6 | 0.1 |
从表 2可以看出，在相同时间窗口约束下，EVM由于没有考虑时间的扰动，可以选择总运输时间期望值更小的路径，但其满足时间窗要求的机会普遍较低，服务水平低于EDM.可以看出，EDM获得的最好解在EVM中往往并不是较好解. EVM选择总运输时间期望值较小的路径，但可能存在较大风险，不能满足客户委托任务对服务水平的基本要求，所设计的等价确定性模型EDM具有一定有效性.
4 结论现代物流复杂的运作环境对物流运输方案设计提出了更高的要求，本文从不确定性角度对带有随机运输时间并考虑时间窗口约束的第四方物流路径问题进行了研究.首先建立了不确定环境下的机会模型，并将其转化为清晰的等价确定性模型.其次根据多重图结构及模型特点，采用蚁群算法对等价确定性模型进行求解.最后通过数值算例，将蚁群算法、等价确定性模型和传统的期望值模型分别进行了对比分析，算例结果验证了算法和模型的有效性，研究为现代物流运作方案设计提供了一种有效工具.
本文仅考虑存在随机运输时间的情形，而复杂的物流运作环境中存在众多的不确定性因素，影响物流决策，同时也加大了优化模型的构建和求解难度，考虑时间、成本、质量等多重不确定性的第四方物流路径优化将是下一步研究的重点.
| [1] |
王勇, 吴志勇, 陈修素, 等.
面向第4方物流的多代理人作业整合优化算法[J]. 管理科学学报, 2009, 12(2): 105–116.
Wang Y, Wu Z Y, Chen X S, et al. optimization algorithm for multi-agent job integration for fourth party oriented logistics[J]. Journal of Management Sciences in China, 2009, 12(2): 105–116. DOI:10.3321/j.issn:1007-9807.2009.02.012 |
| [2] |
徒君, 黄敏.
基于契约设计的第四方物流质量风险管理[J]. 信息与控制, 2014, 43(3): 276–281.
Tu J, Huang M. Contract design based quality risk management for fourth party logistics[J]. Information and Control, 2014, 43(3): 276–281. |
| [3] | Cui Y, Huang M, Yang S X, et al. Fourth party logistics routing problem model with fuzzy duration time and cost discount[J]. Knowledge-Based Systems, 2013, 50: 14–24. DOI:10.1016/j.knosys.2013.04.020 |
| [4] | Gattorna J. Strategic supply chain alignment:Best practice in supply chain management[M]. 6th ed. Aldershot, UK: Gower Publishing Company, 1998: 425-445. |
| [5] | Yao J M. Decision optimization analysis on supply chain resource integration in fourth party logistics[J]. Journal of Manufacturing Systems, 2010, 29(4): 121–129. DOI:10.1016/j.jmsy.2010.12.002 |
| [6] |
崔妍, 黄敏, 王兴伟.
考虑中转发车时间4PLRP的模糊规划模型与算法[J]. 系统工程学报, 2012, 27(4): 535–542.
Cui Y, Huang M, Wang X W. Fuzzy programming model and algorithm of fourth party logistics routing problem by considering travel schedule[J]. Journal of Systems Engineering, 2012, 27(4): 535–542. DOI:10.3969/j.issn.1000-5781.2012.04.015 |
| [7] | Huang M, Ren L, Lee L H, et al. Model and algorithm for 4PLRP with uncertain delivery time[J]. Information Sciences, 2016(330): 211–225. |
| [8] | Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254–265. DOI:10.1287/opre.35.2.254 |
| [9] | Li X, Ying W Y, Liu W H, et al. The decision optimization model of 4PL[C]//IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ, USA: IEEE, 2003, 1241-1245. |
| [10] |
崔妍, 黄敏, 王兴伟.
带有费用折扣的第四方物流路径问题的研究[J]. 系统仿真学报, 2013, 25(4): 714–721.
Cui Y, Huang M, Wang X W. Research on fourth party logistics routing problem with cost discount[J]. Journal of Systems Simulation, 2013, 25(4): 714–721. |
| [11] | Chen J Q, Wang S, Li X, et al. Directed graph optimization model and its solving method based on genetic algorithm in fourth party logistics[C]//IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ, USA: IEEE, 2003: 1961-1966. |
| [12] | Bo G H, Huang M, Ip W H, et al. The harmony search for the routing optimization in fourth party logistics with time windows[C]//IEEE Congress on Evolutionary Computation. Piscataway, NJ, USA: IEEE, 2009: 962-967. |
| [13] |
黄敏, 崔妍, 林婉婷, 等.
带有费用折扣的多任务第4方物流路径优化问题[J]. 控制与决策, 2013, 28(7): 997–1001.
Huang M, Cui Y, Lin W T, et al. Multi-task fourth party logistics routing problem with cost discount[J]. Control and Decision, 2013, 28(7): 997–1001. |
| [14] |
薄桂华, 黄敏, 王洪峰.
4PL路径优化问题0-1规划模型与求解[J]. 控制工程, 2013, 20(2): 239–242.
Bo G H, Huang M, Wang H F. 0-1 programming model and solution to fourth-party logistics routing problem with time windows[J]. Control Engineering of China, 2013, 20(2): 239–242. DOI:10.3969/j.issn.1671-7848.2013.02.011 |
| [15] | Tao Y, Chew E P, Lee L H, et al. A column generation approach for the route planning problem in fourth party logistics[J]. Journal of the Operational Research Society, 2017, 68(2): 165–181. DOI:10.1057/s41274-016-0024-3 |
| [16] | Huang M, Cui Y, Yang S X, et al. Fourth party logistics routing problem with fuzzy duration time[J]. International Journal of Production Economics, 2013, 145(1): 107–116. DOI:10.1016/j.ijpe.2013.03.007 |
| [17] |
任亮, 黄敏, 王兴伟.
考虑客户拖期厌恶行为的第四方物流路径优化问题[J]. 计算机集成制造系统, 2016, 22(4): 1148–1154.
Ren L, Huang M, Wang X W. Fourth party logistics routing problem considering tardiness aversion behavior of customer[J]. Computer Integrated Manufacturing Systems, 2016, 22(4): 1148–1154. |
| [18] | Hassin R. Approximation schemes for the restricted shortest path problem[J]. Mathematics of Operations Research, 1992, 17(1): 36–42. DOI:10.1287/moor.17.1.36 |
| [19] | Dorigo M, Maniezzo V, Colorni A. Ant system:Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1): 29–41. DOI:10.1109/3477.484436 |
| [20] | Yu B, Yang Z Z, Yao B Z. An improved ant colony optimization for vehicle routing problem[J]. European Journal of Operational Research, 2009, 196(1): 171–176. DOI:10.1016/j.ejor.2008.02.028 |