物流车辆调度一般模型及启发式算法求解现状及研究方向

赵建峰，梁伯栋

（深圳职业技术学院，广东 深圳 518055）

1 前言

物流服务提供者通过运输、存储、装卸、包装、流通加工、配送和信息管理等方式满足客户的物流需求，其过程中将企业的采购、生产、制造、销售紧密地联系在一起，是现代社会企业发展的“加速器”和“第三利润源泉”。随着我国经济的不断发展，物流业已经成为社会经济的基础组成部分，根据《2016年全国物流运行情况通报》，我国2016年全国社会物流总额为229.7万亿元，比上年增长6.1%。在物流行业高速发展的同时，物流行业费用依然较高，2016年社会物流总费用11.1万亿元，与GDP的比率为14.9%，与欧美等发达国家10%的比率相比依然有很大提升空间。因此，如何降低物流费用，对于提升我国经济具有重要意义。

在物流领域，车辆货物的装配及车辆路径的规划对于提升物流调度效率、降低物流成本具有重要意义。但是，由于车辆货物的装配及运输路径规划均是NP难题，如何求解该问题一直是物流领域的难题，受到诸多学者关注，如：文献[1]对物流车辆的调度问题进行了综述，描述了物流调度的一般模型，指出了车辆调度主要的优化目标，并对调度模型进行了分类，同时指出模型求解方面，包含精确算法、传统启发式算法和现代智能算法。文献[2]较好地对物流配送车辆优化调度问题进行了综述，对物流车辆调度文件进行了较好地分类，描述了调度模型及主要求解算法。文献[3]对配送车辆调度路径优化问题进行了深入分析，并进行了概况和分析。首先给出了物流配送调度包含的要素：道路、货物、车辆、物流中心、客户、运输网络、约束条件等，然后对VRP问题进行了分类，并对VRP的理论基础进行了介绍。文献[4]对包含产品生产在内的车辆调度问题进行了综述。文献[5]对多约束的车辆调度问题（multi-constrained Vehicle Routing Problems,VRPs），也称 Rich Vehicle Routing Problems(RVRPs)进行了综述，包含：对RVRPs进行了分类并给出了一个定义。

上述文献较好地对物流车辆调度问题进行综述，然而，缺乏对车辆调度模型的具体描述，在求解方面，只描述了启发式算法的求解方法，未对算法的求解过程进行描述，特别是基因编码方法及算法迭代进行描述。本文首先对物流调度问题进行简单介绍，然后，在综合各个文献研究的基础上，抽象出一个典型的物流调度模型并进行了详细的描述，并对当前主流的求解算法从基因编码及算法迭代两个方面，进行了综述。通过本文献，研究者能够快速了解当前物流车辆调度的最新进展并结合自身的经验，提出更加有效的模型或求解方法。

2 物流车辆调度典型模型

在费用最小、时间最少等约束下，如何将物流中的各种货物合理的装载在对应的车辆并运输到相应的目的地，对于提升物流行业的效率具有重要意义。

大家目前认为最早提出物流调度模型的是Dantzig等[6]，该文献以汽油车的向加油站配送汽油为研究案例，提出了物流车辆的调度问题并采用线性规划进行求解。典型的物流车辆调度，如：物流货物配送、便利店货物配送、企业生产仓储配送等，其总的目标是将货物从一个地方（仓库）运输到多个客户并达到运输成本最小、运输时间最短、运输路径最短等目标中的一个或多个，同时假定货物的最大重量或最大体积不超过车辆的最大载重或最大体积。

通过阅读目前的文献，其物流调度模型可以抽象为一个具有代表性的物流调度模型，用形式化的语言可以描述为，存在一个路网G={V,W}，如图1所示，其中，V为路网节点，W为路网间相互连通的带权路径，通常为路径的长度及行驶时间，用（wlij，wtij）表示。其中，V0为中心仓储节点，存有待运输的货物集F，V1，V2，…Vi，…，Vn，为待服务的客户，Wij为Vi和Vj之间的连通权重。运输车辆Ci={ID，Wei，Vol，Pri}，i=1，2，…,c，其中，ID表示车辆的标识，Wei为车辆载重，Vol为车辆容积，Pri表示该车辆运输一公里的价格；仓储货物 Fi={ID，Wei，Vol，Des}，i=1，2，…，f，其中，Des表示货物的目的节点。

