DOI: 10.11817/j.issn.1672-7207.2015.05.049

多车型集配货一体化车辆路径问题研究

陈妍¹，单汨源¹，王秋凤²

(1. 湖南大学 工商管理学院，湖南 长沙，410082；

2. 中南大学 图书馆，湖南 长沙，410083)

摘要：针对客户存在收货和发货双重需求的物流配送问题，讨论具有多种车型的集配货一体化车辆路径问题。在综合考虑各车型的固定成本和可变配送成本的前提下，以总成本最小为目标，以尽可能提高车辆满载率、减少出行次数为思路，构建多车型集配货一体化车辆路径优化模型。基于最小插入费用法设计初始可行解生成算法，通过引入基于概率的多算子邻域操作、最优解记忆装置、多准则终止原则对模拟退火算法进行改进，给出求解思路。设计算例并对多车型单/双向集配货模型的求解结果进行比较，以验证模型的实用性和算法的有效性。研究结果表明：使用改进后的模拟退火算法对构建的多车型集配货一体化车辆路径问题模型求解更直接简便，对多车型集配货一体化车辆路径优化后能有效降低配送成本。

关键词：车辆路径问题；多车型；集配货一体化；模拟退火算法

中图分类号：U492.2；TP301.6           文献标志码：A         文章编号：1672-7207(2015)05-1938-08

Research on heterogeneous fixed fleet vehicle routing problem with pick-up and delivering

CHEN Yan¹, SHAN Miyuan¹, WANG Qiufeng²

(1. School of Business Administration, Hunan University, Changsha 410082, China;

2. Library of Central South University, Changsha 410083, China)

Abstract: Considering that heterogeneous fixed fleet vehicle routing problem with pickups and deliveries (HFFVRPPD) in logistics distribution is a widespread NP problem, which is more complex than single/multi vehicle with one way routing problem, HFFVRPPD optimization model was established to improve the load rate of vehicle, and reduce travel times. The algorithm of producing initial feasible solutions of the model was constructed, the improved simulated annealing algorithm was designed, which includes the operation of multi operators neighborhood based on the probability, embedding of memory devices, and the termination of many standard ways. The multi vehicle routing with one way problem and HFFVRPPD were compared to verify the effectiveness of the model and algorithm. The results show that the improved simulated annealing algorithm solving the HFFVRPPD is more convenient, and the HFFVRPPD optimization can effectively reduce the distribution costs.

Key words: vehicle routing problem; heterogeneous fixed fleet vehicle; pickups and deliveries; simulated annealing algorithm

车辆路径问题(vehicle routing problem, VRP)是由Dantzig等^[1]提出。国内外对VRP研究较多，Solomn等^[2-9]对VRP的研究主要集中在求解算法的改进、约束条件的变换以及客户信息的不确定性等讨论上。随着现代物流的不断发展，一方面，越来越多的客户同时拥有送货与收货需求；另一方面，随着客户量的增大，物流企业的配送和收货业务都不断增大，这2项业务的融合和有效完成成为降低物流成本的重要问题，这就形成了集配货一体化车辆路径问题(VRP with pick-up and delivering, VRPPD)，即需同时考虑配送和回收的车辆路径问题。目前，人们对集配货一体化路径问题和多车型路径问题均进行了相关研究。对VRPPD问题研究均假设顾客点进行集配货服务的车辆是同质的(homogeneous)，即车辆具有相同的装载能力、相同的固定费用、相同的最大行驶距离约束等，并且通常假设车辆数无限^[10-12]。而对多车型车辆路径问题(heterogeneous)，主要研究多车场、动态需求、开放式等情况下的优化方法^[13-15]。事实上，多车型集配货一体化是物流配送中更普遍的问题。在实际配送管理中，物流企业所拥有的车队(fleet)一般由一组异型(heterogeneous)的车辆组成，这些车辆具有不同装载能力、不同的单位旅行费用，使用车辆具有不同的固定成本，由于受资金约束，物流企业拥有的各种类型车辆数目也是有限的，同时，为了降低人力成本、车辆固定成本、车辆行驶成本、时间成本，物流企业更趋向于集配货问题同时完成。本文作者研究车辆路径问题即具有固定车辆数的多车型集配货一体化车辆路径问题(heterogeneous fixed fleet vehicle routing problem with pickups and deliveries, HFFVRPPD)。首先构建多车型集配货一体化车辆路径问题的数学模型，其次给出模型求解算法，最后通过算例验证该模型和算法的有效性。

1  问题描述与模型

1.1  问题描述

