物流配送车辆调度问题智能算法研究进展

2015-12-20肖柯伟XIAOKeweiCHENZhiZHAOBo

物流科技 2015年12期

肖柯伟，陈志，赵博 XIAO Ke-wei, CHEN Zhi, ZHAO Bo

（1. 中国农业大学工学院，北京100083；2. 中国机械工业集团有限公司，北京100080；3. 中国农业机械化科学研究院，北京100083）

(1. College of Engineering, China Agricultural University, Beijing 100083, China； 2. China National Machinery Industy Corporation,Beijing 100080, China； 3. Chinese Academy of Agricultural Mechanization Science, Beijing 100083, China)

0 引言

物流配送车辆优化调度问题是由Dantzig 和Ramser[1]于1959 年首次提出的，一般认为它是车辆路径问题（Vehicle Routing Problem）和车辆排程问题（Vehicle Scheduling Problem）的统称。车辆路径问题一经提出，就受到了组合数学、网络分析、图论、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，他们进行了大量的理论研究和实验分析，并将其研究成果成功运用在运输、物流配送、快递收发等系统中。目前，我国物流需求规模保持较高增幅，物流成本逐年攀升，物流配送车辆调度问题在企业运营中的作用越来越大。而物流配送车辆调度问题的研究目标就是要降低物流企业成本、提高物流配送的效益、提高企业竞争力，进而达到发展现代物流配送系统、促进产业结构调整、推动区域经济发展的战略目标。因此，该问题一直是国内外研究的热点。

1 车辆调度问题概述

1.1 车辆调度的优化目标

车辆调度问题是在满足一定约束条件下，选择某种目标作为优化目标，实现总配送成本（广义的配送成本，如配送时间、总费用、需要车辆等）最优[2]。其中总配送成本一般表现为最小化总费用，即车辆完成配送任务的各项费用之和最小，如车辆启用固定费用、车辆行驶费用、车辆等待费用、车辆服务费用、车辆惩罚费用等；最小所需车辆数即完成全部配送任务所需总车辆数最小；最小总距离即完成全部配送任务车辆路径总长度最小；最短服务时间即完成全部配送任务总配送时间最小，配送时间一般包括车辆行驶时间、等待时间、服务时间和延误时间等。

1.2 配送车辆优化调度的模型

通过建立数学模型来定量研究物流配送成本的方法，目前可以归纳为三类：车辆流模型、物资流模型和集覆盖模型。从建立模型时的出发点考虑，绝大多数模型可以看做这三种模型的变形与组合。在派出一辆车固定费用高于行驶费用时，一般采用车辆流模型。本文车辆调度问题采用的就是车辆流模型。

物流配送车辆调度问题数学模型可描述为：车辆由配送中心发出，对每一个客户按照时间或其它要求配送到，车辆完成配送后返回配送中心，规定每个客户只能由一辆车对其进行服务且只服务一次，要求在满足约束条件（如载重约束、时间约束、里程约束等）下对车辆行驶路径进行优化，使完成配送的优化目标（成本、路程、车辆数等）最小。

物流车辆调度问题的数学模型是目标规划模型，其结构特征一般为：

1.2.1 有载重约束的车辆调度模型。车辆调度问题根据载货任务情况可分为非满载车辆调度问题以及满载车辆调度问题。非满载车辆调度问题要求每个客户需求量少于车辆载重量，一辆车能够同时给一个或多个客户运送货物。大多数时候一次任务不能恰好装满整车，这往往造成车辆装载率不高。满载车辆调度问题中，客户需求不小于车辆载重量，完成每次任务都需要满载行驶，配送过程需要多辆车满载，存在着最后一辆车非满载的情况。

目前，对于车辆调度问题的研究以非满载车辆调度问题为主。首先，给出决策变量：

下面对非满载车辆调度问题建立车辆调度模型。

