末端配送服务模式与路径联合优化

杨京帅，杨玉娥，李嫚嫚，李园园

(长安大学 汽车学院，陕西 西安 710021)

末端配送是与客户联系最为紧密的物流环节，一方面影响客户的物流服务质量，另一方面又是物流成本节约的重要领域.末端配送成本约占运输总成本的28%[1]，合理规划配送路径可以显著降低配送成本，路径规划问题因此得到广泛的研究[2].末端配送服务模式影响客户的物流服务质量感知与满意度[3]，企业由此推出了不同的末端配送服务模式.由于末端配送服务模式的配送网络和服务形式存在差异，不同配送服务模式的配送路线和服务成本不同[4].如何兼顾末端配送服务质量与成本改善，协同决策末端配送服务模式和配送路径，是值得物流企业探寻的一个问题.

目前常见的末端配送服务模式包括送货上门、自提柜和自提点3种模式[5].送货上门是物流企业将货物送达客户指定地点的服务模式；自提柜是设置在公共区域的自助取货柜，存放的货物数量及种类有一定限制，客户可在任意时间取件，但是初始投资成本较高[4]；自提点是与物流企业合作的超市、店铺等，投资成本低，客户只能在自提点开放时间段取货[6].末端配送服务模式与路径规划的协同优化问题是在考虑多种末端配送服务模式的情况下，以总成本最小化[7]或总运输距离最小化[8-9]等作为优化目标，对客户的末端配送服务模式和配送路线进行综合决策.Du等[10-11]研究末端配送服务模式与同时取送货型路径规划的联合优化问题.Enthoven等[12-13]研究送货上门和自提柜模式下的两阶段车辆路径规划问题.Zhou等[14]进一步研究多个配送中心下的两阶段车辆路径规划问题.周翔等[15-16]考虑自提柜位置对配送路径的影响，研究多种末端配送服务模式共存情景下的自提柜选址和配送路径联合优化问题.常见的末端配送服务模式与路径联合优化问题求解算法有模拟退火算法[11]、大邻域搜索算法[12]、遗传算法[17]和分支定界算法[18].在进行配送路径规划时，鲜有研究同时考虑到送货上门、自提柜和自提点3种末端配送服务模式，从而无法充分发挥配送系统的最大效能.Suwatcharachaitiwong等[19]虽然考虑到3种末端配送服务模式，但是只从物流服务商角度对末端配送服务模式进行选择，忽略客户对于不同模式的偏好，难以高质量提供配送服务.

为了弥补现有研究的不足，本研究同时考虑送货上门、自提柜和自提点3种末端配送服务模式，从平衡物流企业成本与服务质量的新角度出发，研究末端配送服务模式与路径联合优化问题.以配送成本和客户满意度为双目标，考虑到车辆容量限制、客户收货模式以及收货时间窗等约束建立模型，改进NSGA-Ⅱ算法求解模型实现客户配送模式与配送路径的联合优化，为建立高效、高服务质量的末端配送系统提供决策依据与方法.

1 问题描述

末端配送服务模式与路径联合优化问题如图1所示.具体可描述为：在某配送区域存在1个配送中心以及对客户点提供配送服务的a个自提柜和b个自提点.每个客户点可接受多种末端配送服务模式，不同模式的对比如表1所示[3-4]，各种末端配送服务模式的客户满意度与物流企业配送成本不同.在兼顾配送成本和客户满意度的前提下，决策该区域的配送路径和客户接受的末端配送服务模式.

图1 末端配送服务模式与路径联合优化问题示意图Fig.1 Joint optimization diagram of terminal distribution service mode and routing

表1 不同末端配送服务模式对比Tab.1 Comparison of different terminal distribution service modes

2 末端配送服务模式与路径联合优化模型构建

2.1 模型假设

