不同车型车辆路径问题模型及混合算法

王琦;席丹;钱年发;毛韵霞

【摘 要】Based on the traditional vehicle routing problem (VRP), the swap-body vehicle routing problem (SB-VRP) which contains transfer stations and different vehicle types is solved. With the purpose of a lower cost, tabu search algorithm is employed to optimize the initial solution figured out by the sweep method. Results show that with the proposed method, a better solution with lower cost can be obtained;after adding different vehicle types, the model of SB-VRP is more efficient than traditional VRP.%在传统车辆路径问题(VRP)的基础上,求解带有中转站的不同车型车辆路径优化问题(SB-VRP).以行驶成本低为目标,在扫描法形成初始解的基础上,采用禁忌算法进行优化搜索,通过实证分析对算法进行验证.结果表明:本文算法可以得到成本比初始解更优的解;增加不同车型之后的SB-VRP模型比传统VRP模型效率更高. 【期刊名称】《安徽工业大学学报（自然科学版）》 【年(卷),期】2017(034)002 【总页数】8页(P200-207)

【关键词】车辆路径问题;扫描法;禁忌搜索算法 【作 者】王琦;席丹;钱年发;毛韵霞

【作者单位】北京邮电大学经济管理学院,北京100876;北京邮电大学经济管理学院,北京100876;安徽马钢汽车运输有限公司,安徽马鞍山243000;北京邮电大学经济管理学院,北京100876

【正文语种】中 文 【中图分类】TP312

现代物流业作为企业重要利润源之一，越来越引起人们的重视。配送是现代物流的一个重要环节，很多学者对其中车辆路径问题[1](Vehicle Routing Problem,VRP)展开研究。传统意义上的车辆路径问题[2]指仓库位置、客户需求和位置已知，并且满足一定约束条件的情况下，寻求一条路径，对每个客户进行访问，使得运输成本达到最小。约束条件包括：车辆载重的约束、访问次数约束、出发点及终点约束等。VRP问题作为近代组合优化领域典型难题之一，被张国英、李向阳[3-4]等认为是NP-hard(Non-deterministic Polynomial Hard)问题。

Crevier等[5]通过增加车厂的数量，讨论由VRP模型衍生而来的多车厂模型。张毅等[6]在增加时间窗的约束(VRPTW)情况下，研究车辆路径的多目标优化问题。宾松等[7]进一步修正了时间窗约束，即增加软时间窗(VRPSTW)，不严格要求车辆必须到达的时间，但需考虑车辆在最早到达时间之前到达的等待成本和最迟到达时间之后的罚金成本。钱小凤等[8]研究忽略车辆的能力约束的多货郎担问题(m-TSP)，并以m-TSP模型为基础研究邮政网络的社区物流问题。张媛媛等[9]考虑车辆配送的周期性问题，结合单周期静态车辆配送问题(即VRP问题)，分析多周期车队组合及配送，建立起物流企业动态车队组合优化模型。彭碧涛等[10]研究三维装载车的车辆路径问题(3L-CVRP)，其中每一个物品除了质量属性外，还包括长度、高度和宽度的概念。Salhi等[11]考虑中央配送中心、运输中转站以及其他选址设施进行车辆路径优化，提出最近多级选址-路径问题(NE-LRP)。Jacobsen等[12]首先提出带有带有中转站的两级选址路径问题(2E-LRP)，规划了印刷厂、中转站、顾客之间的巡回路径。求解方法上，Kuo[13]用模拟退火法解决时间依赖的车辆路径问题；葛显龙等[14]用遗传算法解决多车型车辆路径问题；丁秋雷等[15]用蚁群

算法解决带有时间窗的车辆路径问题；王付宇等[16]用混沌萤火虫算法优化城市突发事件下应急物资配送；张涛等[17]用禁忌搜索算法解决不确定车辆的路径优化问题。其中禁忌算法是一种全局优化算法，是指在一个初始解的基础上，通过引入灵活的储存结构和相应的禁忌准则来避免重复的搜索。但是禁忌搜索比较依赖于初始解的优良程度。上述有关路径问题的研究中，忽略了车辆容积与中转站车型转换的影响。

SB-VRP(Swap-body Vehicle Routing Problem)模型属于传统车辆路径问题的衍生问题，也属于NP-hard问题，该模型研究带有中转站，使用train和truck两种不同容积不同、单位成本不同的车型进行配送，两种类型车辆可在中转站拆卸安装车厢相互转化。本文采用混合算法，在扫描法形成相对优异的初始解基础上，用禁忌搜索算法(Tabu search algorithm，TS)进行优化，利用1-1交换和1-0交换两步操作，将使用相同车型的客户访问次序在子路径间交换，解决不同车型的SB-VRP问题。