因此，在上述形式化描述下，车辆的调度目标为：

图1 带权的路网

寻找最佳的车辆行驶路径 P(p1，p2，…，pc)，s.t min F={price,time,path}

其中，pi={Vi1,Vi2,…,Vil}表示车辆经过的节点，

同场PK：将葛兰许和Bin 707放在一起PK是极其不公平的，这里不过是想比较一下两款酒的风格而已，因为Bin707近年价位越来越逼近葛兰许，是Penfolds众多红葡萄酒中最为强壮、饱满的代表。707充满力量，却不会让你觉得太霸道，浓郁的黑浆果香，入口复杂的香料香和更多层次的香气。葛兰许要深沉和沉稳很多，它是一款你得要品尝到第三口才能喝明白的年份，刚开始有很多你无法形容的感受。

并且满足：

在典型模型中，对调度边界条件、调度方式等做了相应的假定，即：每个客户通过一次服务可以完成服务，待运输货物的总重量不超过车辆的总载重和总体积，每次运输都可以达到车辆的满载运输等，同时也未对货物或客户服务动态变化的情况予以考虑。目前，主要的文献研究都是基于本文抽象出的调度模型，在此基础上，将模型的边界条件及限定条件进行修订，以达到不同的研究目的，如：车辆运输并非满载运输[7]，其假定车辆的装载并不满载，只需要满足客户的需求即可；更多约束条件下的物流车辆调度问题，如文献[8]就研究了带弹性时间约束的车辆调度问题；发货点更多更加复杂[9-11]；车辆类型更多样[12]；时间约束更严格[13-14]、多装货地点多卸货地点；车辆、货物、客户动态变化下的物流调度求解问题[16-17]等。

3 常见启发式求解算法

启发式算法是一类通过模仿自然界的生物特性进而获得问题的近似解的求解算法。在现实世界中，存在一类问题，其无法通过精确求解的方法获得最佳解，而只能通过不断迭代试错的方式获得近似解。通常此类问题具有较大的求解空间，在有限的时间内遍历算法所有的解。因而，通过模拟自然界生物的求解过程，如：遗传进化、蚂蚁寻求食物、鸟群觅食、退火过程等，以在较短的时间内获得问题的近似解（可接受解）。物流车辆调度中，从主体角度分析，涉及到调度中心、配送点、货物及车辆，从问题求解过程分析，涉及到车辆的装配、车辆路径的规划等，其求解过程是典型的NP问题，因此，使用进化算法进行求解是一种典型的求解方法，典型的文献有：遗传算法[18-19]、蝙蝠算法[20]、多智能体[21]、粒子群算法[22]、蚁群算法[23]、模拟退火算法[24]、免疫算法[25]、混合算法，即包含了多种启发算法的求解方法，如文献[26]使用了遗传算法和模糊规则。

在进化算法求解中，其求解过程分为两个核心部分：编码和迭代。编码是用计算机表示问题的解的方式，迭代是对编码进行不断更新以获得更优解的方法。在编码中，对于物流调度问题，常见的有整数编码方法、实数编码方法；而迭代问题，以遗传算法的基因迭代和粒子群的迭代算法最具代表性。本文以前文描述的调度模型为基础，对这两种典型的编码方法和迭代方法进行详细介绍，以使研究者清晰了解当前物流调度问题的启发式求解过程。

3.1 编码方法

（1）整数编码方法[14,27-28]。用一组长度为n+c+1的实数进行编码，表示一组调度方案，如：一个调度中包含8个客户节点3辆车，则一个编码为047201308560，其对应的含义为：车辆1负责客户4、7、2的运输，车辆2负责客户1、3的运输，车辆3负责8、5、6的运输，客户顺序亦为车辆行驶路径。