1）各个客户点的位置、需求量、服务时间窗和可接受的末端配送服务模式已知；2）各个自提柜或自提点的位置和所能服务的客户已知，并且容量是能够满足配送需求；3）考虑到3种末端配送服务模式，分别为送货上门、自提柜和自提点；4）单配送中心，车辆只提供配送服务，不提供收揽服务；5）每个客户点仅被服务1次，不存在二次配送的情况；6）配送车辆为同类型车，客户点需求量不可拆分.

2.2 符号定义

构建末端配送服务模式与路径联合优化模型所用符号如表2所示.

表2 所提模型定义的符号及含义Tab.2 Notations and meanings of proposed model

2.3 模型构建

建立的末端配送服务模式与路径联合优化模型为

式中：T1为配送总成本；Cost_TW为时间窗惩罚成本.式(1)为目标函数，表示最小化由车辆运输成本、车辆固定成本、配送服务成本和时间窗惩罚成本构成的配送总成本.

式中：T2为客户满意度.式(2)为最大化客户满意度，也是一个目标函数.

式(4)为每位客户有且仅有一辆车采用一种配送模式为其提供服务.

式(5)为末端配送服务模式选择约束.

式(6)为限制每位客户选择的模式，和配送路径决策出的模式为同种模式.

式（7～9）为路径约束.

式(10)限制一条路径由同一辆车行驶.

式(11)为车辆到达客户点的时间约束.

式(12)为车辆到达客户点的配送量约束.

式(13)为车辆的最大载重量约束.

式（14～15）为决策变量的取值约束.

3 末端配送服务模式与路径联合优化模型求解

上述模型是具有多约束的双目标混合整数规划模型，混合整数规划模型的求解是一个NP-Hard问题，为此采用元启发式算法求解模型[20].元启发式算法中的NSGA-Ⅱ是目前应用最广泛的多目标进化算法之一，能够得到Pareto最优解集，使得各目标函数都尽量达到最优[21].NSGA-Ⅱ具有适用性广泛、求解速度快等优点[22]，因此改进的NSGA-Ⅱ用于模型求解，具体流程如图2所示，其中Gen为种群迭代次数，算法涉及的具体操作展示在3.1节～3.5节.

图2 改进NSGA-Ⅱ的流程Fig.2 Improved NSGA-Ⅱ flowchart

3.1 编码

末端配送服务模式与路径联合优化问题，需要将客户服务模式、配送车辆指派及配送路径等决策目标融入编码过程，将问题的实际方案表达为染色体基因.本研究采用实数编码，设定每条染色体长度为2×A+B+1（A、B分别为客户点和配送车辆数量），前A位为末端配送服务模式，后续基因为车辆配送路径.以5个客户点生成的染色体为例（如图3所示），客户1、3采用上门服务，客户2、5采用自提柜服务，客户4采用自提点服务，2辆车的配送路径由0划分.

图3 改进NSGA-Ⅱ的染色体编码Fig.3 Chromosomal coding of improved NSGA-Ⅱ

3.2 初始种群

为了提高初始解的质量，采用节约里程法（clarke-wright，CW）和随机生成相结合的策略生成初始种群.CW算法的原理是在满足车辆容量限制的条件下，尽可能多地将2个配送回路合并，以此减小运输距离.利用CW算法生成初始解质量较高但易造成种群单一化，因此30%的初始解由CW算法生成，其余70%初始解随机生成.此方法既加快了收敛，又保证了种群的多样性.

3.3 快速非支配排序

设共有m个优化目标，若对于任意优化目标k(k=1,2,···,m) 有fk(x1) 不 劣 于fk(x2)，并且至少在1个优化目标上有fk(x1) 优于fk(x2) ，则称解x1支配解x2.若是x1没有被其他解所支配，则称x1为非支配解（即Pareto解）.按照此定义对所有染色体进行排序，称为快速非支配排序.具体操作过程是从所有染色体中选择非支配染色体，得到第1层级的非支配染色体，然后从其他未划分层级的染色体中再次选择非支配染色体，得到第2层非支配染色体，重复此过程直到所有染色体都被划分层级.通过快速非支配排序，可以得到Pareto解.Pareto解对应的目标函数值（Pareto前沿），如图4所示.