考虑到运输中客户车厂大小、车辆体积等因素的影响，对传统的VRP问题增加限制条件，研究带有中转站且含不同车型的车辆路径问题(SB-VRP)。文中增加的约束条件包括：1)两种车辆类型：truck(只带有一节车厢)、train(带有两节车厢，拆卸一节后则变为truck；2)两种客户类型：I型客户仅可以被truck访问；II型客户均可以被以上两种车型访问；3)增加中转站，车辆可在此装卸整节车厢。train可在中转站将一节车厢卸下后，变为truck车型，再继续访问I型客户。每个车厢容量相同。其他条件和目标与VRP模型相同。

truck带有一节车厢，共m辆，train带有两节车厢，共l辆，每节车厢的最大容量为Q。所有车辆均从仓库出发，最后回到仓库，不允许交换车厢，仅可在中转站整箱装卸变更车型。客户Ci需求量qi＞0，且每个客户Ci仅被访问一次；共有n个客户。为保证可行性，假设每个客户需求量不超过2×Q,中点站专为train准

备。变量定义参见表1。

根据以上假设和定义，建立SB-VRP模型如下：

式(1)为目标函数，要求达到总成本最小；式(2)表示每辆车从仓库出发，最终回到仓库；式(3)，(4)表示每个客户有且仅有一辆车为其配送；式(5)表示第1,2,…,m辆车为truck，为I型客户配送；式(6)表示第m+1,m+2,…,m+l辆车为train，II型客户配送；式(5)，(6)表示实际载客量小于车辆额定载重；式(7)表示每个客户仅仅用一辆车服务，且最终离开。

传统的VRP模型中，车辆从仓库出发，访问部分客户后，直接回到仓库，如图1所示。SB-VRP模型加入了中转站，且在中转站卸掉train的一节车厢可以使train变为truck，在中转站为truck安装一节车厢可以使truck变为train，如图2所示。

首先对仓库、中转站、I型客户和II型客户进行编码，再在改进扫描法形成初始解基础上，使用禁忌算法进一步对初始解进行优化。混合算法过程分为两个阶段： 1)改进的扫描法形成初始解

为了最初形成一个比较优的解，提高后续优化速度，在初期使用改进的扇形扫描法，所有子路径的需求总和满足车辆载重的限制条件下，形成车辆访问所有用户的完整路径。 2)禁忌算法优化

在初始解的基础上，经过1-1交换和1-0交换，以成本目标函数作为评价函数，以所有子路径需求总和满足车辆载重为条件，找到更优的解。

中转站编码为S1,S2,S3,…；客户编码为C1,C2,C3,…;唯一的仓库编码为D。如编码(D,C23,C11,C4,C22,S1,C21,C8，C2，S1，C5，C19，D)表示一条子路径，代表车辆从配送中心 D 出发，分别经过客户 C23,C11,C4,C22,至中转站S1，卸下一节车厢，然后经过客户C21,C8,C2,返回中转站S1装上车厢，再经过客户C5,C19，

最终回到配送中心。一条全路径包含所有客户，不同车辆用D隔开，即(D,C11C12,…,C1x,D,C21,C22,C2Y,D,…,D,CK1,CK2,…,CKZ,D)。

传统求解方法中采用随机生成法生成初始解，即随机将一定数量的客户加入一条子路，直至客户需求之和满足车辆载重的最后一个客户；也有采用扫描法，即沿着仓库作一条射线，沿某一方向扫描，直至客户满足约束构成一个客户分群，重复操作，将所有客户加入路径。通常扫描法得到解的成本低于随机生成法。

由于SB-VRP模型中含有两种车型、两种类型用户，不同车型通过在中转站拆卸车厢相互转化的特殊性，为了形成一个比较优的初始解，本文使用改进的扫描法，具体流程如下：

STEP1过配送中心与某一客户生成一条射线，并逆时针转动，扫描的区域形成一个扇形；

STEP2将扇形中所包含客户的需求量按角度依次相加，直至再加一个客户的客户需求量之和超过2×Q，扫描过程可能出现以下3种情况：

1)若扇形区域内没有中转站，且里面客户全部为II型客户，由train依次访问； 2)若扇形区域内没有中转站，且里面客户既包含I型客户也包含II型客户，或者全部是I型客户，则将这部分重新扫描，直至再增加一个客户的客户需求量之和超过Q，这部分客户用truck访问，剩余的客户重新进入下次扫描；