其中：F为车辆固定费用，m为车辆数，cijk为单位里程成本，dij为客户i到客户j的距离，qi为客户需求量，Q为车辆载重量，Lk为车辆最大行驶距离；式（2）是载重约束，式（3）是每个需求客户由一辆车来完成，式（4）是车辆最大行驶距离限制，式（5）表示每个客户都能得到车辆的配送任务，式（6）、式（7）表示两个变量之间的关系，式（8）、式（9）表示决策变量为0-1 约束。

1.2.2 有时间约束的车辆调度模型。时间约束问题可分为硬时间窗约束、软时间窗约束、混合时间窗约束三种。硬时间窗约束模型对不能在规定时间内运达的给予一较大的惩罚M值（即成本升高），从而降低其适应值；软时间窗约束模型是对不能在规定时间运达的给予惩罚，惩罚值依到达时间与规定时间的差值而定；混合时间窗模型则是对不能按规定时间运达的分段处理，在可接受时间范围内采用软时间窗问题处理，超过可接受时间范围则采用硬时间窗问题处理。

硬时间窗问题惩罚函数设置：车辆必须在[ei,li]时间内到达，否则给予其较大惩罚值M。下面建立带硬时间窗约束的车辆调度模型：

需添加时间窗约束方程式：

其中：ti为配送车辆到达客户i的时间，Ti为在客户i处装卸货所耗费的时间，tij表示车辆从i到j所用的时间，T为一足够大的常数。

1.2.3 有里程约束的车辆调度模型。带里程约束问题的现实来源是车辆油箱容积限制。也有一种经济学解释：车辆在行驶超过一定里程后会收取燃料附加费。其数学模型见1～9。

2 智能算法在物流配送车辆路径问题中的应用

通过对已有文献进行总结归纳，车辆调度问题求解算法可以分为三类：精确算法、传统启发式算法和现代智能算法。鉴于精确算法计算能力有限、计算时间长，传统启发式算法易陷于局部最优、参数设置过于影响算法效果，目前，现代智能算法是研究车辆调度问题的主流算法。用于车辆调度问题的智能算法主要有：遗传算法、蚁群算法、人工神经网络算法、模拟退火算法、禁忌搜索算法等。虽然智能算法具有全局搜索能力强，运算方便等优点，但是也存在着局部搜索能力差、收敛时间过长、易陷于局部最优等问题，单一智能算法不是车辆调度问题的最有效算法。混合算法是当今研究车辆调度问题的热点算法。

2.1 混合遗传算法

在实际运算过程中，遗传算法存在着局部搜索能力差、易早熟等问题，而邻域搜索算法、模拟退火算法、量子进化算法等却具有较强的局部搜索能力，能够快速收敛。现有研究也证明了常规遗传算法往往不是求解具体问题的最有效算法，而将遗传算法与某些算法结合起来构成混合算法，却有可能产生求解性能极佳的方法。

2.1.1 量子遗传算法。量子遗传算法是20 世纪90 年代后期新兴的一个研究领域，主要是在遗传算法中引入量子计算的一些概念，利用量子态的叠加性和相干性带来的内在并行性来加速算法的求解速度，与其他经典算法本质的区别在于它具有量子并行性。与传统遗传算法相比，量子遗传算法能够在较小的种群规模下，快速地收敛到全局最优。文献[3]研究了动态车辆调度问题，运用量子遗传算法对建立时间轴的车辆调度模型求解，通过与其他算法比较，验证了算法的有效性。文献[4]研究了车辆路径问题，将遗传算法交叉，变异操作引入到量子粒子群算法，取得了较好的效果。

2.1.2 遗传算法与模拟退火算法结合。遗传模拟退火算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法。遗传模拟退火算法具有遗传算法的整体搜索能力和模拟退火算法的局部搜索能力，算法运算效率高[5]。文献[6]结合tsp 问题的特点，运用遗传与模拟退火算法相结合的遗传模拟退火算法，成功解决了该tsp 问题。

文献[7]研究改进遗传模拟退火算法，采用多层并行搜索结构，给出了一种早熟评价指标，并成功将该算法应用于tsp 问题中。