图4 Pareto前沿示意图Fig.4 Pareto frontier diagram

3.4 拥挤度计算

NSGA-Ⅱ用拥挤度表示种群染色体的空间密度，染色体的拥挤度越大代表种群多样性越好.以图5所示染色体分布为例，两端的染色体拥挤度设为 ∞，其余染色体的拥挤度是距离染色体最近两点构成的矩形长宽之和，即

图5 染色体i拥挤度Fig.5 Crowded degree of Chromosome i

式中：id为染色体i的拥挤度，fk(i) 为染色体i在优化目标k的目标函数值.

3.5 遗传算子

3.5.1 选择算子 在进行非支配排序和拥挤度计算后，运用竞标赛机制选择父代染色体.随机选出2条不同的染色体，将排序等级较高的作为父代染色体，如果选出的2条染色体排序等级相同，则选择拥挤度较大的成为父代染色体.

3.5.2 交叉算子 交叉是对生物遗传过程中染色体基因重组的模仿，本研究采用多点交叉和POCSX[23]交叉策略.多点交叉是指在父代染色体的末端配送服务模式段和配送路径段分别随机选择一对交叉点，交换相应交叉点间的基因片段.如图6所示，父代1和父代2交叉点间的基因片段（加粗数字所示，下同）进行交换得到子代1和子代2.对交叉后的子代染色体进行有效性检验，如果出现重复节点或车辆超载等情况，则将造成冲突的基因取消交换.

当最优解重复出现10次，表明算法陷入局部最优.为了提高种群进化效率，染色体配送路径段采取POCSX交叉.POCSX交叉是以子代上一个添加的节点和待选基因池中节点的代价（一般以节点间距离表示）确定子代的下一个节点.待选基因池的生成规则为待选基因池的第1位基因取父代1的第1个基因，剩余基因在父代2中随机选取.如图7所示，若设待选基因池大小为3，则需从父代选择3个基因节点构成待选基因池[5,4,3].在子代首位添加0表示车辆配送的开始，并将待选基因池中距离节点0最小的节点5添进子代，同时将父代中的节点5删除；按照待选基因池生成规则生成新的待选基因池 [2,1,3]，并将待选基因池中与节点5距离最短的节点1添加到子代，同时父代删除节点1，重复此过程直至删除父代染色体全部节点生成子代.

3.5.3 变异算子 变异是对生物遗传过程中染色体基因突变的模仿.本研究采取反转突变策略，即在一条染色体的配送服务模式段和配送路径段分别随机选择一对变异点，将变异点间的基因序列颠倒.如图8所示，将父代变异点1和2之间的染色片段、变异点3和4之间的染色片段都反转得到子代.

图8 改进NSGA-Ⅱ的反转变异算子Fig.8 Inversion mutation operator of improved NSGA-Ⅱ

3.5.4 灾变算子 灾变模仿了自然进化中的重大灾害，是帮助算法跳出局部最优的一种手段.当最优解连续重复出现10次时，算法进行灾变操作，即只保留当前种群中质量最好的前30%的染色体，其余70%的染色体重新生成.

4 算例分析

基于Solomon RC102算例，对模型和算法进行验证.为了使案例符合研究问题，根据自提柜和自提点数量与人口密度显著正相关的特点[24]，增加自提柜和自提点位置；按照客户对送货上门、自提柜、自提点的满意度高低[3,25]为客户设置可选末端配送服务模式.例如，客户对送货上门模式的满意度最高，则将送货上门作为可选模式的客户数量设置成最多.其余案例参数参照文献[26-27]设置，具体如表3所示.改进NSGA-Ⅱ利用Matlab编译，在配置为Intel(R)Core(TM)i5-5200U、2.20 GHz、4 GB RAM，Windows10(64位)的电l脑上运行.算法参数如下：种群规模为100，交叉概率为0.75，变异概率为0.10，Pareto解集数量为150.