（2）粒子编码方法，实数编码方法[11-22]。用一组长度为n的实数向量表示，实数整数部分表示该节点客户由那个车辆进行服务，小数部分的大小决定了车辆的行驶路径。如：一个调度中包含8个客户节点，2辆车，则n=8，对应的编码为[1.232,2.356,1.587,2.654,2.965,1.852,1.478,1.357],则表示节点1,3,6,7,8由车辆1进行服务，节点2,4,5由车辆2进行服务，车辆的行驶路径为，车辆1：0-＞1-＞8-＞7-＞3-＞6-＞0;车辆2：0-＞2-＞4-＞5-＞0。

3.2 迭代方法

在进化算法中，必须通过迭代的方法获取更优的下一代个体，如遗传算法是通过选择、交叉、变异来进行。一个典型的遗传算法（整数编码）迭代过程如下：

其中，n为种群大小，fi为染色体i的适应值，则个体pi的累积概率为：

生成一个随机数r，若 pi-1＜r≤pi，则选择个体i作为下一代个体种群。

（2）交叉。对于两个个体，随机选择一个任务点，并交换相应的任务点，为保证编码中个体不重复，需要替换个体中相同点，示例如下：

（3）变异。对一个个体，随机选择两个任务点，并交换位置，示例如下：

Pi=[012034506780]互换一个位置Pi1=[012037506380]

对于粒子群算法，则通过个体的最佳位置和群体的最佳位置来计算个体的下一个运动位置，一个典型的粒子群算法（实数编码）的主要计算过程如下：

设粒子i在t时刻的状态为Xit，则粒子i在t+1时刻的状态：

其中，λ是惯性权重，表示粒子的当前位置对粒子移动到下一个位置的影响；α、β为加速系数，pBest表示粒子运动中出现的最佳位置，gBest表示粒子群的最佳位置，r1、r2为随机数。

4 未来的研究方向

（1）新能源物流车调度。新能源车是未来发展的趋势，相比传统燃油车，新能源车在单位运输成本方面有较大的优势，同时物流企业也更容易提供固定的充电桩，因此，未来城市物流一定使用新能源车作为运输工具。新能源车相比传统燃油车，其运输里程和充电时间、位置都需要在运输中进行考虑，其物流车辆的调度更加复杂，这是未来物流调度研究方向之一，具体内容可以参考文献[29]。

（2）基于物联网及车联网的物流运输。目前，调度模型的假设都是以零售配送为原型设计，现代物流的复杂已经远远超过了经典的物流调度模型。如：动态的物流调度模型，在运输过程中，可以动态地根据客户的需求调整物流过程；基于预测及大数据分析的物流调度方法，可以依据数据的分析，精准的调整物流配送的过程，确保整个物流环节尽可能达到零库存。

随着物联网的发展，物流货物的信息，包含体积，重量、目的地、时间约束等信息可以更加充分的获取，同时车辆的状态也可以通过车联网实时获取，因此，如果更好地匹配货物和车辆是一个重要的研究方向。同时，由于上述技术发展所带来的实时动态物流调度也是一个研究方向。

（3）更加高效的编码方法。首先，目前以节点为序的编码方式，限制了基因表达的多样性，只能局限于对特定问题的求解，限定条件较多。如：经典的整数编码方法，限定了每个服务点允许且只允许访问一次，一个服务节点可以通过一次服务满足其需求。这种限定条件在特定的物流环境，如：零售配送是适用的，但是对于仓储物流，如，不同仓储节点间的调度，很多仓储节点是不可以通过一次服务得以满足，必须通过多辆车进行服务以满足其调度需求。

其次，目前对于物流车辆的调度，无论是整数编码还是实数编码，其编码效率较低。如：实数编码要求以节点为编码，要求每个节点出现且只出现一次，这就极大地降低了解空间的遍历效率，容易陷入局部最优。同时，以0为车辆遍历路径的分割点，这种分割在初始化时便确定，存在部分解无法遍历的问题。

因此，寻找更加有效的基因编码方法是物流车辆调度的一个研究难点。一种较为可行的研究思路是，不在采用以节点为编码的方式，可以考虑以车辆为编码或者以货物为编码，进而建立更加符合实际需求的调度模型。

[1]肖柯伟,陈志,赵博.物流配送车辆调度问题智能算法研究进展[J].物流科技,2015,(12):21-24.

[2]杨弋,顾幸生.物流配送车辆优化调度的综述[J].东南大学学报(自然科学版),2003,(S1):105-111.