2.1.3 遗传算法与其他算法的混合算法。文献[8]采用遗传算法与最近邻域算法结合混合遗传算法解决单车线路优化问题，在可行时间内得到了满意解。文献[9]研究了模糊需求的车辆路径问题，以模糊可信行理论为基础，引入扫描算法进行种群的初始化，结合配送分队数和剩余载重因素提出了混合交叉算子。文献[10]研究了一类具有多个配送中心、需要进行车辆租赁和车辆共享、有时间窗限制、开环的VRP 问题，设计了一种结合扫描算法和C-W 节约算法对车辆路径和车辆调度统筹优化的混合遗传算法。

2.2 混合粒子群算法

2.2.1 量子粒子群混合算法。量子粒子群算法是将量子进化算法融合到粒子群中产生的。该算法中粒子的位置是由量子比特进行编码，粒子位置的更新是由量子旋转门来完成。文献[11]研究了带时间窗车辆调度问题，提出了一种基于粒子碰撞的离散粒子群算法，成功解决该问题。文献[12]将量子粒子群算法与模拟退火算法相结合，用来求解带时间窗的车辆路径问题。文献[13]提出混沌量子粒子群算法，并将它应用于车辆调度问题，取得了较好的效果。

2.2.2 粒子群算法与模拟退火算法。粒子群—模拟退火融合算法增强了粒子群优化算法的全局搜索能力和跳出局部最优的能力，增加了粒子群的多样性，提高了算法收敛速度。文献[14]针对改进的车辆调度模型，设计了混合粒子群算法，用粒子群算法来分配每辆车的客户，用模拟退火求解每辆车完成运输任务的次序，避免了单纯粒子群算法编码复杂的缺陷，求出了其有效近似解。文献[15]提出粒子群算法与模拟退火算法结合的混合粒子群算法，快速求得带时间窗车辆路径问题的优化解。

2.2.3 粒子群算法与其它算法的混合算法。文献[16]研究了带时间窗车辆调度问题，提出改进的粒子群优化算法，在惯性权重递减的基础上通过群体极值进行t分布变异。文献[17]建立了多车场多车型车辆路径调度问题的数学模型，提出了在种群中的粒子采用一定的概率进行柯西变异的改进粒子群算法。

2.3 混和蚁群算法

2.3.1 量子蚁群算法。量子蚁群算法是一种概率优化算法，它以量子计算的理论和概念作为基础，具有较强的全局寻优能力和丰富的群体多样性。文献[18]采用量子蚁群算法研究带时间窗的车辆路径问题，通过定义人工蚂蚁的转移概率，增加量子比特启发式因子，以及用量子旋转门实现信息素更新，从而提高算法全局搜索能力，有效避免了算法陷入局部最优。文献[19]通过量子蚁群算法对物流配送路径优化问题进行求解，对各路径上的信息素进行子比特编码，采用量子旋转门及最优路径对信息素进行更新，有效解决了物流配送路径问题。

2.3.2 蚁群算法与粒子群算法结合。蚁群粒子群混合算法同时具有蚁群算法的大规模寻优特性和粒子群算法的较强局部搜索能力，在确保全局收敛性的基础上，能够快速搜索到高质量的优化解。文献[20]建立货运关系明细的多需求点车辆调度模型，模型求解过程是先由粒子群算法的粒子位置向量得到单车运送的货物，再由蚁群算法优化单车路径，根据优化目标筛选粒子，直到终止条件，实现所有货物对所有车辆的分配。

2.3.3 蚁群算法与其他算法结合。文献[21]采用改进蚁群算法，引入信息变异算子和种群入侵算子，较好地求解了多车场多车型最快完成车辆路径问题。文献[22]设计了一种改进的蚁群算法，将蚁群系统（ACS）与最大最小蚂蚁系统（MMAS）相结合，求解了带时间窗的车辆路径问题。文献[23]提出了一个能同时利用演化算法的全局优化能力和蚁群算法的局部探索能力的混合智能优化算法，对动态网络环境下动态需求的最优路径搜索问题进行了研究。

3 总结与展望

