考虑支线运输服务的多式联运网络优化*

蒋 洋， 张星臣， 周晓晔

(1. 沈阳工业大学 a. 管理学院， b. 机械工程学院， 沈阳 110870； 2. 北京交通大学 交通运输学院， 北京 100044)

多式联运是实现物流机动灵活、“门到门”服务的最好的运输方式，其中的关键问题之一就是网络优化设计问题[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]。

本文基于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 参数符号

表2 决策变量

(9)

(10)

(11)

(12)

(13)

(14)

(15)

Xik∈{0，1} ∀i∈N，k∈H

(16)

(17)

(18)

(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)

(26)

a0≤wiv≤b0∀v∈V，i∈{0}

(27)

(28)

(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所示，阶段Ⅰ模型通过非枢纽节点归并、干线运输网络设计决策等影响阶段Ⅱ的支线运输服务方案设计，反之亦然。通过Ⅰ、Ⅱ两个阶段之间的相互影响不断反馈调节，最终形成综合优化方案。

图1 算法迭代流程思路

交叉熵算法的核心在于对选择概率at不断进行更新，使得越趋近于最优目标值的方案被选择的概率越大，其他决策方案被选择的概率越小，最终趋近于0，直至满足收敛精度要求终止迭代。算法中，α表示交叉熵算法迭代权重系数；β表示算法迭代终止精度要求；ρ表示分位点；γt表示分位点位置的系统目标值；I表示0-1值。

四、算例分析

选取包含10个点的网络算例对模型和算法的有效性进行测试，各点位置坐标如表4所示，其中拟规划枢纽节点2个，非枢纽节点8个。网络中包含公路和铁路两种运输方式，具体参数如表5所示。假定网络中任意两个节点之间的运输需求均为20吨，配送服务成本cij=1元/(吨·公里)，K=50辆，单车载重=400吨/辆。

表4 网络节点信息

研究基于MATLAB开发算法。交叉熵算法的参数设置如下：Y=500，ρ=0.9，α=0.7，β=1e-5。设置遗传算法中交叉概率为0.9、变异概率为0.1。

表5 模型参数

交叉熵算法收敛性如图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 算例样本配送路径优化结果

图3 枢纽节点支线配送路径

在此算例样本中，枢纽1～3之间选择修建铁路，且在节点1和3处分别建设铁路车站。由于铁路运输区段的服务能力为1 000吨，可以满足运输需求，而且运输成本低廉，单位吨·公里仅为0.2元，配送成本与网络布局、干线运输成本之和为60 203元。

表7 阶段Ⅱ模型与分别优化的结果比较 元

两阶段分别优化所得到的枢纽布局方案为1号点和2号点，且非枢纽节点需求全部归并到2号节点，1号节点不提供任何支线服务。此时干线网络中1号点与2号点之间的运输成本仅为665元，相对较小，但其第二个运行优化阶段，即支线运输服务成本会显著提升，相比本文模型提高了200 435元。基于本文提出的阶段Ⅱ优化决策方法所得到的优化布局方案是1号点和3号点，总成本仅为60 203元，相较分别优化的方法降低成本73%，非枢纽节点会根据具体需求、与枢纽点之间的位置关系等特点进行归并，因此系统性地降低了支线配送距离及成本。

之所以两阶段分别优化的思路会产生需求归并的不合理情况，是因为在阶段Ⅰ多式联运网络设计中模型仅仅考虑了网络设计、枢纽布局以及干线运输成本，而忽略了支线运输服务成本影响。根据模型约束条件式(12)可以看出，当所有非枢纽节点归并于一个枢纽时，干线上的总需求最小，总成本也最低，但会导致配送成本急剧增加。

五、结 论