3)若扇形区域中包含中转站，则要求所有客户需求量不超过2×Q，同时所有I型客户的总需求之和不超过Q。随机找到一个中转站，将该中转站与所有I型客户点按TSP(Traveling Saleman Problem)模型求得一条最优路线；再将该中转站、所有II型客户、仓库按TSP模型求得一条最优路线。两条路线合并起来，形成一条完整子路径，即仓库——部分II型客户——中转站——所有I型客户——中转站——其余的II型客户——仓库。这条路径解释为：使用train车型出发，途经部分II型客户后，在中转站卸掉一节车厢转化为truck访问所有I型客户，回到中转

站装上之前卸掉的车厢访问其余的II型客户，最终回到仓库。 3种情况及处理方法见表2。

STEP3射线沿着STEP2中的最后的射线继续逆时针扫描，该扇形以外的第一个点开始形成下一个扇形路径，重复上述步骤，直至所有的点全部形成子路，从而形成一条完整路径。 1)算法设计

(1)解的评价。在解的邻域搜索中，需要保证解的可行性，即满足每个子路径的客户需求之和不会超过车载重，且符合车的型号。以目标函数(成本)作为评价函数，目标值越小，评价越好，解越优。

(2)邻域搜索。按照2.2.2节所述方法计算，已经达到每条子路线内的最优解，所以本节继续对路线进行子路线间的邻域交换搜索。1-1交换法：从两条子路中分别取一点，进行交换。1-0交换法：从一条子路中取一点，随机插入到另一条子路中。 考虑到SB-VRP模型中存在不同客户类型，在邻域搜索过程中，1-1交换法，选取同类型的s客户进行交换；1-0交换，若选取要插入别的子路径的客户是I型，则插入的路径也要求为其他部分I型客户所组成的路径；若选取要插入别的子路径的客户是II型，则插入的路径也要求为其他部分II型客户所组成的路径。 (3)禁忌表与禁忌对象。为了防止产生循环解，禁忌算法定义了禁忌表，用于记录最近几次迭代中达到局部最优解或求解过程，将当前计算的最优解作为禁忌对象插入禁忌表中，本文对两种邻域交换分别添加禁忌。1-1交换中，对最优解的交换点禁忌，在一定数目的迭代搜索中不允许这两个客户再进行交换；1-0交换中，对最优解的该点的插入禁忌，在一定数目的迭代搜索中不允许该客户从该子路径中移除。 禁忌表的长度是重要因素，通常由实际问题决定，禁忌长度太长可能会导致太多禁忌，降低了搜索的作用，太短可能会导致循环搜索。 (4)终止准则。采用最大迭代指定步数终止准则。

2)算法步骤

(1)建立1-1交换和1-0交换禁忌表T1，T2，初始化T1=，T2=；

(2)运用扫描法产生初始解x0，当前最优目标值，进化代数g=1，设定最大进化代数gmax；

(3)如果g＞gmax，转至步骤(6)；若g≤gmax，通过1-1交换产生x0的邻域N(x0)，从中选择满足禁忌要求的候选集U(x0)；

(4)从候选集U(x0)选择一个适配值最优的解x1，循环上一操作并更新禁忌表，以及局部最优解；

(5)g=g+1，返回步骤(2)；

(6)输出当前最优解x1，则当前最优目标值，进化g'=1，设定最大进化代数； (7)如果，转至步骤(10)；若，则通过1-0交换产生x1的邻域N(x1)，从中选择满足禁忌要求的候选集U(x1)；

(8)从候选集U(x1)选择一个适配值最优的解x1，循环上一操作并更新禁忌表，以及局部最优解；

(9)g'=g'+1，返回步骤(7)； (10)输出结果。

1)2种车辆类型。truck(一个车厢，容量500 m³；成本0.7元/km)；train(两个车厢，每个车辆容量500 m³，共1000 m³，成本0.9元/km；若拆卸掉一个箱子，则变成truck，成本变为0.7元/km)

2)站点的类型。配送中心：1个(D)，所有点需要从仓库出发最后回到仓库；客户：57个，其中I型客户15个 (C1～C15)，被truck访问；II型客户42个 (C16～C57)，两种车型均可访问；中转站：20个 (S1～S20)，train可在中转站装卸一节完整车厢转化为truck。

本例中各类型点均为实际的城市。其中：X坐标指城市所在经度；Y坐标为所在纬

度。其中配送中心和中转站的坐标如表3，客户坐标和需求如表4。

首先根据改进扫描算法求解出较优的初始解，再由禁忌算法对目标进行优化以求最优解，参数设置为禁忌长度为5，邻域中选取解的个数为100，迭代次数gmax为100。在禁忌搜索1-0交换过程中，可能因为客户的交换，出现无访问的中转站，此时将中转站在路径中删除以节约成本。

