求解带时间窗动态车辆路径问题的改进蚁群算法

孙 小 军＊1， 介 科 伟

（1.宝鸡文理学院 数学与信息科学学院，陕西 宝鸡 721013；2.西安科技大学 理学院，陕西 西安 710054）

0 引 言

从现代物流管理系统的总体构成来看，车辆路径问题［1］（vehicle routing problem，VRP）是物流管理当中的核心问题之一.尤其在互联网电商交易和物流产业快速发展的今天，如何实时、动态、高效地调度车辆并合理规划行车路径一直是学界和业界共同关注的焦点.作为运筹学中一类典型的组合优化问题，经过国内外专家和学者半个多世纪的研究，车辆路径问题已由早期的静态问题发展成为动态的、带复杂约束条件、多目标、多车场等类型的车辆路径问题，同时还衍生出众多研究分支，带时间窗的动态车辆路径问题（dynamic vehicle routing problem with time windows，DVRPTW）就是其中一个重要的扩展类型.

DVRPTW 发展相对较晚，2000年 Larsen［2］在其论文中首次将时间窗和动态车辆路径问题相联系，并在动态度的定义上做了相关补充.2008年Ahmmed等［3］提出了用多重蚁群优化算法来求解DVRPTW，即在满足使用车辆数目最少和行驶距离最短两个目标函数时，引入两个使用独立信息素且彼此之间存在沟通的蚁群进行求解，从此拉开了运用现代启发式算法求解该问题的序幕.2011年Xu等［4］首次引入随机环境因子、满意水平函数分别描述软时间窗和顾客满意度，并对GLNPSO算法和GLNPSO-ep算法求解模糊随机环境下带软时间窗的动态车辆路径问题的性能进行对比分析.同年，Yu等［5］将不同周期下积累的启发式信息看成多维信息素矩阵，提出一种改进蚁群算法来解决具有周期性带时间窗的车辆路径问题.2012年Hong等［6］考虑将运行时间划分成长度相同的时间片来处理动态请求，并采用事件驱动机制将动态问题分解为一系列静态问题来处理，为带硬时间窗动态车辆路径问题的求解提供了一种方法.同年，Ding等［7］为了避免传统蚁群算法在搜索过程中陷入局部最优解，在信息素的计算中引入灾难因子，提出了一种求解带时间窗的车辆路径问题的混合蚁群优化算法.2013年李妍峰等［8］将城市实时交通信息与车辆路径问题相结合，为动态网络车辆路径优化问题提出了一类将初始路径安排与实时路线调整相结合的求解策略.2015年孙小军［9］结合布谷鸟搜索算法和单亲遗传算法的各自优势，设计了一种求解带时间窗车辆路径问题的混合智能算法，并指出不确定性环境下时间窗车辆路径问题将是该领域未来一个重要的研究方向.2016年张文博等［10］针对动态需求下的带时间窗车辆路径问题，在配送成本最小化和服务准时性最大化的目标下，分别运用改进遗传算法和模拟退火算法通过两阶段策略得到了实时优化后的车辆路径方案.2017年王晓东等［11］针对传统蚁群算法中挥发因子取定值的不足，通过引入节约矩阵作为先验信息引导蚂蚁搜索，并在不同搜索时段选取不同的函数作为信息素挥发，有效地实现了“探索”和“利用”之间的平衡，避免了传统蚁群算法易陷入局部最优解、收敛速度慢等缺点.近年来，随着DVRPTW从理论研究向实际运用的转变，实际问题和不确定性信息的结合成为该问题的一大特点，因此有效开展DVRPTW的应用研究，寻找切实可行的解决方案具有越来越重要的实际意义和研究价值.

1991年，Dorigo等受自然界中蚂蚁觅食行为的启发提出了一种仿生算法——蚁群（ant colony optimization，ACO）算法［12］.蚁群算法作为求解路径规划问题的现代启发式算法之一，具有较强的鲁棒性、优良的分布式计算、易于与其他算法结合等特性，但存在着过早收敛于局部最优解、收敛速度不稳定等缺点［13］.基于已有相关研究成果，本文针对带时间窗的动态车辆路径问题，建立双目标DVRPTW的数学模型，并提出一种求解该问题的改进蚁群（improved ant colony optimization，IACO）算法.该算法基于区域化配送理念，在对顾客进行区域划分的基础上，通过引入交通拥堵因子来改进传统蚁群算法中的状态转移概率公式，提高计算效率；同时考虑到传统蚁群算法中挥发因子在（0，1）上取任意定值时，易造成收敛速度不稳定、陷入局部最优等问题，将挥发因子取为服从（0，1）上均匀分布的随机变量，从而能更稳定地收敛到全局最优解.最后通过一个数值实例，比较IACO算法与文献［10］中的两阶段规划算法和原有方案，以验证算法的计算性能.