车辆调度问题尽管在模型和算法方面已取得了大量的成果，但是由于该问题涉及的因素多，仍有很多重要问题值得进一步研究。目前研究的缺陷主要体现在：①研究目标单一，应用价值不大。在实际研究中，客户需求各异甚至相互冲突，如客户满意度的提高和运作成本的降低就可能是一对效益相反的矛盾。因此，在决策中需要更多地考虑多目标的情况，但以往对车辆调度问题的研究主要集中于单一目标问题，对多目标问题的研究尚显不足。一个值得深入研究的方向是采用线性加权法或理想点法等评价函数法将多目标优化问题转化为单目标优化问题，从而求得多目标优化问题的pareto 最优解。②模型考虑因素单一，与实际应用尚有距离。现今研究的模型多因为建模的方便和可行性，建模过程相对理想化，人为的增加或减少一些约束，这往往与实际不符。考虑的因素一般不能全面反映具体物流车辆调度模型，如车辆满载与非满载耗油量是不同的，相应燃料费用也是不一样，但往往在实际模型中没有考虑这点或者做简单线性处理。③对动态车辆调度问题研究相对较少。动态车辆路径问题取得了一定的研究成果，但是其研究的深度还不够，对动态车辆路径问题的模型研究还很少，对动态信息处理的研究不成熟、解决实际问题的能力还比较差。早前的研究中，动态车辆调度问题主要是采用静态调度问题的研究思路，先根据概率确定动态车辆调度问题中可能出现的因素，然后采用静态车辆调度问题的模型解决。这种研究思路虽然可行，但是对于解决实际问题意义不大。近年来，随着量子算法等新算法和改进算法研究的深入，动态车辆调度问题研究思路也在转变。譬如，利用分布估计算法解决动态车辆调度问题就是值得研究的方向。分布估计算法是遗传算法和统计学相结合的思想，它是基于概率模型的进化，更能适应动态的优化。

今后物流配送车辆调度问题研究的重点还是在调度模型与求解算法这两点上。调度模型越贴近实际，考虑的因素越多，对模型的构建以及求解算法要求越高。目前算法改进思路大致有三种：（1）对现有算法进行细节上调整；（2）采用混合算法的方式；（3）根据对自然界的探索并结合交叉学科提出新的算法。第一种改进思路受算法自身缺陷的限制，求解性能一般；第三种改进思路需要较长时间探索并完善新算法且算法本身也需要进一步改进。所以，在可以预见的较长时间里，求解算法更多会是多种算法的混合，混合算法会是今后研究物流配送车辆调度问题的重点与热点。

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

[2] 葛显龙. 面向云配送模式的车辆调度问题及算法研究[D]. 重庆：重庆大学，2011:4-5.

[3] 王旭，葛显龙，代应. 基于两阶段求解算法的动态车辆调度问题研究[J]. 控制与决策，2012,27(2):175-181.

[4] 黄震. 混合量子粒子群算法求解车辆路径问题[J]. 工程与应用，2013,49(24):219-223.

[5] 周明，孙树栋. 遗传算法原理及应用[M]. 北京：国防工业出版社，1999:78-83.

[6] 杜宗宗，刘国栋. 基于混合遗传模拟退火算法求解TSP 问题[J]. 计算机工程与应用，2010,46(29):40-46.

[7] 乔彦平，张骏. 基于一种改进遗传模拟退火算法的TSP 求解[J]. 计算机仿真，2009,26(5):205-208.

[8] 曹二保，赖明勇，聂凯,等. 大规模物流配送车辆调度问题研究[J]. 湖南大学学报（自然科学版），2007,34(12):89-92.

[9] 吴天羿，许继恒. 基于混合遗传算法的模糊需求车辆路径问题[J]. 解放军理工大学学报（自然科学版），2014,15(5):475-481.

[10] 刘家利，马祖军. 存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J]. 系统工程理论与实践，2013,33(3):666-675.

[11] 李娅，王东，杨跃武,等. 改进的量子粒子群算法求解车辆路径问题[J]. 计算机与数学工程，2013,284(6):870-886.

[12] 李艳芳，姜磊，黄洪亮. 基于量子粒子群优化算法的车辆路径问题[J]. 计算机与数字工程，2008,211(3):25-27.