多车场多车型车辆路径问题的优化研究

朱晨晨

【摘 要】针对多车场多车型车辆路径问题，通过建立虚拟配送中心将多车场路径优化问题转化为单一车场路径优化问题。文章建立了数学模型并利用遗传算法求解模型，同时根据问题性质对遗传算法的编码和解码方式进行改进。基于企业实例的实证研究表明：文章提出的模型对求解多车场多车型车辆路径问题具有一定的优势，能够为企业实际的物流运输调度提供决策支持。

【关键词】多车场;多车型;遗传算法

自1959年车辆路径问题（Vehicle Routing Problem，VRP）被Dantzig和Ramser[1]在文献中首次提出以来，越来越多的研究投入该领域[2]。随着现代物流运输的发展，车辆路径问题及其变体的研究越来越深入，它描述的是在一个连通网络中拥有配送中心和客户两类节点，车辆需要从配送中心出发，在满足客户需求和实现优化目标的前提下，按照一定的行车路线将货物交付到客户手中。

货物从制造工厂或者配送中心通过运输网络流向消费者的这一过程中，运输路线是否合理对成本、效率至关重要。经典VRP的诸多变体包括具有硬、软和模糊的服务时间窗口、客户同时具有取货和交付需求等。多车场多车型车辆路径问题是在经典VRP的基础上添加了“多车场”和“多车型”两类约束，更加符合现实的物流配送情况，同时使得NP-hard的问题求解难度进一步加大。

1 文献综述

多车场多车型车辆路径问题（Multi-Depot Vehicle Ro-uting Problem with a Heterous Fleet，MDHFVRP），是VRP问题的变体之一。由于VRP为NP-hard难题，多车场和多车型的出现又提升了问题的求解难度。多数学者采用启发式算法求解MDHFVRP。例如，Cassidy等人[3]在1972年提出了求解MDHFVRP的迭代算法，他们的研究基于学校送餐的实际案例，该案例拥有600所学校、300个配送中心和100辆异质车队，该算法通过对随机的初始解不断迭代从而改进解的质量，从而实现减少车辆运输时间以尽快配送的优化目标;Wren等人[4]同样提出了迭代算法求解MDHFVRP，初始解依据节约里程法生成，在他们的方案中，算法会根据客户的优先级来满足客户需求;Saihi等人[5]在1997年引入多级启发式方法，在第一阶段利用边界客户建立初步可行解，第二阶段利用局部搜索策略对初始可行解进行改进，该方法被证明在拥有360个客户的大规模问题中具有较好的应用性能;A Willian Ho等人[6]通过两阶段方法求解，算法的第一阶段考虑随机生成的初始解，第二阶段通过最近邻启发式算法和节约里程法找到初始种群，在不同实例上的计算表明了该算法具有良好性能。

针对大规模的MDHFVRP，多数研究采取先聚类再优化的求解思路，此种方法可以缩小问题规模和降低求解难度。例如，Thangiah等人[7]利用遗传算法进行客户分群，将问题转变为旅行商问题，然后通过插入启发式算法求解旅行商问题;Luo.J等人[8]则改进了蛙跳算法，对客户聚类后再进行优化，然后对总体进行调整以生成新的聚类，直到满足设定的收敛标准为止，该方法被证明可以用来求解大规模的多车场车辆路径问题。

大量文献表明，国内外学者对于车辆路径问题及其变体的研究已经较为深入。但多车场多车型车辆路径问题因涉及的变量和约束条件较多，使得NP-hard难题更加复杂。对于大规模多车场多车型车辆路径问题，将其拆分成仓库优化和路径优化两步虽然可以降低求解难度，但是容易导致局部优化。因此，需要针对MDHFVRP进行全局优化，生成整个运输网络的优化解。

2 多车场多车型路径优化问题和数学模型

2.1 问题描述

文章的研究对象可以被描述为多个配送中心拥有多个车型，每种类型的车数量有限，需要对各个需求点提供配送服务，要求通过合理调度车辆，实现总配送成本最少。文章通过建立一个虚拟的配送中心，设定各车场到虚拟配送中心的成本和距离均为0。车辆由虚拟车场出发，经过任一配送中心，服务完客户后再依次回到原配送中心、虚拟车场。

通过设置虚拟配送中心，多车场车辆调度问题可以转变成单车场车辆调度问题，从而降低了问题的求解难度，可从全局进行优化，避免陷入局部最优情况。