1 DVRPTW问题描述与数学模型

1.1 问题描述

DVRPTW是一种在配送过程中信息具有不确定性的车辆路径问题，而信息的变化有很多类型［14］，如路网信息的不确定性（交通路网堵塞或天气变化等）、配送车辆的不确定性（车辆抛锚或临时调度等）、需求信息的不确定性（新顾客的出现和老顾客的缺失等）.在求解过程中所考虑的不确定因素越多，问题的复杂度就越高.本文所研究的DVRPTW可以描述为给定单配送中心和多台配送车辆，在满足配送车辆装载量与顾客时间窗等约束条件下，在制订的初始静态配送方案执行过程中，由于新动态的不断到来，调度系统需要对实时信息进行处理，即对原配送方案实行插入、删除或重新规划配送车辆的行驶路径，最终既能使得所有配送车辆的总运输距离最短，又能提高顾客的满意度.

配送中心一天的工作时序可以表示为在一个完备无向图G＝（V，E）中，其中V为所有节点的集合，E为所有边的集合，令v0为配送中心，其余为顾客点.M辆具有有限装载能力的配送车辆从配送中心出发，在满足配送车辆装载量与顾客时间窗等约束条件下，在初始配送方案的执行过程中，接受调度中心在收到新动态后对原有配送路径的调整，并完成对所有客户需求的配送服务后返回到出发点.其基本原理如图1所示.

图1 配送中心日工作时序图Fig.1 Day working sequential chart of distribution center

其中A为配送开始时刻；B为实时窗口开启时刻；C为实时窗口关闭时刻；D为配送完成时刻；AB为配送前一天接收的订单；BC为配送前一天未完成订单及接受的新订单；CD为配送剩余订单；DA为完成配送后车辆陆续返回配送中心.

DVRPTW中的约束条件主要有［15］

（1）配送中心约束：参与配送任务的每辆车必须从配送中心出发，在完成各自配送任务之后，必须回到配送中心.

（2）车辆载重约束：参与配送任务的每辆车的装载量，在满足初始方案路径上各客户需求量之和的基础上，不能超出各自的最大装载限制.

（3）服务条件约束：在确定配送路径之后，每条线路上只能由一辆配送车辆进行配送，并且每个顾客只能被服务一次.

（4）时间窗约束：在对每一个客户进行服务时，应该在其要求的时间窗内进行.

（5）配送距离约束：在满足配送中心约束的条件下，在整个配送过程中，参与配送任务的所有车辆的总运输距离最短.

1.2 数学模型

根据DVRPTW的特点，采用事件触发驱动和服务后调整车辆路径策略，将配送路径的策略分为固定策略和触发策略［16］.固定策略是在车辆位置及完成节点服务后保证原有路径不变，对剩余节点进行服务；触发策略是在解决由需求信息不确定性带来的问题时，将实时动态需求过程转化为多个瞬时静态子过程，在某个时间节点重新进行调度安排.配送中心在收到新顾客的请求时，首先根据新时间窗和需求量判断新顾客是否可以插入到当前的配送路径当中，如果可以，则进行车辆路径的重新安排；否则，拒绝新顾客的请求或将新顾客的请求安排到次日配送任务当中.

DVRPTW的基本参数设定如下：

Cp表示在时间窗外，因等待、延误而产生的费用；

Ct表示完成任务后的总运输费用；

K表示配送车辆每km的运输费用；

M表示参与配送车辆总数；

v0表示配送中心；

v表示配送车辆；

C表示每辆车使用成本；

dij表示节点i与节点j之间的欧氏距离；

lA（tp）表示tp时刻配送车辆正在服务或已被服务的节点集合；

lB（tp）表示tp时刻加入的新节点或未被服务的节点集 合，不 包 括lA（tp）中的节 点，即lA（tp）∩lB（tp）＝；

l（tp）表示tp时刻所有节点的集合，即lA（tp）∪lB（tp）∪v0＝l（tp）；

［tei，tli］表示节点i的时间窗；

tij、tai、twi、tsi分别表示从节点i到节点j 的行驶时间、到达节点i的时间、在节点i的等待时间、在节点i的服务时间；

Qv（tp）表示tp时刻配送车辆v 的载重，其中Qv（t0）为车辆最大载重；

qi表示节点i的需求量；

P1表示早到的惩罚因子；

P2表示迟到的惩罚因子；

tli表示老顾客i的最大推迟时间；

H（tai）表示在顾客i处按照时间窗惩罚规则计算的惩罚费用；