从图论的角度，多车型集配货一体化车辆路径问题(HFFVRPPD)可定义如下：设为有向图，V={0, 1, 2, …, I}表示节点集，，，表示边集；节点0表示车场点，一组车辆从车场点出发对顾客点进行配送服务；表示待服务的顾客点集合，顾客点i的需求即配货量为d_i，回收即集货量为p_i；每条边(i, j)赋有旅行距离D_ij；车场点有1队车辆，表示车辆类型集，，表示具体某种类型的车辆，k类型车辆具有装载能力Q_k，k类型车辆具有最大行驶距离限制L_k；使用1辆k类型车辆的固定费用为f_k；在节点对(i, j)间k类型车辆的单位可变旅行费用为v_k；不同类型的车辆数固定且为n_k。HFFVRPPD的优化目标是：确定车辆路线集对I个顾客点进行集货和配货服务，使得总的运输费用最小。运输费用包括使用车辆的固定费用和车辆的旅行费用。这些车辆路线满足以下要求：1) 车辆路线开始于车场点，并结束于车场点；2) 每个顾客点仅由1辆车服务，且其集配货量需求必须得到满足；3) 在整个集配货过程中，所有车辆均不能超过其装载能力；4) 每条车辆路线的行驶距离不能大于其最大允许行驶距离。

1.2  模型假设

为了方便建立数学模型描述HFFVRPPD问题，本文进行如下假设：

1) 只有1个物流中心；

2) 物流中心与需求点的坐标位置及集货量和配货量均已知；

3) 各种车型的车辆数已知，且各车型的固定费用、旅行费用、车容量均已知；

4) 不考虑配送时间限制；

5) 每辆车服务1条回路，由场站出发且最终回到场站；

6) 每辆车在行驶中的车载质量不超过该车型的容量限制；

7) 每辆车每次的配送距离不超过该车型允许的最大行驶距离；

8) 每个需求点能且只能被服务1次，即服务1次并满足需求点的集配货要求；

9) 货物在运输途中不会变质损坏；不考虑司机的工作时间；不考虑道路的通行情况；不考虑运输时的规章制度等。

1.3  模型的建立

设为车辆类型集，共K种；m_k为不同类型的车辆数，总的车辆数为；：k为类型车辆的车辆集；Q_k为车容量，即配送车辆最大载质量；f_k为使用1辆k类型车的出行起步价；v_k为k类型车辆的单位距离运输价格；L_k为k类型车辆具有最大行驶距离限制；kl为k类型车辆中的第l辆；{1, 2, …, I}为顾客需求点集合，共有I个顾客需求点；，表示所有需求点及物流中心的集合；节点O代表物流中心；为待服务的顾客点集合；D_ij为顾客i和顾客j之间的距离；d_i为第i(0≤i≤I)位顾客需要的配货量；p_i为第i(0≤i≤I)位顾客需要的集货量；为k类型车中的第l辆离开顾客点i时的货车载质量；n_kl为k类型车辆第l辆服务的顾客数；n_klj为k类型车辆中第l辆服务的第j个顾客，如n₄₂₃表示4型号车辆中的第2辆车服务的第3个顾客；

HFFVRPPD的数学模型可表示为

        (1)

s.t.                                                                                                                         

，      (2)

，  (3)

，       (4)

，       (5)

，

           (6)

，      (7)

其中：式(1)为目标函数式，表示使总配送成本最小(总配送成本包括所有出行的各车型固定成本和旅行成本)；式(2)表示每个顾客都必须被某种车型的车服务1次，且仅被服务1次；式(3)为车流量守恒式；式(4)用于限制每辆货车所有配货量不得超过车容量；式(5)用于限制每辆货车所有集货量不得超过车容量；式(6)表示车辆在行驶过程中，任一顾客点的载质量都不能超过车容量；式(7)表示每条配送路径的长度不超过车辆1次配送的最大行驶距离。

2  算法设计

2.1  模拟退火算法

HFFVRPPD问题是一个NP难题，即使是对HFFVRP问题和VRPPD问题求解，规模稍大时精确算法几乎不可行^[14]，因此，多采用启发式算法求解^[15]。模拟退火算法的基本原理来自于固体加热至一定的温度后由固体结构瓦解变为液体结构，再对其降温过程加以控制，使得分子在变回固体结构时，能重新排列成所预期的稳定状态。模拟退火算法已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法，因此，研究新车辆路径问题时常用此算法^[16]。本文研究的HFFVRPPD问题用模拟退火算法可以描述为：该问题的1个解i及其目标函数f(i)分别与固体的1个微观状态i及其能量E(i)等价。模拟退火算法步骤为(以目标函数求最小为例)^[17-19]：