针对多车型，有学者在分析影响多车型车辆运输成本的因素后，得出车辆满载时运输成本最低[9]，葛显龙等人[10]的研究中也根据最大车载率原则选择车型。综合学者们的研究，文章采取“最大满载率”原则，即对于一段路径来说，优先选择对应该路径上满足所有客户总需求的满载率最大的可用车型。

2.2 数学模型

考虑不同车型的使用费用差异巨大，对运输总成本的影响程度也不同，因此文章的目标函数选取为车辆运输的固定成本和可变成本之和。

3 遗传算法求解设置

3.1 遗传算法的求解步骤

（1）染色体编码：1到n的n个自然数的随机排列表示客户，基因的数值表示该客户，该基因在染色体中的位置代表该客户被服务的顺序。采取（n+1）到（n+m）的m个整数表示m个车场。0代表虚拟配送中心。

（2）初始种群：初始种群采用随机的方式生成，隨机产生1到n的全排列构成染色体Sk，G=（S1，S2，…，Sk）表示初始种群。

（3）适应度函数：适应度函数取目标函数的倒数。

（4）选择：计算种群中每个个体的适应度，采用轮盘赌方式选择个体。

（5）交叉：设定交叉概率Pc，从上一代种群中随机选择两个个体作为父代，并产生0～1的一个随机数，若随机数小于Pc，则对两个父代进行交叉操作，否则不交叉。

（6）变异：设定变异概率Pm。产生0～1的一个随机数，若该随机数小于Pm，则执行变异操作，否则不变异。

3.2 遗传算法的改进

（1）编码方式的改进。传统的一条染色体表示一个个体的方式虽然比较直观简洁，但是当问题涉及变量较多时，会造成染色体数目过多，在执行交叉、变异等遗传操作时效率低下，占用大量计算空间，甚至会形成不可行解，大大降低了算法的运算效率[11]。文章采用一條染色体表示多个个体的“复合染色体编码”，此种设置可以减少染色体数量，提高算法的执行速度和计算精度。

（2）解码方式的改进。文章通过建立“染色体信息矩阵”实现对解的快速解码，该矩阵包含每条染色体中个体的分割点、该个体对应的子路径满载率、服务车场编号、匹配车型等。

例如，在一个多车场多车型车辆路径问题中，2个车场共拥有2种车型，并有6个客户需求点，则用1～6的自然数表示6个客户，7和8分别表示2个车场，1 000和1 500分别为两种车型的额定装载量。假定某条染色体的客服排列顺序为123456，则对应某个可行解的相关信息会存储在“染色体信息矩阵”中，矩阵的前三行分别表示分割点、服务车场、匹配车型：  3   6 7   81 000 1 500矩阵表达的意义为7号车场为1、2、3号客户提供服务，并由额定装载量为1 000的车型进行运输，8号车场为4、5、6号客户提供服务，并由额定装载量为1 500的车型进行运输。解码后的两条路径分别可以表示成0-7-1-2-3-7-0和0-8-4-5-6-8-0，0为虚拟配送中心。

4 算例分析

H公司位于k市，面向全国客户销售货物A，H公司在k市拥有5个仓库，用于承接客户的订单并组织车辆进行配送。目前的物流配送中存在的问题如下。①车辆满载率低：H公司在进行车辆调配时缺少明确的选择原则，存在较大车型承载较少订单量的情况，导致车辆满载率低。②运输距离长：H公司的发货计划在满足车辆装载量限制的情况下存在相近到货点的订单被不同批次的车辆运输，增加了总运输距离。

基于以上两个问题，H公司现有的配送计划导致了较高的运输总成本。因此，文章的优化思路为在尽量提高车辆满载率的情况下，实现总运输成本的最小化。

本文选择一天的订单数据进行仿真试算，该天没有突发订单，客户的地理位置分布均匀，所以试算结果可以较好地表现模型的性能。在仿真试算前，需对初始数据进行处理，使数据更适用于模型。H公司共有7个配送中心，考虑到地理位置的远近，以及库存数量较少的配送中心需要从其他配送中心调货，因此实际上可视为5个配送中心。模型中需要的数据包括各节点的地理位置、运输车辆的额定装载量及各客户的需求量等。考虑到初始数据中各节点是以实际的地理单位表示，文章利用百度地图将各节点的地理位置表示为经纬度，并利用经纬度距离公式表示两节点的距离;初始数据中客户的需求量通过货物A的件数表示，文章根据货物A的重量和体积，将各车型的额定装载量换算成额定装载件数，并取历史订单中利用率最高的5种车型作为文章的可用车型。