表3 算例参数及取值Tab.3 Experimental parameters and values

4.1 模型验证

为了验证末端配送模式与路径联合优化模型的正确性，调用求解器GUROBI对5个客户点的小规模算例进行求解.在调用求解器GUROBI对模型进行求解时，采用将配送总成本T1作为目标函数，将客户满意度 C S转化为约束条件的处理方法.如式（17）所示，设置最小满意度值 C Smin作为模型的1个约束条件，从而将双目标函数转化为单目标函数，同时降低模型求解的复杂程度.

GUROBI的求解结果如表4所示.从表4可以看出，所得末端配送服务模式和路径方案满足问题约束，即客户的末端配送服务模式满意度和车辆载重约束，表明所建模型有效.

表4 GUROBI对小规模算例的求解结果Tab.4 GUROBI results of small-scale example

4.2 算法性能分析

4.2.1 算法稳定性 为了验证改进NSGA-Ⅱ的稳定性，对11个算例求解20次.11个算例求解20次的配送总成本平均解和最优解如表5所示.Gap为 平均解C2和 最优解C1差异的百分比，即 Gap=(C2-C1)/C1.表5显示，改进NSGA-Ⅱ求解20次的平均解和最优解相对误差较小，平均值为1.23%，说明改进NSGA-Ⅱ在求解末端配送服务模式与路径联合优化问题时具有较好的稳定性.

表5 改进NSGA-Ⅱ算法稳定性分析Tab.5 Algorithm stability analysis of improved NSGA-Ⅱ

4.2.2 算法性能优越性 为了验证改进NSGA-Ⅱ的性能，本节将改进NSGA-Ⅱ与GUROBI和传统NSGA-II算法的求解结果进行对比，17个中小案例的求解结果如表6所示.其中，GUROBI列展示的结果为2000 s求解时间限制下的结果，“-”表 明 在 限 制 时 间 内 没 有 发 现 可 行 解.G ap1和Gap2分别为传统NSGA-Ⅱ和改进NSGA-Ⅱ求得的配送总成本最优值C3 ,C1与GUROBI求得的配送总成本最优值C4差 异的百分比，即 Gap1=(C3-C4)/C4，Gap2= (C1-C4)/C4.

表6 三种算法求解末端配送服务模式与路径联合优化模型的性能Tab.6 Performances of three algorithms to solve terminal distribution service mode and routing model

通过对比求解器GUROBI和改进NSGA-Ⅱ对相同案例的求解结果可知，当客户规模小于15时，GUROBI和改进NSGA-Ⅱ的求解质量基本相同，平均差异小于0.1%.当客户规模大于15时，75%的案例，改进NSGA-Ⅱ得到的解比GUROBI优.GUROBI的求解时间会随着客户规模的增大急剧增加.当客户规模为10时，GUROBI就需要1907 s的求解时间.而改进NSGA-Ⅱ的求解时间增加并不明显，最大求解时间也不超过240 s，只是GUROBI所用求解时间的1/10.除此之外，改进NSGA-Ⅱ可以一次性求解出Pareto前沿，而GUROBI只能求解出一个解.对比传统NSGA-Ⅱ和改进NSGA-Ⅱ的结果可知，求解时间平均仅增加23 s，求解质量平均提升了3.37%.综上可知，所设计的改进NSGA-Ⅱ求解效果优于GUROBI和传统NSGA-Ⅱ.

4.2.3 Pareto解集 图9展示60个客户算例求解的Pareto前沿，可以看出客户满意度S和配送总成本C存在正相关关系.送货上门、自提柜和自提点3种服务模式的服务成然依次递减，是以客户满意度降低为代价.在实际操作中，物流企业需对配送服务质量和成本进行权衡.

图9 60个客户案例求解到的Pareto前沿Fig.9 Pareto frontier of 60 customer cases