步骤1：随机得到1个初始可行解x₀。设定初始温度t₀，令当前解，当前迭代步数，当前温度。

步骤2：若在该温度达到内循环停止条件，则转步骤3；否则，从邻域中随机选择1个邻解，并计算。若，则；否则，若 (表示1个0到1之间的均匀随机数)，则，重复步骤2)。

步骤3：， (温度控制函数)，若满足终止条件，则转步骤4；否则，转步骤2)。

步骤4：输出计算结果，算法停止。

内循环为第2步，它表示在同一温度下进行随机搜索。外循环主要包括步骤3中温度下降、迭代步数增加和停止准则。

2.2  算法流程及改进

对算法进行改进往往可以获得更优的结果。结合多车型集配货一体化车辆路径问题的特点，对传统的模拟退火算法加以改进，构造求解该问题的一种新的模拟退火算法。其改进方法如下。

1) 初始可行解的产生。将解编码为R=(0—1—2—3—4—0—5—6—7—8—0—…—0)的形式(其中0代表配送中心，表示其前1条线路的结束和后1条线路的开始)。对于车辆数既定的多车型集配货一体化问题，寻找初始可行解有一定困难，本文按图1所示流程产生初始解。其中，最小插入费用由下式计算：

           (8)

图1  初始解产生算法

Fig. 1  Generate initial solution algorithm

式中：为需求点i插入到k类型车辆路线中的最小费用；i₁和i₂分别为需求点i的插入位置前1个需求点和后1个需求点的编号；和分别为需求点i到插入位置的前1个需求点和后1个需求点的距离；为原路线上需求点i₁和i₂的距离；为k类型车辆单位距离的运输价格。该初始解产生方法首先确保加入的需求点净增量与车辆现有载货量之和不超过该车的最大容量，保证了解的可行性；其次，最小插入费用考虑了各车型的可变费用、加入位置对整条路线长度的变化，使得该方法得到的初始解在整体费用控制上与随机生成的可行路线相比具有优越性。

2) 邻域操作方法与可行解的判断。传统模拟退火算法采取的邻域操作是2-Opt交换法。这种交换法简单易行，每次只交换2个节点，但其搜索解空间的能力不强。因此，在每一温度下，要保证得到该温度下的1个优解，就需要较长时间来搜索解空间。当温度缓慢降低时，外循环的次数增多，算法的时间呈倍数增加，从而导致整个算法搜索时间过长。

为增强搜索解空间的能力，邻域操作采用4种交换算子基于概率随机进行，分别为SWAP算子、RELOCATE算子、2-Opt算子和2-Opt^*算子，见图2。

图2  4种交换算子运行过程

Fig. 2  Four kinds of exchange operators

采用组合算子的优点是在相同的迭代步数下，虽然得到的解个数没变，但搜索解空间范围增大很多，再配合1个记忆数组就可以保证得到1个较满意的优解，因此，可以在较大程度上减小马尔科夫链的长度，从而节省算法时间。采用以下方式判断产生的新解是否为可行解。

步骤1：对变换后的解解码，求出使用的总车数，若大于配送中心拥有的总车数M，则转到步骤7，否则，转步骤2。

步骤2：求出各线路总配货量D_j和总集货量P_j，若＞或＞，则转步骤7，否则，转步骤3。

步骤3：将各线路总配货量D_j以及各车型Q_k降序排列，按车容量分配车型，若大于某车容量的线路条数超过了大于该车容量的车辆数，则转步骤7，否则，转步骤4。

步骤4：求出每条线路的总长L_j，若存在某线路的L_j大于其对应车型的最大行驶距离L_k，则转步骤7，否则，转步骤5。

步骤5：计算各车型所在路线的每个顾客需求点上货物量状况，若货物量大于该车型最大容量，则转步骤7；否则转步骤6。

步骤6：该解为可行解，计算该解的目标函数值，评价该解。若符合终止条件，则算法终止，否则，转步骤7。

步骤7：重新进行邻域操作，产生变换后的解，转步骤1。

3) 记忆装置的设计。传统模拟退火算法输出时不能保证是本次计算所搜寻到的最优解，本文在算法中内嵌1个记忆数组S，用于传导各优解。算法开始时，将记忆数组初始化为初始解，即：，。若搜索到1个满足各种约束的优解，则对与进行比较，若，则；通过与的比较，不断更新S，最后输出S，就可以得到本次搜寻的最优解。

