多式联运是实现物流机动灵活、“门到门”服务的最好的运输方式，其中的关键问题之一就是网络优化设计问题[1]，主要围绕网络设计优化[2-3]、枢纽节点中转服务过程[1]、选址布局优化[4-7]、配送车辆路径优化[8-9]、能力及运力配置[1，10]等方面展开。考虑时间窗的车辆路径问题(VRP with time windows，VRPTW)被广泛应用于物流配送领域，如餐饮配送[11-12]、快递配送等[13]。Bräysy和Gendreau[14-15]对VRPTW问题的建模与求解算法进行了较全面的综述，并按照求解算法将目前研究分为启发式算法与人工智能算法两类。其中，文献[14]侧重于启发式算法在求解VRPTW问题方面的应用，而文献[15]则对VRPTW问题的人工智能算法进行了总结。考虑到车辆路径问题求解的复杂性，相关学者大多采用启发式算法进行求解[16-17]。
单独考虑网络设计或车辆路径优化问题并不一定能保证网络设计合理、运行流畅，因此更多的研究侧重于集成化问题，如生产与分销联合问题，把运输规划和生产集成起来考虑，抽象为“生产
分销”问题、“定位运输”问题、“库存运输”问题等集成优化问题。
“定位运输”问题(location-routing problem，LRP)整合了分销系统设计问题与VRP，起步于20世纪70年代[18]，为资源整合优化配置研究提供了重要借鉴。Xie等[19]针对危险品货物运输提出了枢纽选址与运输路径集成优化的非线性规划模型，将单一运输方式拓展为多方式运输，且考虑了中转换装作业时间成本约束，采用大规模算例证实了模型和算法的有效性。Meisel等[20]提出了基于危险品运输的公铁联运多目标规划模型，解决铁路长距离运输中的运力分配决策问题，包括各铁路班列的开行频次、不同路径不同班列中货流的分布情况等。曾庆成[21]探讨配送中心选址问题与此基础上路径问题的相互影响，建立了配送系统优化的双层规划模型，上层为配送中心选址问题，下层为车辆路径优化问题。王永等[22]提出了一个正逆向结合的应急物流设施定位运输路线安排问题模型。Nagy等指出LRP属于NP难问题，启发式算法是比较可行的求解方法[23]。蒋洋等综述了求解LRP的各类启发式方法，指出大多数求解真实案例的LRP模型都通过启发式方法求解[24]。
本文基于LRP的研究思路，在多式联运背景下探讨网络设计与支线配送路径的综合优化方法，提出Ⅱ阶段决策思路，对枢纽布局、网络设计及支线运输服务设计等进行综合决策，并设计启发式求解算法，为发展基于多式联运的“门到门”物流运输服务提供理论借鉴。
一、问题描述
本文提出Ⅱ阶段决策思路：阶段Ⅰ中管理者对多式联运的干线运输网络布局进行规划，力求干线运输中的固定成本与可变成本之和最小，同时对干线运输网络中的中转集散枢纽布局进行设计；阶段Ⅱ中管理者基于阶段Ⅰ提供的枢纽及网络布局规划决策和非枢纽节点的需求归并情况，针对任意一个枢纽节点进一步对支线运输服务方案进行设计，决策内容包括各支线服务线路所服务的对象及顺序情况。由于在此过程中考虑了服务时间窗因素，因此阶段Ⅱ可以借鉴带时间窗的车辆路径问题的研究方法。
定义多式联运网络的节点集合为N，其中备选枢纽节点集合H⊆N，h∈H；非枢纽节点集合F⊆N；运输方式集合为M，m∈M。
本文研究假设如下：
(1) 干线运输网络中各个枢纽节点间可设计多种不同运输方式，支线运输服务只能通过公路运输；
(2) 同种运输方式的运输能力一致，忽略因等级等差异造成的影响；
(3) 不经过枢纽中转的运输需求量不在本文研究范围内，如归并于同一枢纽的非枢纽节点之间的运输需求。
二、模型构建
阶段Ⅰ和阶段Ⅱ的决策优化模型可分别表述为式(1)和(20)，表1、2分别给出了模型参数及变量。
阶段Ⅰ：
(1)
s.t.
(2)
Xik≤Xkk ∀k∈H，i∈N
(3)
(4)
(5)
(6)
(7)
(8)
表1 参数符号
qst节点s与t之间的货运需求CHmk在k点建设方式m枢纽的成本CLmkp枢纽k与p之间方式m的区段建设费用CAPm运输方式为m的区段运输能力CAP_Interm1m2运输方式为m1与m2的之间的转运能力cmkp枢纽k与p之间,方式m的单位运输距离成本ocmkm方式的枢纽k的单位服务成本cij枢纽与非枢纽节点构成的支线运输网络中区段单位运输成本D规划枢纽的数量K可支配的支线配送车辆数上限CAPv配送服务车辆v的运输载重能力αm枢纽k与p之间,运输方式m的规模经济系数(成本折减)[ai,bi]支线节点时间窗si服务时间
表2 决策变量
Xik值为1,则非枢纽节点i∈F由枢纽点k进行配送服务,否则值为0Hmk值为1,则在k∈H建设m型枢纽,否则值为0Zmkp值为1,则枢纽k与p之间布局运输方式为m的路线,否则值为0yst,mkp值为1,则s与t间需求经过枢纽k与p且运输方式为m,否则值为0xijv值为1,则支线中(i,j)由车辆v∈V服务,i={j,k∀k∈H,Xik=1}wiv车辆v对支线节点i的服务开始时间
(9)
∀i，j∈N∶i≠j，k∈H
(10)
∀s，t∈N∶s≠t，k，p∈H∶k<p
(11)
(12)
∀k，p∈H，k≠p
(13)
(14)
∀k∈H
(15)
Xik∈{0，1} ∀i∈N，k∈H
(16)
(17)
(18)
p∈H∶k≠p，m∈M
(19)
式(1)中f(xijv)为支线运输车辆进行货物取送服务成本，该车辆围绕枢纽节点k∈H对其支线进行服务，该成本由阶段Ⅱ求解。阶段Ⅱ参考带时间窗的车辆路径问题进行建模，其中枢纽节点“0”(k∈H)由阶段Ⅰ给出。
阶段Ⅱ：
(20)
s.t.
(21)
(22)
(23)
(24)
xijv(wiv+si+tij-wjv)≤0 ∀v∈V，i，j∈N
(25)
∀v∈V，i∈N
(26)
a0≤wiv≤b0 ∀v∈V，i∈{0}
(27)
(28)
∀i∈N\H
(29)
xijv≥0 ∀v∈V，i，j∈N
(30)
xijv∈{0，1} ∀v∈V，i，j∈N
(31)
阶段Ⅰ中目标函数实现了系统总成本最小化，包括枢纽及线路的建设成本以及干、支线运输服务成本。约束条件式(2)、(3)表示一个非枢纽节点只能够被一个枢纽节点服务；约束条件式(4)要求枢纽节点从集合H中产生；约束条件式(5)表示网络中布局D个枢纽；式(6)～(9)表示枢纽间运输方式应规划约束；平衡流约束以及流量运行规划约束如式(10)和(11)所示；式(12)计算结果表示由该枢纽点产生的或途径中转的总需求量；式(13)为干线运输网络中枢纽间的运输成本；式(14)～(15)为线路及枢纽节点能力约束；式(16)～(19)为0-1变量定义。阶段Ⅱ为带时间窗的车辆路径问题，该阶段目标为实现各支线运输总成本最小。约束条件式(21)确保了每个支线节点需求只被一条路径服务；约束条件式(22)～(24)确保了任意一条路径由一辆车进行服务；约束条件式(25)～(27)是时间窗约束；约束条件式(28)为车辆负载约束。式(29)表示枢纽所服务客户的需求总量，是基于阶段Ⅰ的货流归并后的结果，包括了两部分需求的合并：一是归并客户与枢纽节点之间的货运需求量；二是归并节点与其他节点间需要经过枢纽节点中转的需求量。式(30)、(31)定义了阶段Ⅱ中的关键决策变量。
三、交叉熵为主体的启发式方法
旅行商问题是VRP的一个特例。由于旅行商问题已被证明是NP难题，因此VRPTW也是NP难题。本文设计以交叉熵算法为主体的启发式求解算法进行求解，算法流程借鉴文献[24]的思路，主体算法流程伪代码如表3所示，其中嵌入遗传算法对模型阶段Ⅱ进行求解。遗传算法与交叉熵算法类似，都是一种优胜劣汰的随机优化搜索算法，其主要优势表现在优化过程中只需要适应度函数作为依据，不需要其他信息辅助，已在货物配送路径优化领域获得广泛应用[2]。
表3 基于交叉熵主体算法的流程
步骤迭代过程1初始化样本S=1000;迭代次数初始化time=1;判断变量BOOL=02判断BOOL=03如果time=1,则初始化算法选择概率at={…,0.5,…};依选择概率随机产生一个阶段Ⅰ中的样本,调用VRPTW的遗传算法,计算每个枢纽为配送中心的支线运输服务成本;遗传算法采用自然数编码的方法,交叉策略中将每代种群中适应度值最大的染色体复制后直接进入,下一代种群采用轮盘旋转法从父代染色体种群中随机产生,变异策略用交换策略进行,即随机交换选取染色体内的2个基因值并交换位置4计算系统目标值5依据成本由低到高排序,并选取分位点值γt=r(1-ρ)N6判断如果TotalCost≤γt,那么令I{r(Xi)≥γt}=1;否则I{r(Xi)≥γt}=07更新选择概率at=αat+(1-α)at-1,其中at=∑i∈YI{r(Xi)≤γt}xi∑i∈YI{r(Xi)≤γt}8判断max(min(at,1-at))≤β,那么BOOL=1;否则BOOL=0;time=time+1;转步骤2
交叉熵为主体的启发式算法思路如图1所示，阶段Ⅰ模型通过非枢纽节点归并、干线运输网络设计决策等影响阶段Ⅱ的支线运输服务方案设计，反之亦然。通过Ⅰ、Ⅱ两个阶段之间的相互影响不断反馈调节，最终形成综合优化方案。
图1 算法迭代流程思路
交叉熵算法的核心在于对选择概率at不断进行更新，使得越趋近于最优目标值的方案被选择的概率越大，其他决策方案被选择的概率越小，最终趋近于0，直至满足收敛精度要求终止迭代。算法中，α表示交叉熵算法迭代权重系数；β表示算法迭代终止精度要求；ρ表示分位点；γt表示分位点位置的系统目标值；I表示0-1值。
四、算例分析
选取包含10个点的网络算例对模型和算法的有效性进行测试，各点位置坐标如表4所示，其中拟规划枢纽节点2个，非枢纽节点8个。网络中包含公路和铁路两种运输方式，具体参数如表5所示。假定网络中任意两个节点之间的运输需求均为20吨，配送服务成本cij=1元/(吨·公里)，K=50辆，单车载重=400吨/辆。
表4 网络节点信息
编号坐标经度坐标纬度aibisi110914195434902111140870923903184485179044917624390510813924299906510405453907953924429081101461013609095490495490101522127790
研究基于MATLAB开发算法。交叉熵算法的参数设置如下：Y=500，ρ=0.9，α=0.7，β=1e-5。设置遗传算法中交叉概率为0.9、变异概率为0.1。
表5 模型参数
干线网络参数数值公路运输成本(元/(吨·公里))0.8铁路运输成本(元/(吨·公里))0.2公路区段年平均折旧成本(元/公里)5铁路区段年平均折旧成本(元/公里)10公路枢纽年平均折旧成本(元/座)0铁路枢纽年平均折旧成本(元/座)1000枢纽中转作业服务成本(元/吨)0.5公路区段运输能力(吨)600铁路区段运输能力(吨)1000枢纽中转服务能力(吨)500
交叉熵算法收敛性如图2所示。经过有限次迭代得到最优优化方案，可以看出交叉熵算法具有较好的稳定性，收敛速度较快。在前20次迭代过程中，系统目标值收敛速度明显；在之后的迭代过程中系统目标值下降缓慢，30～40次迭代后达到误差精度范围。算例样本配送路径优化结果如表6所示。由表6可知，最优结果显示选取1和3号点为枢纽节点，其余为非枢纽点。以1号点为中心的最优支线运输服务路径包括两条：1→8→1，1→5→2→1(图3a)；以3号点为中心的最优支线运输服务路径包括两条：3→10→4→6→3，3→7→9→3(图3b)。
图2 交叉熵算法收敛性
表6 算例样本配送路径优化结果
枢纽非枢纽车辆路径路径货流量吨行驶里程公里122584679101-5-2-12801-8-11403-10-4-6-33003-7-9-320017.832.2
图3 枢纽节点支线配送路径
在此算例样本中，枢纽1～3之间选择修建铁路，且在节点1和3处分别建设铁路车站。由于铁路运输区段的服务能力为1 000吨，可以满足运输需求，而且运输成本低廉，单位吨·公里仅为0.2元，配送成本与网络布局、干线运输成本之和为60 203元。
为进一步说明本文提出Ⅱ阶段优化方法的效果，将本文提出的Ⅱ阶段优化决策方法同两阶段分别优化的结果进行了对比(先“网络设计布局优化”再“定位运输”)，模型和算法的参数均保持一致，结果如表7所示。
表7 阶段Ⅱ模型与分别优化的结果比较 元
总成本干线运输成本支线配送成本支线里程公里支线车辆数辆6020336608.02359550.05224700665.2224030726.22
两阶段分别优化所得到的枢纽布局方案为1号点和2号点，且非枢纽节点需求全部归并到2号节点，1号节点不提供任何支线服务。此时干线网络中1号点与2号点之间的运输成本仅为665元，相对较小，但其第二个运行优化阶段，即支线运输服务成本会显著提升，相比本文模型提高了200 435元。基于本文提出的阶段Ⅱ优化决策方法所得到的优化布局方案是1号点和3号点，总成本仅为60 203元，相较分别优化的方法降低成本73%，非枢纽节点会根据具体需求、与枢纽点之间的位置关系等特点进行归并，因此系统性地降低了支线配送距离及成本。
之所以两阶段分别优化的思路会产生需求归并的不合理情况，是因为在阶段Ⅰ多式联运网络设计中模型仅仅考虑了网络设计、枢纽布局以及干线运输成本，而忽略了支线运输服务成本影响。根据模型约束条件式(12)可以看出，当所有非枢纽节点归并于一个枢纽时，干线上的总需求最小，总成本也最低，但会导致配送成本急剧增加。
五、结 论
以铁路开展“门到门”现代物流运输服务为背景，将多式联运网络设计问题与战术规划层面的“定位运输”问题相结合，从系统全局优化的角度探索多式联运网络优化及支线运输服务方案设计的综合决策方法。研究结论如下：
(1) 将多式联运网络设计问题与“定位运输”问题融合，并提出了阶段Ⅱ的优化决策方法。根据该方法中两个阶段相互反馈和相互影响的作用机理，设计了以交叉熵为主体的嵌入了基于遗传算法带时间窗的车辆路径问题求解思路，并基于MATLAB平台得以实现。算例分析表明算法有效且计算效率令人满意。
(2) 研究利用一个10个点的算例网络对模型优化结果进行分析，并将本文提出的阶段Ⅱ的优化决策方法同两阶段分别优化(先“网络设计布局优化”再“定位运输”)的结果进行了对比。结果显示，在模型和算法的参数均一致的前提下，系统总成本降低了73%。
[1] Meng Q，Wang X.Intermodal hub-and-spoke network design：incorporating multiple stakeholders and multi-type containers [J].Transportation Research Part B Methodological，2011，45(4)：724-742.
[2] 刘艳秋，焦妮，张义华.基于低碳理念的多级物流网络优化设计 [J].沈阳工业大学学报(社会科学版)，2015，37(4)：404-409.
[3] 王保华，何世伟.综合运输体系下快捷货物运输网络资源配置优化模型及算法 [J].铁道学报，2017，39(2)：10-17.
[4] 李婷婷，宋瑞，何世伟，等.基于分层布局的城市群综合客运枢纽优化模型 [J].中国公路学报，2016，29(2)：116-122.
[5] Yuan Y，Yu J.Locating transit hubs in a multi-modal transportation network：a cluster-based optimization approach [J].Transportation Research Part E Logistics & Transportation Review，2018，114(2)：85-103.
[6] 刘丽娜，张青山，徐伟.双渠道采销模式下装备制造企业选址影响因素分析 [J].沈阳工业大学学报(社会科学版)，2018，11(4)：320-327.
[7] Ambrosino D，Sciomachen A.A capacitated hub location problem in freight logistics multimodal networks [J].Optimization Letters，2016，10(5)：1-27.
[8] Ldiri A，Oukarfi M，Boulmakoul A，et al.A distributed approach for shortest path algorithm in dynamic multimodal transportation networks [J].Transportation Research Procedia，2017，27(2)：294-300.
[9] 周骞，白云卯，徐春龙.基于遗传算法的多式联运物流运输配送路径优化研究 [J].物流工程与管理，2015，37(1)：89-91，104.
[10] 蒋洋，张星臣，周晓晔.公铁网络联运方案设计 [J].交通运输系统工程与信息，2018，18(6)：222-228.
[11] Wu X，Nie L，Xu M.Designing an integrated distribution system for catering services for high-speed railways：a three-echelon location routing model with tight time windows and time deadlines [J].Transportation Research Part C Emerging Technologies，2017，74(5)：212-244.
[12] 陈萍，李航.基于时间满意度的O2O外卖配送路径优化问题研究 [J].中国管理科学，2016，24(S1)：170-176.
[13] 张如云，刘清.考虑低碳的城市配送车辆路径优化模型研究 [J].工业工程与管理，2015，20(4)：29-34.
[14] Bräysy O，Gendreau M.Vehicle routing problem with time windows，part Ⅰ：route construction and local search algorithms [J].Transportation Science，2005，39(1)：104-118.
[15] Bräysy O，Gendreau M.Vehicle routing problem with time windows，part Ⅱ：metaheuristics [J].Transportation Science，2005，39(1)：119-139.
[16] Ma M，Mka G，Ri H，et al.Solving the feeder vehicle routing problem using ant colony optimization [J].Journal of Computational Science，2017，21(4)：255-262.
[17] Yao B，Yu B，Hu P，et al.An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot [J].Annals of Operations Research，2016，242(2)：1-18.
[18] 汪寿阳，赵秋红，夏国平.集成物流管理系统中的定位运输线路安排问题的研究 [J].管理科学学报，2000，3(2)：69-75.
[19] Xie Y，Wei L，Wen W，et al.A multimodal location，routing model for hazardous materials transportation [J].Journal of Hazardous Materials，2012(43)：135-141.
[20] Meisel F，Kirschstein T，Bierwirth C.Integrated production and intermodal transportation planning in large scale production-distribution-networks [J].Transportation Research Part E Logistics & Transportation Review，2013，60(6)：62-78.
[21] 曾庆成，杨忠振，蒋永雷.配送中心选址与车辆路径一体化优化模型与算法 [J].武汉理工大学学报(交通科学与工程版)，2009，4(2)：267-270.
[22] 王永，胥冬川，农兰晶.震后过渡阶段应急物流系统的定位运输路线安排问题研究 [J].计算机应用，2015，35(1)：243-246.
[23] Nagy G，Salhi S.Location-routing：issues，models and methods [J].European Journal of the Operational Research，2007，177(2).649-672.
[24] 蒋洋，张星臣，王永亮.多式联运运输方案选择的交叉熵方法 [J].交通运输系统工程与信息，2012，12(5)：20-25.