最终求得的路径见图3～5。其中的点包含了所有客户、中转站、仓库，每一条回路为一辆车所走的子路径，途中一些没有被访问的点全部为中转站。其中图3为采用VRP模型计算，且仅用truck访问，得到的初始解以及经过禁忌算法得到的最终解；图4采用VRP模型仅用train访问得到的初始解以及经过禁忌算法得到的最终解；图5按照增加了中转站和使用两种车型配送的SB-VRP模型，得到的初始解和禁忌算法优化之后的最终解。

仿真结果：若根据VRP模型计算，用truck访问得到的最终成本是6 692 473元，用train访问得到的最终成本是4 433 597元；若根据SB-VRP模型计算，得到的最终成本是4 357 492元。对于同一个实例，增加了中转站、两种车型的车辆路径问题与传统的车辆路径问题方案相比较，成本明显减少。其主要原因在于：1)传统的VRP，使用train容量是truck的2倍，然而train配送的成本小于使用2个truck。因此按照传统VRP模型计算，truck运输成本大于train的成本。SB-VRP模型用两种不同车型运输配送，优先考虑使用train配送，其次考虑使用truck，因此，SB-VRP模型比单纯用truck配送VRP模型成本更小；2)SB-VRP模型与单纯使用train配送的VRP模型相比，一部分车到达中转站之后卸掉一节车厢，变为truck再进行配送，单位成本0.7小于用train的单位成本0.9。因此，SB-VRP模型比单纯用train配送的VRP模型成本更低。从成本角度分析，SB-VRP比传统的VRP模型更有现实意义。

1)实际问题中，由于客户停车场大小不同，中心城市的配送要求、成本等多重因素，

货车中甩挂车的应用越来越广泛，因此考虑车辆、客户类型的SB-VRP模型更具有现实意义。

2)本文提出针对SB-VRP模型的扫描法与禁忌算法相结合的算法，在扫描法形成较优初始解的基础上进行禁忌邻域搜索优化，找到更优解。实例表明，该算法在数据较大的情况下，具有搜索范围广和能够克服陷入局部最优的优点，且SB-VRP模型可以求解出比传统的VRP成本更小的路径，更优的成本，更高的效率。

【相关文献】

[1]DANTZIG G B,RAMSER J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[2]陈君兰，叶春明.物流配送车辆调度问题算法综述[J].物流科技，2012(3):8-12. [3]张国英，林贤茂.遗传算法在VRP问题中的应用[J].物流科技，2009,32(5):41-43. [4]李向阳.遗传算法求解VRP[J].计算机工程与设计，2004,25(2):271-276.

[5]CREVIER B,CORDEAU J F,LAPORTE G.The multi-depot vehicle routing problem with inter-depot routes[J].European Journal of Operational Research,2007,176(2):756-773. [6]张毅，申彦杰.时间窗约束下的车辆路径问题多目标优化算法[J].数学的实践与认识，2009(4):124-131.

[7]宾松，符卓.求解带软时间窗的车辆路径问题的改进遗传算法[J].系统工程，2003(11):12-17. [8]钱小凤，林国龙.基于邮政网络的社区物流多中心m-TSP问题[J].大连交通大学学报，2012(8):43-48.

[9]张媛媛，李建斌.动态车队组合优化模型及精确算法[J].系统工程理论与实践，2007(2):83-91. [10]彭碧涛，周永务.基于禁忌搜索的三维装载车辆路径问题研究[J].计算机工程，2011(6):190-194. [11]SALHI S,RAND G K.The effect of ignoring routes when locating depots[J].European Journal of Operational Research,1989,39(2):150-156.

[12]JACOBSEN S K,MADSEN O B G.A comparative study of heuristics for a two-level routing-location problem[J].European Journal of Operational Research,1980,5(6):378-387. [13]KUOY.Usingsimulatedannealingtominimizefuelconsumptionforthetime-dependentvehicle routingproblem[J].Computers&Industrial Engineering,2010,59(4):157-165.

[14]葛显龙，许茂增，王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学，2010,32(8):1801-1807.

[15]丁秋雷，胡祥培，李永先.求解有时间窗的车辆路径问题的混合蚁群算法[J].系统工程理论与实

践，2007,27(10):98-104.

[16]王付宇，叶春明，王涛.城市突发事件下的应急物资配送路径寻优[J].安徽工业大学学报(自科版)，2016,33(2):177-184.

[17]张涛，张玥杰，王梦光.不确定车辆数的车辆路径问题模型和混合算法[J].系统工程理论方法应用，2002(6):121-130.