4) 终止准则的确定。采用混合停止准则，即当温度低于某值或者记忆数组连续g次无变化时，算法终止。此策略简单易行，与初始温度t₀和降温系数一起易于控制算法迭代的步数，易于得到全局最优解，并由g消除不必要的多余迭代，以减少迭代步数，提高算法效率。g的取值根据节点规模而变化，节点规模大，则g较大。

与传统模拟退火算法相比，改进的退火算法在寻优能力、计算效率等方面都更加优化。

3  算例

基于文献[14]中的客户需求数据和文献[20]中的车辆信息，设计如下算例：1个配送中心拥有6种车型，要完成27个既有配货又有集货任务的顾客需求点的配送任务，要求确定选用哪些类型、每辆车的服务路线，使得完成整个配送过程的费用最低。各顾客点的相关信息见表1，车辆属性相关参数见表2。

采用本文给出的改进模拟退火算法，初始温度为100 ℃，马尔科夫链长度即外循环迭代次数为100，降温速度系数为0.98。当温度低于0.2 ℃或者记忆数组连续30次无变化时，算法终止。

利用本文所设计的算法对其求解，得到最小费用为1 465.98元。图3所示为求解过程中温度与目标值变化曲线，其中横轴为温度，纵轴为目标函数值。从图3可以看出改进后的模拟退火算法在跳出局部最优解方面具有优越性。最终的路径安排如图4所示，最优结果的车型、数量及路线如表3所示。为比较单向配送与集配货一体化配送成本，计算多车型单向配送的结果，见表4。同时，将单独配送和集货与集配货一体化配送的结果进行综合比较，见表5。

表1  顾客需求点集配货量

Table 1  Information of customers’ pick-up and delivering

表2  配送车辆属性

Table 2  Property of distribution vehicles

表3  最优计算结果

Table 3  Best computational results

图3  退火寻优过程图

Fig. 3  Optimizing computation process of improved simulated annealing algorithms

从表4和表5可以看出：采用多车型单向配送模式时，为了分别达到最优，配货任务和集货任务需要不同的车辆、不同的路线去完成任务，其中配货任务用车6辆，集货任务用车5辆。通过比较可以看出：相对多车型单向配送方式，多车型集配货一体化配送

图4  集配货一体化最优路线图

Fig. 4  Optimal routes of VRP with pickups and deliveries

方式降低了47.99%的成本，因此，对多车型集配货一体化车辆路径问题的探讨有实际意义。同时，为检验对模拟退火算法改进的效果，与传统模拟退火算法求解结果进行比较，结果如表6所示。

从表6可以看出改进后的模拟退火优越性较明显：1) 由于改进后的模拟退火算法通过4种交换算子实现多邻域操作，使得搜索的空间更加大，更有利于跳出局部最优，寻找全局最优，因此，获得的集配货一体化配送方案的成本更低；2) 由于其采用了多准则终止方法，省去了一些不必要的反复计算，因此，提高了计算效率，求解时间得到了有效降低。

表4  单一任务计算结果

Table 4  Best computational results of single task

表5  单向配送结果与集配货一体化配送结果比较

Table 5  Results comparison of HFVRP and HFFVRPPD

表6  改进模拟退火算法与普通模拟退火算法求解结果比较

Table 6  Results comparison of improved simulated annealing algorithms and general simulated annealing algorithms

4  结论

1) 根据实际配送中出现的多车型集配货一体化问题，建立了HFFVRPPD模型。该模型考虑了不同车型有不同的车容量、不同的初始出行费用、不同的运价及其不同的最大行驶距离等，更加符合实际。

2) HFFVRPPD属于NP-hard问题，因此，更适合采用启发式算法进行求解。求解时对传统的模拟退火算法进行改进，包括设计HFFVRPPD初始可行解的产生算法、基于概率的多算子邻域操作、记忆装置的嵌入、多准则终止方法等。

3) 本文提出的模型与算法对多车型集配货车辆路径优化具有节省配送车辆、减少配送里程、降低配送成本、提高配送效益等优点。

参考文献：

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[2] Solomn M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265.

[3] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research, 1992, 40(2): 342-354.

[4] George I, Manolis K, Gregory P. A problem generator-solver heuristic for vehicle routing with soft time windows[J]. Omega, 2003, 31(1): 41-53

[5] Ho S C, Hangland D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31: 1947-1961.

[6] 周科平, 翟建波. 改进蚁群算法在地下矿山运输路径优化的应用[J]. 中南大学学报(自然科学版), 2014, 45(1): 256-261.

ZHOU Keping, ZHAI Jianbo. Application of improved ant colony algorithm in route optimization of underground mine’s transportation[J]. Journal of Central South University (Science and Technology), 2014, 45(1): 256-261.