4.3 敏感度分析

4.3.1 末端配送服务模式分析 为了体现末端配送服务模式与路径联合决策模型的优势，将采用送货上门、自提柜和自提点的单一末端配送服务模式与三种配送模式混合使用下的配送总成本与客户满意度进行对比分析.客户的可选末端配送服务模式限定为单一模式，即成为相应模式下的只考虑配送成本的路径决策问题.客户不可接受末端配送服务模式的满意度变为相应末端配送服务模式的0.5倍，5个算例求解20次所得配送成本最低的解如表7所示.

从表7可以看出，送货上门服务模式能够得到最高的客户满意度，但其配送成本也最高；自提点服务模式的配送成本最低，客户满意度也最低；自提柜模式的成本和客户满意度均介于送货上门和自提点模式之间.混合模式与自提柜和自提点模式相比，成本分别增加了3.11%和18.71%，但客户满意度分别提高了22.48%和47.78%，整体提升了19.37%和29.07%；与送货上门相比，客户满意度降低了8.56%，同时配送成本降低了20.57%，整体提升了12.01%.综合来看，混合利用多种末端配送服务模式能够发挥各模式的优势，达到 既控制配送成本又能提升客户满意度的目标.4.3.2 自提柜和自提点数量分析 将100个客户算例中的自提柜和自提点数量均增加3个，相同客户满意度下成本最低的配送方案如表8所示.表中Ct、Cf、Cs和Cw分别为运输成本、车辆固定成本、服务成本、时间窗成本.增加自提柜和自提点数量后配送总成本降低了115.94元，其中运输成本降低了11.88%.这说明管理者在投资建设成本允许的情况下，可以通过适当增加自提点和自提柜数量降低配送总成本.

表7 不同末端配送服务模式的配送总成本与客户满意度Tab.7 Distribution cost and customer satisfaction with different terminal distribution service modes

表8 不同自提柜和自提点数量下成本最低的配送方案Tab.8 Lowest cost distribution scheme with different number of parcel lockers and pick-up points

4.3.3 时间窗宽度分析 在分析时间窗宽度影响时，保持其它参数不变.在不同时间窗宽度下，利用求解器GUROBI求解8个客户的小规模算例，利用改进NSGA-Ⅱ求解100个客户的大规模算例，结果如图10所示.图中Cmin 为所得最低配送总 成本，η为原时间窗宽度的变化倍数.

图10 不同时间窗宽度倍数下的最低配送成本Fig.10 Minimum distribution cost with different time window width multiples

由图10可知，客户可接受的服务时间窗宽度会对配送成本产生影响，并且不同规模算例的变化趋势相同，即客户可接受的服务时间窗宽度越大，所需配送总成本越低.由表9可知，当客户时间窗调整比例由0.8倍变为2.0倍时，在相同客户满意度下，车辆固定成本保持不变，运输成本和服务成本以低于0.5%的微弱幅度分别增加和降低，而时间窗成本显著降低，时间窗成本是配送总成本降低的主要因素.在实践中，为了降低配送成本，物流企业管理者可以通过与客户协商谈判、提供奖励等方式，使得客户接受更宽的服务时间窗.

表9 不同时间窗宽度倍数下的配送方案Tab.9 Distribution schemes with different time window width multiples

5 结语

本研究提供了末端配送服务模式与路径联合优化方法.考虑到车辆容量限制、客户对不同配送服务模式的接受度、收货时间窗等约束，以配送成本和客户满意度为目标，建立了一个混合整数规划模型，改进NSGA-Ⅱ算法对模型进行求解.算例分析证实了模型的准确性以及所设计算法的优越性能.算例参数敏感度分析发现：

1）相较于单一末端配送服务模式，末端配送服务模式与路径联合优化能够同时对配送成本和客户满意度进行改善.

2）管理者可以通过适当增加自提点和自提柜数量，争取与客户达成更宽松的收货时间窗的途径，实现降低配送成本的目标.