高铁快运城市配送优化模型及算法研究

杨博文，金哲宇

(兰州交通大学 交通运输学院，甘肃 兰州 730070)

0 引言

自2014 年起，铁路运营企业推出一系列高铁快运产品，积极打造高速铁路物流品牌，目前的合作体系中多为与第三方物流进行合作，物流配送体系还不完善，从“门到站”和“站到门”有一部分要依靠第三方物流配送，配送质量有待提升，“最后一公里”的问题尚未有效解决[1-2]，亟需对高铁快运城市配送问题展开研究，以更好减少配送成本，提高快件配送的时效性和客户满意度，提升高铁快运形象。

高铁快运城市配送问题属于车辆路径规划问题，对于城市配送的车辆路径问题，国内外学者展开了广泛研究。杨黎朝[3]基于国家政策和京东平台发展现状，分析了京东自营配送物流的必要性，建立了带软时间窗的京东生鲜食品电动车物流路径优化模型，提出了最佳的充电策略。袁涛等[4]在考虑解决应急物资物流配送问题时，构建了多式联运多级应急物流网络，考虑了灾后道路损毁对通行时间和可靠度的影响，以救援总成本最小为目标，生成路径方案。李伟等[5]针对高铁快运末端物流城市配送成本过高的问题，考虑时间惩罚成本，建立带软时间窗的城市末端物流配送路径优化模型。蒋丛萃[6]在寻找高铁快运配送最短路上，设计一种针对电子商务物流的配送路径优化算法，建立物流配送路径优化多目标函数，寻找到最优的目标路径。常乐等[7]针对电动汽车配送问题，以客户满意度最大和运输距离最短等为目标，建立电动汽车多目标配送模型，设计一种改进蚁群算法解决模型。Carina 等[8]为了最大程度地减少总服务时间和确保服务同步，提出城市物流配送服务运营规划的数学模型。吴耕锐等[9]以运输安全和运输距离为目标，建立双目标路径优化模型，设计自适应随机多目标路径选择算法。

可见，针对高铁快运城市配送的路径优化问题研究需要对高铁快运的服务特点和市场定位充分考虑，故基于高铁快运业务小批量、多频次、高品质的特点和高铁快运业务的发展方向，提出服务质量目标和成本目标，构建高铁快运城市配送多目标优化模型，决策车辆配送路径。

1 高铁快运城市配送优化模型构建

1.1 问题描述

高铁快运物流配送是高铁快递在营业部完成到达作业后与客户进行快递交付的一个关键环节，主要包括确定客户配送区域、配送顺序、配载车辆、配送车辆路径、进行车辆配送和问题件处理等环节。高铁快运城市配送的目标客户为对时间要求敏感的客户，高铁快运城市配送货物的特点为小批量、多频次和高品质，配送客户的特点为分布分散且服务需求多元化，配送的关键决策是提供优质快运配送服务，提升服务质量水平。目前高铁快运物流配送主要存在以下问题：①配送成本较高，常因司机的主观意识强、习惯走某条道路或其他原因使配送路径变长，造成较高的配送成本；②配送中心单一，由于业务量不足，高铁快运快递市场有待发掘，目前在办理高铁快运业务的城市大多为配送中心—客户的二级城市配送结构；③服务质量较低，高铁快运城市配送的目标客户为对时间要求敏感的客户，不同客户对配送时间的要求不同，过早或过晚的配送服务使配送服务质量变低。在生成配送路径方案时，要考虑到配送中心和客户双方的利益，既要保证高铁快递准时送达到客户手中，又要保证配送中心的配送收益，故在进行模型构建时主要本着“高时效性”和“物流成本低”2个原则。

高铁快运城市配送优化问题可被描述为：在高铁快运城市配送网络中有1 个配送中心(高铁快运营业部)、多个客户点和多个配送车辆，配送车辆从配送中心出发，有且只经过1 次各客户点且每个客户均被服务1 次，最后返回配送中心。配送车辆送达客户的时间必须早于客户要求的最晚时间，故配送车辆必须在客户规定的服务时间或早于服务时间到达客户点进行配送服务。模型构建基于以下假设：①城市配送道路的各个时间段的拥挤度相同，各配送车辆的平均速度一致；②每个高铁快件的最晚配送时间不超过客户提出的服务提供时间；③配送车辆返回的最晚时间不能超过配送中心规定的下班时间。