[7] 薛雪, 孙伟, 刘晓文. 露天煤矿车辆的不确定调度模型与优化求解[J]. 中南大学学报(自然科学版), 2011, 42(5): 1354-1360.

XUE Xue, SUN Wei, LIU Xiaowen. Uncertain scheduling model and optimization of vehicle in open mine[J]. Journal of Central South University (Science and Technology), 2011, 42(5): 1354-1360.

[8] 高显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学, 2013, 21(1): 125-133.

GAO Xianlong, XU Maozeng, WANG Weixin. Study on multi-types vehicle routing problem and its quantum genetic algorithm[J]. Chinese Journal of management Science, 2013, 21(1): 125-133.

[9] 李进, 傅培华. 具有固定车辆数的多车型低碳路径问题及算法[J]. 计算机集成制造系统, 2013, 19(6): 1351-1362.

LI Jin, FU Peihua. Heterogeneous fixed fleet low-carbon routing problem and algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(6): 1351-1362.

[10] 王晓博, 任春玉, 李海晨. 多车型开放式车辆路线问题的混合启发式算法[J]. 计算机工程与应用, 2013, 49(7): 243-247.

WANG Xiaobo, REN Chunyu, LI Haichen. Hybrid heuristic algorithm for heterogeneous open vehicle routing problem[J]. Computer Engineering and Applications, 2013, 49(7): 243-247.

[11] 葛显龙, 王旭, 邢乐斌. 动态需求的多车型车辆调度问题及云遗传算法[J]. 系统工程学报, 2012, 27(6): 823-832.

GE Xianlong, WANG Xu, XING Lebin. Multi-vehicle scheduling problems and cloud GA based on the dynamic needs[J]. Journal of Systems Engineering, 2012, 27(6): 823-832.

[12] 罗鸿斌. 多车场多车型车辆调度问题的改进粒子群算法[J]. 计算机工程与应用, 2014, 50(7): 251-253.

LUO Hongbin. Study on multi-depots and multi-vehicles vehicle scheduling problem based on improved particle swarm optimization[J]. Computer Engineering and Applications, 2014, 50(7): 251-253.

[13] 刘云忠, 宣慧玉. 车辆路径问题的模型及算法研究综述[J]. 管理工程学报, 2005, 19(1): 124-130.

LIU Yunzhong, XUAN Huiyu. Summarizing research on models and algorithms for vehicle routing problem[J]. Journal of Industrial Engineering and Engineering Management, 2005, 19(1): 124-130.

[14] Saez D, Cristian E, Nunez A. Hybrid adaptive predictive control for the multi-vehicle dynamic pick-up and delivery problem based on genetic algorithms and fuzzy clustering[J]. Computers & Operations Research, 2008, 35(11): 3412-3438.

[15] Hoff A, Gribkovskaia I, Laporte G, et al. Lasso solution strategies for the vehicle routing problem with pickups and deliveries[J]. European Journal of Operational Research, 2009, 192(3): 755-799.

[16] Amico M D, Righini G, Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection[J]. Transportation Science, 2006, 40(12): 235-247.

[17] 陶胤强, 牛惠民. 带时间窗的多车型多费用车辆路径问题的模型和算法[J]. 交通运输系统工程与信息, 2008, 8(1): 113-117.

TAO Yinqiang, NIU Huimin. Model and heuristic algorithm for the multi-type vehicles routing problem with multiple costs and time windows limits[J]. Journal of Transportation Systems Engineering and Information Technology, 2008, 8(1): 113-117.

[18] Lin S W, Yu V F, Chou S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic[J]. Computers & Operations Research, 2009, 36(5): 1683-1692.

[19] Toth P, Vigo D. The vehicle routing problem[M]. Siam, USA: Society for Industrial and Applied Mathematics, 2002: 10-40.

[20] 李相勇. 车辆路径问题模型及算法研究[D]. 上海: 上海交通大学管理科学与工程, 2007: 56-78.

LI Xiangyong. A study on models and algorithms for vehicle routing problems[D]. Shanghai: Shanghai Jiaotong University. Management Science and Engineering, 2007: 56-78.

(编辑  陈灿华)

收稿日期：2014-07-22；修回日期：2014-09-26

基金项目(Foundation item)：国家自然科学基金资助项目(70971036)；湖南省软科学研究计划项目(2013ZK3026) (Project(70971036) supported by the National Natural Science Foundation of China; Project(2013ZK3026) supported by Soft Science Research Plan of Hunan Province)

通信作者：单汨源，教授，博士生导师，从事运营管理、项目管理与调度优化研究；E-mail: yanchen@hnu.edu.cn