tas、tws、tss、tls分别表示到达新顾客s 的时间、为新顾客s服务前的等待时间、为新顾客s的服务时间、新顾客s要求的最迟服务时间；

qs表示新顾客的需求量；

q0i表示配送路径中老顾客i取消订单.

基于上述分析，可建立如下总运输成本最小、总惩罚费用最少的双目标DVRPTW数学模型.

目标函数：

约束条件：

为表示参与配送的车辆都从配送中心出发，最后再回到配送中心，建立式（2）、（3）：

为表示每个顾客只能被一辆车进行服务，建立式（4）、（5）：

为表示参与配送车辆的装载量不超过其最大载重，建立式（6）：

将新顾客安排在配送任务中，其需求量应满足：

式（10）、（11）为决策变量.

2 IACO算法介绍

2.1 基本思想

基于“销售渠道通畅、营销区域全覆盖、终端市场全面控制”的现代物流理念，针对DVRPTW的特点和传统蚁群算法的不足，IACO算法首先对所有顾客进行区域划分；其次通过引入交通拥堵因子对影响计算效率和结果的状态转移概率公式进行改进，弥补传统蚁群算法未考虑不确定因素的不足；再针对传统蚁群算法中信息素挥发因子的静态设置容易导致收敛速度不稳定和陷入局部最优的缺点，将挥发因子取为服从（0，1）上均匀分布的随机变量，进而提高了计算效率，并能更稳定地收敛到全局最优解.

2.2 算法步骤

步骤1 配送区域划分［17］.

根据每个顾客的不同需求量，配送区域划分如下：以配送中心为圆心O，画一个包含所有顾客的圆，将各顾客与配送中心连接，在所有顾客中随机地选择一个顾客点A，顺时针旋转线段OA与下一个顾客的相应线段OB共线，判断顾客A、B的需求量之和与配送车辆最大载重的大小关系，若顾客A、B的需求量之和不超过配送车辆的最大载重，则继续转动，判断下一个顾客是否可划入当前区域，依次类推；否则，若累加当前顾客对货物的需求量后超过配送车辆最大载重，则将该顾客之前的所有顾客划分到同一区域.同理，直到所有顾客被划分到相应区域，划分终止.分区原理和分区结果如图2所示.

步骤2 利用IACO算法对单个区域进行求解.

（1）初始化参数

设置传统蚁群算法中的启发因子、期望因子、蚂蚁数量、信息素增加强度系数、最大迭代次数.

（2）状态转移概率公式的改进

在传统蚁群算法的状态转移概率公式中引入交通拥堵因子，得到新的状态转移概率公式：

图2 区域划分图Fig.2 The chart of area division

式中：α、β、γ分别表示信息素重要程度、启发因子重要程度、交通拥堵重要程度；τij（t）、ηij（t）、δij（t）分别表示t时刻从i到j的信息素含量、启发因子、交通拥堵因子［16］；adk＝｛1，2，…，n｝－auk，表示蚂蚁k下一步可以选择的顾客集合，auk表示蚂蚁k已经走过的顾客集合.

（3）修正挥发因子

在实际路径选择中，挥发因子的取值往往是随机变化的，为了反映这种变化，令挥发因子服从（0，1）上的均匀分布：

从而得到新的信息素更新公式：

其中ρ为局部信息素挥发因子，（1－ρ）为局部信息素的保持因子，Δτij（t）表示信息素增量.

（4）确定配送路径，计算当前最优解

随机将蚂蚁放于不同顾客点，将每个蚂蚁访问过的顾客进行记录，直至所有顾客被访问，得到禁忌表au，记录当前最优配送路径并计算其长度.

（5）对所有顾客进行多次遍历

利用式（12）确定下一时刻要访问的顾客，并利用式（13）更新挥发因子取值，将禁忌表au清零，返回（4）.

（6）终止条件

采用指定迭代次数的终止原则.令Nc＝Nc＋1，如果Nc≤Nc＿max，则转至（5），否则保存该区域的最优配送路径.

步骤3 判断划分的所有区域是否都已找到最优配送路径，若都已找到，转步骤4，否则，转步骤2.

步骤4 计算最优目标函数值.

2.3 算法流程图

在求解实际问题时，IACO算法可按图3执行.

图3 算法流程图Fig.3 Algorithm flow chart

3 实验结果与分析

3.1 实验结果