[3]浮萍萍,叶春明,李佳桐.物流配送车辆调度路径优化问题算法研究[J].物流科技,2015,(3):5-8.

[4]Adulyasak Y,Cordeau J-F,Jans R.The production routing problem:A review of formulations and solution algorithms[J].Computers&Operations Research,2015,55(Supplement C):141-152.

[5]Lahyani R,Khemakhem M,Semet F.Rich vehicle routing problems:From a taxonomy to a definition[J].European Journal of Operational Research,2015,241(1):1-14.

[6]Dantzig G B,Ramser J H.The Truck Dispatching Problem[M].INFORMS,1959.

[7]杨贵红.非满载物流车辆调度优化方法研究[J].计算机仿真,2017,(3):147-150.

[8]Manisri T,Mungwattana A,Janssens GK,et al.A Hybrid Algorithm for the Vehicle Routing Problem with Soft Time Windows and Hierarchical Objectives[J].Journal of Information and Optimization Sciences,2015,36(3):283-300.

[9]王桢,黄磊.考虑订单发货区域的物流配送调度问题研究[J].计算机应用研究,2016,(1):82-86.

[10]金涛.多配送中心物流车辆调度的改进差分进化算法[J].计算机工程与应用,2014,(3):232-235.

[11]邓先瑞,于晓慧,李春艳,等.基于种群分类粒子群算法的物流车辆调度优化[J].计算机工程与应用,2016,(10):237-240.

[12]王阳明,赵利.基于多车型多约束的动态车辆调度算法研究[J].计算机工程,2016,(9):305-309.

[13]任雪甜,朱晓敏,何中祥,等.基于改进C-K节约算法的第三方冷链物流企业车辆调度[J].北京交通大学学报,2015,(4):125-132.

[14]黄遵娟.基于遗传算法的城市冷链物流配送路径优化研究[J].经营与管理,2017,(8):97-101.

[15]李秀娟,杨玥,蒋金叶,等.蚁群优化算法在物流车辆调度系统中的应用[J].计算机应用,2013,(10):2 822-2 826.

[16]张婷,赖平仲,何琴飞,等.基于实时信息的城市配送车辆动态路径优化[J].系统工程,2015,(7):58-64.

[17]冯亮,梁工谦.联网中物流配送车辆调度目标定位设计与仿真[J].计算机仿真,2017,(4):377-381.

[18]郑丹阳,毛剑琳,郭宁,等.求解动态需求车辆调度问题的自适应量子遗传算法[J].传感器与微系统,2017,(8):130-133.

[19]张玉,贾遂民.多资源约束的车辆调度问题的改进遗传算法[J].计算机工程与应用,2016,(7):253-258.

[20]张晓磊,马从安,申晨.物流云服务下基于改进蝙蝠算法的任务调度[J].计算机应用研究,2015,(6):1 676-1 679.

[21]席钌姿,张峰.基于多智能体技术的物流运输调度系统分析[J].物流工程与管理,2017,(5):67-70.

[22]吴聪,杨建辉.基于改进粒子群算法的物流配送车辆调度优化[J].计算机工程与应用,2015,(13):259-262.

[23]王晓东,张永强,薛红.基于改进蚁群算法对VRP线路优化[J].吉林大学学报(信息科学版),2017,(2):198-203.

[24]唐冲.基于模拟退火算法的应急物流车辆调度[J].物流技术,2017,(1):114-116.

[25]潘世举.应急物流车辆调度优化中免疫算法的应用[J].物流技术,2016,(7):80-82.

[26]张潜,李钟慎,胡祥培.基于模糊优化的物流配送路径(MLRP)问题研究[J].控制与决策,2006,(6):689-692.

[27]甘宝,薛玉玺,魏文萍.基于改进遗传算法的车辆路径问题[J].交通运输研究,2015,(4):88-94.

[28]冯辉宗,陈勇,刘飞.基于遗传算法的配送车辆优化调度[J].计算机集成制造系统,2004,(S1):81-84.

[29]Juan A,Méndez C,Faulin J,et al.Electric Vehicles in Logistics and Transportation:A Survey on Emerging Environmental,Strategic,and Operational Challenges[J].Energies,2016,9(7):86-107.