1.2 模型变量参数设置

设高铁快运城市配送网络为G=(N，A)，其中高铁快运配送中心0 和所有客户点i 的集合N=

{0，1，2，...，n}。 各 节 点 间 有 向 弧 的 集 合 为A={＜ni，nj＞|ni，nj∈N，i ≠ }j ，其中＜ni，nj＞表示客户点ni到客户点nj的几何路径。模型相关符号及含义如表1所示。

表1 模型相关符号及含义Tab.1 Related symbols in the model and their meaning

1.3 模型构建

高铁快运主要提供2 大类服务：时效快递和经济快递。其中，时效快递主要有4 种产品：当日达、次晨达、次日达与隔日达。经济快递分为2 种产品：普通快递和同城快递。其中当日达、次晨达、次日达、隔日达分别是指在客户要求的城市之间为客户提供快递服务，并承诺在当日22：00、次日11：00、次日18：00、第三日18：00 前送达收件人。

高铁快运客户办理业务的不同会影响到在服务质量目标中客户的重要性，故提出快运服务客户重要度的概念，用于评价高铁快运业务办理客户的重要程度。客户点ni的快运服务客户重要度θi的计算公式为

式中：λ1，λ2，λ3，λ4分别表示办理当日达、次晨达、次日达和隔日达业务的运价首重，kg；zi表示客户ni办理的高铁快运业务类型，z1，z2，z3，z4分别表示客户办理的业务为当日达、次晨达、次日达和隔日达。

客户不满意度与车辆到达客户点的时间关系如图1 所示。关于客户不满意度sij随着时间t 的变化产生2段函数。

图1 客户不满意度与车辆到达客户点的时间关系Fig.1 Relationship between customer dissatisfaction and the time vehicles arrive at customer points

考虑以下2 种情况：①当配送车辆到达客户点nj的时刻aij早于客户规定的时间窗[bi，ei]时，客户将产生不满意度，由于高铁快运办理的业务是定时服务，如与客户所办理的定时服务有所偏差，会引起客户的不满，偏差结果越大，旅客的不满意度越高；②当配送车辆到达客户点nj的时刻aij在客户规定的时间窗[bi，ei]内，客户将不产生不满意度，考虑到客户在规定的时间窗内收到高铁快运快件会对高铁快运业务产生满意感，但s 代表客户不满意度，所以s ≡0。此外配送车辆到达客户点nj的时间aij晚于客户规定的时间窗[bi，ei]将不被考虑在内。sij计算公式为

每个客户点服务的起始时间要早于客户终止服务的时间，可表示为

配送车辆从配送中心出发的时间小于车辆返回配送中心的时间，可表示为

2 算法设计

针对高铁快运城市配送多目标优化模型，采用带精英策略的非支配排序遗传算法(Elitist Non-Dominated Sorting Genetic Algorithm，NSGA-Ⅱ)，对高铁快运城市配送优化模型进行算法设计。NSGA-Ⅱ是基于帕累托(Pareto)最优解优化，与其他算法相比，NSGA-Ⅱ的种群多样性和分布性较优，收敛性更快，求解速度也相对较快，主要体现在快速非支配排序、拥挤度因子和精英策略3大核心思想，使得算法可在解决多目标问题上具有良好的表现性，算法流程图如图2所示。

图2 算法流程图Fig.2 Algorithm flow chart

（1）构造非支配集。NSGA-Ⅱ中通过快速非支配排序构造非支配集，首先，找出该种群中的所有非支配染色体，得到第一个非支配最优层；然后对种群中的其他个体继续按照支配与非支配关系进行分层，对剩下的个体继续上述操作，直到种群中的所有个体都被分层。

（2）拥挤度排列比较。NSGA-Ⅱ中的拥挤度是引入拥挤度nd和拥挤度比较算子，先对种群个体p 进行无距离化处理，随后以拥挤度比较算子对种群个体进行排列，然后用拥挤度公式求出每个种群个体p的拥挤度，最后比较个体间的拥挤度nd并进行升序排列。