本文采用Python 3.6.2、Matlab 2014a作为编程工具，在 Windows处理器3.20GHz、Intel Core i5-6500CPU、内存8.0GB的实验平台上，验证本文算法的有效性和优越性.这里的数据来源于文献［10］，且具体参数如下：车辆最大载重60件，车辆使用成本100元，每km费用5.5元，配送中心时间窗［Ta，Tb］＝［7：00，18：00］，动态服务时间窗［Tc，Td］＝［7：00，15：00］，实时服务时间的间隔为2h（即当天有4个动态服务时间窗），早到和迟到的配送惩罚因子分别为P1＝10元／h、P2＝40元／h，配送中心的坐标为（0，0），车辆行驶速度为40km／h.基于文献［18］，在早晚高峰时间段（7：00～9：00、17：00～19：00）道路交通运行指数介于轻度拥堵与拥堵之间，此时交通拥堵因子为4；其余时间段道路交通运行指数介于基本畅通与缓行之间，此时交通拥堵因子为2.初始顾客信息如表1所示.

表1 初始顾客信息汇总表Tab.1 Summary table of initial customer information

利用IACO算法计算得到初始的配送方案为0→1→24→23→2→3→0；0→17→18→22→21→20→19→0；0→9→15→16→7→8→6→5→0；0→14→13→12→11→10→4→0，如图4所示.

图4 初始配送方案Fig.4 Initial distribution plan

表2 需要更改信息的顾客汇总表Tab.2 Customer summary table of needing change information

表3 新增顾客信息汇总表Tab.3 Summary table of new customer information

根据物流配送的实际情况，假设当日配送中心在动态服务时间窗开启之后接到的动态信息如表2、3所示.显然，从表2、3中可以看到：在当天的4个动态服务时间窗内均有动态信息呼入，因此相应分区内配送路径需利用IACO算法做更新调整.由于在第1个动态服务时间窗［7：00，9：00］内，加入了新顾客25号，根据步骤1可知，25号顾客属于第1分区，所以对第1分区的路径重新规划调整后为0→1→25→24→23→2→3→0；在第2个动态服务时间窗［9：00，11：00］内，有新顾客26、27号加入，并且老顾客24、17号更改了时间窗，所以重新规划路径后得到：0→1→24→25→23→2→3→0；0→17→18→27→19→22→20→21→0；0→9→15→16→7→8→6→5→0；0→14→13→12→11→10→26→4→0；在第3个动态服务时间窗［11：00，13：00］内，增加了新顾客28号，而老顾客17、24号取消了订单，但因为17号顾客是第2分区中第1个被配送的顾客，而接到取消订单时间是11：33，所以该动态信息可忽略.因此调整后的配送路径为0→1→25→28→23→2→3→0；在第4个动态服务时间窗［13：00，15：00］中增加了新顾客29号，由于各分区配送车辆在完成分区内其余顾客的配送任务后，都无法满足新顾客29号的需求量，如果安排新的车辆对29号顾客进行配送，无疑会使总运输成本增大，所以29号顾客被安排与下一批顾客一起配送.因此，在对所有动态信息处理后，需安排4辆车来完成配送任务，且最终配送路径如图5所示.

图5 最终配送方案Fig.5 Final distribution plan

3.2 实验结果分析

为了说明本文算法的优越性，将IACO算法与文献［10］两阶段规划算法所得到的配送方案、配送公司原有方案进行对比，结果如表4所示.

由表4可以看出：IACO算法在总距离、总成本这两个主要指标上均大幅度优于两阶段规划算法和原有方案，虽然在累计早到指标上相对以往算法有所恶化，但未迟到服务率仍然很高，且在时间窗约束中累计早到时间增加并不会影响新老顾客的满意度.另外由于两阶段规划算法未考虑交通拥堵情况，使得初始配送方案中17号顾客被安排在最后配送，而IACO算法则是在考虑了交通拥堵的情况下，将17号顾客安排为第2个配送区域中第1个配送顾客并及时完成配送，所以要比两阶段规划算法多配送一名顾客.

表4 方案指标结果对比Tab.4 Results comparison of program indicators

4 结 语

本文讨论了带时间窗的动态车辆路径问题，建立了一种更符合配送中心与顾客实际的双目标优化模型，并设计了一种求解新算法.与文献［10］中算法的比较结果表明：本文算法在计算效率、寻优能力和求解结果的稳定性等方面具有良好的性能.另外，本文对DVRPTW的研究更多地考虑了客户的不确定因素，求解算法也只是针对传统蚁群算法的不足进行了改进.而现实世界的复杂性促使实际的车辆路径问题衍生出了更多类型，如装卸一体化的带取送车辆路径优化问题、不确定因素条件下带回程取货的车辆路径问题、基于配送地点变化的物流车辆路径问题等.而对这些不确定环境下的多目标、复杂约束车辆路径问题的建模和高效实用混合智能算法的设计则具有更重要的实际意义和应用价值，这也将是下一步研究的主要方向.