因此，算例信息可描述如下：5个配送中心，拥有数量有限的5种车型，额定装载量分别为2 000、1 750、1 250、1 000、800件，对应的车辆可变成本即每公里运输成本分别为0.1、0.15、0.2、0.25、0.3元，固定成本分别为100、150、200、250、300元。车辆该天共有192个需求点，存在到货地点相同的不同订单。

在经过多次试算后，文章设置遗传算法的参数如下：种群规模n=60，迭代次数C=200，交叉概率pc=0.8，变异概率pm=0.05。算法通过在Win10系统的计算机上运行Matlab 2018进行，对算例数据运行5次，结果见表1。

取5次运算中的最低成本，为77 085元，共调用103辆车，车队总运力为139 250件，运力利用率为94.51%。对应的优化运输路线图如图1所示。

现有方案共调用共调用119辆车合计运力为175 650件，实际利用运力为131 605件，利用率74.92%;总路程为274 934 km，总运输成本为86 405元（见表2）。

通过将现有运输方案和优化运输方案进行对比，文章主要实现的优化点有4个：①总运输成本：现有运输方案的总成本为86 594元，优化后为77 085元（见表3），降低了10.15%。现有的运输方案中虽调用了大量的车辆，但是车辆利用率不高，每辆车调用一次就会产生一个固定成本下，使得总运输成本上升。②满载率：优化方案中车辆的满载率作为多车型选择的优先原则大大提高了优化后车辆的满载率，减少了车辆空载率过高的现象。③总运输距离：现有运输方案的总运输距离为274 934 km，优化后的总运输距离为273 915 km。现有运输方案中，少量多批次的原则造成大量车辆的迂回运输，经优化后，车辆满载率的提高使得在满足额定装载量限制的条件下，一条路径可以有更多的客户被服务，从而减少了车辆的迂回运输，减少总运输距离。总距离的减少程度不显著的主要原因在于本文的优化目标是总运输成本最少，除了运输距离外，车辆的固定成本是影响调度方案的重要因素。④调用车辆数：现有运输方案总共调用了119辆，优化后的运输方案共调用了103辆，降低了13.4%。

5 结论与展望

针对多车场多车型车辆路径问题，本文建立数学模型、并设计遗传算法进行求解，并对企业实际的物流运输问题，实证研究，算例结果表明文章建立的数学模型和遗传算法可以得到比现有运输方案更优的解，能够为企业节省一定的运输成本，产生更多的经济效益。

但现实的物流配送中，时间窗约束是较为关键的问题，车辆能够在硬、软时间窗条件下完成配送对于客户满意度、企业信誉等具有重要影响力，因此在现有问题上加上时间窗因素，将是下一步的研究方向。

参 考 文 献

[1]Dantzig G B，Ramser J H.The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.

[2]何彥东.网购物流终端配送问题研究[D].重庆：重庆大学，2018.

[3]Bettinelli A，Ceselli A，Righini G.A branch-and-

cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows[J].Transportation Research Part C Emerging Technologies，2011，19（5）：723-740.

[4]Wren A，Holliday A.Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points[J].Journal of the Operational Research Society，1972，23（3）：333-344.

[5]Salhi S，Sari M.A multi-level composite heuristic for the multi-depot vehicle fleet mix problem[J].European Journal of Operational Research，1997，103（1）：95-112.

[6]A W H ，B G T S H，B P J ，et al.A hybrid genetic algorithm for the multi-depot vehicle routing problem[J].Engineering Applications of Artificial In-telligence，2008，21（4）：548-557.

[7]Thangiah S R，Salhi S.Genetic clustering：An ada-ptive heuristic for the multidepot vehicle routing problem[J].Applied Artificial Intelligence，2001，15（4）：361-383.

[8]Luo J，Chen M R.Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW[J].Computers & Industrial Engineering，2014，72：84-97.

[9]Moshe，Dror，Michael，et al.Inventory/routing： Reduction from an annual to a short-period problem[J].Naval Research Logistics，1987，34（6）：891-905.

[10]葛显龙，王旭，邓蕾. 基于联合配送的开放式动态车辆路径问题及算法研究[J]. 管理工程学报，2013，27（3）：60-68.

[11]陈呈频，韩胜军，鲁建厦，等.多车场与多车型车辆路径问题的多染色体遗传算法[J].中国机械工程，2018，29（2）：218-223.