式中：M 为目标个数；fm(i+1)表示该个体在对应的Pareto 等级的下一个个体对应的目标函数值；fm(i-1)表示该个体在对应的Pareto 等级的上一个个体对应的目标函数值。

以二维目标为例，种群个体p 在Pareto 域中按等级进行分层，拥挤度是在该目标空间每个个体p 不触碰其他同等级个体所生成的最大矩形的边长之和。

（3）选择优质解。NSGA-Ⅱ中通过精英策略选择优质解，将经过选择的父代的优良种群的个体与经过交叉变异的子代种群进行混合，然后进行选择后形成新的优良种群，这样生成的下一代种群会保留父代种群的优良个体，维持种群的多样性，提高了种群水平。

（4）算法流程。算法首先定义相关变量参数，迭代次数Gen 初始为0，初始化种群Rt生成初代种群。通过快速非支配排序得到非支配集Z，通过拥挤度比较算子对Fi从大到小排列，精英策略将Fi的非支配解放入到种群Ct+1中。对父代种群Ct+1进行选择、交叉和变异操作得到子代种群Dt+1。将子代种群Dt+1和父代种群Ct+1混合成个体数为2N 的种群，并按照锦标赛准则选择个体生成种群Rt。反复迭代直到生成满意的非支配集，当Gen 等于最大迭代次数max(Gen)时，跳出循环、算法结束。

3 算例分析

以某城市一次高铁快运配送为例，该高铁快运配送网络包含21 个节点，包含1 个配送中心和20 个客户点，基本参数取值如表2 所示，将各配送中心和客户点置于坐标系内进行计算。

设置初始种群数量为100，最大迭代次数500，交叉概率为0.9，变异概率为0.1。运行此算法对优化模型求解。在求得的Pareto 解集中，考虑到高铁快运配送中心决策者在不同情况下所侧重方向不同，分别选取服务质量目标最优和配送成本最优的解作为高铁快运城市配送路径方案，其中配送方案Ⅰ是在保证一定成本的基础上使服务质量目标最小的方案；配送方案Ⅱ为保证一定服务质量的基础上使成本最小的方案，2个方案配送车辆数均为4辆，得到2个配送方案情况对比如表3 所示。在服务质量目标方面，配送方案Ⅰ的服务质量目标数值为51.32，较配送方案Ⅱ低37.83；在成本目标方面，配送方案Ⅰ的快件配送成本为1 034.24元，配送方案Ⅰ的成本较方案Ⅱ高63.78元。

2个配送方案车辆路线轨迹图如图3所示，配送车辆从配送中心出发经过多个客户点，最终回到配送中心。配送方案Ⅰ中，配送车辆为了服务质量最大化，牺牲了配送车辆的行驶距离；配送方案Ⅱ中配送车辆是在满足客户规定的配送时间窗的等条件下进行配送，此方案在路径选择上牺牲了客户一定的满意度，将配送总成本降到最低。高铁快运配送中心决策者可考虑不同的目标侧重，结合相关情况选择不同方案：偏向配送成本选择配送方案Ⅰ，偏向服务质量选择配送方案Ⅱ。

图3 2个方案车辆路线轨迹图Fig.3 Vehicle route trajectories of two schemes

表2 基本参数取值Tab.2 List of basic parameters

表3 2个配送方案情况对比Tab.3 Comparison between two distribution schemes

4 结束语

高铁快运依托现有高速铁路网运输资源和运力优势，向客户提供中小快件的中高端运输服务，实现“门到门”之间运输，为铁路货运现代物流模式转变提供了新的方向。目前高铁快运处于发展阶段，日均快件配送量不高，因此在研究时只考虑了单个配送中心、二级配送网络进行配送，当高铁快运业务发展到一定阶段后，还需考虑多个配送中心、三级配送网络进行配送的情况。在进行配送服务时，将客户服务时间窗固定，在实际情况中，某些客户可能因特殊情况导致无法配送，需要问题件处理进行二次配送，可做进一步优化研究。