基于禁忌搜索的动态车辆路径问题研究

动态车辆路径问题研究综述作者：韩娟娟李永先来源：《绿色科技》2015年第05期摘要：[HT5”K]指出了动态车辆路径问题是运筹学和组合优化领域的前沿研究方向，研究动态车辆路径问题具有重要的理论和现实意义。

阐述了动态车辆问题（DVRP），根据动态信息的特征将动态车辆路径问题分为随机车辆路径问题（SVRP）和模糊车辆路径问题（FVRP）。

从动态车辆路径问题的建模、算法和仿真优化三个方面分析了其研究成果，对现有研究的不足进行了探讨，提出了动态车辆路径问题的进一步研究方向。

关键词：[HT5”K]动态车辆路径问题；随机VRP；模糊VRP；算法中图分类号：[HT5”SS]F2.24文献标识码：[JY]文章编号：[HT5”SS]1674994.4（2015）05028504[HK]1引言车辆路径问题（Vehicle Routing Problems，VRP）是一类具有重要实用价值的组合优化问题。

VRP是指对安排适当的车辆路径，使车辆在满足约束条件下，经过一系列的发货点和（或）供货点并达到一定的目标。

如果在车辆、时间、人员、顾客需求等信息都确定的情况下安排车辆路径，这类问题属于静态车辆路径问题。

但在现实世界中，信息大多是不确定的，比如顾客需求、交通状况、天气状况、人员、车辆等信息的不确定，有些信息还会处在不断变动的状态，这对安排车辆路径造成了很大的困扰，需要根据不断更新的系统信息动态地安排车辆路径，这类问题属于动态车辆路径问题（DVRP）。

根据动态信息的随机性和模糊性，动态车辆路径问题可以分为随机车辆路径问题和模糊车辆路径问题。

如果可以根据历史资料或市场调查得到信息（顾客需求、车辆行驶时间、服务时间等）的概率分布或信息服从的某种变化规律，路径制定者根据信息的规律及得到的新的系统信息实时地规划车辆路径，这类问题就是随机车辆路径问题。

但是，当需要的信息没有长期积累，不能获得信息的分布规律（如企业开辟新市场时，顾客的需求信息就是模糊的）或者信息不能清晰的被描述，这类问题就是模糊车辆路径问题。

动态车辆路径优化问题作者：屈莎莎郑笑非来源：《环球市场信息导报》2013年第10期现代物流问题的众多研究中，车辆路径问题一直是焦点问题。

车辆路径优化后的配送作业不仅可以降低物流配送企业的物质消耗、节约成本，还可以提高客户的满意度和服务水平，最终提高企业的市场竞争力。

该文在分析客观世界动态需求特征的基础上，对动态车辆路径问题进行分析，并基于时刻表建立动态车辆路径问题优化模型。

1引言随着信息技术的发展，物流已从传统的运输服务发展成为以信息技术和管理为核心的综合物流系统。

据统计，物流成本占产品销售价格的75%左右。

其中，运输成本在整个物流成本中占有相当大的比例。

因此，对物流配送车辆调度进行优化成为企业尤为关注的焦点。

以往对物流配送和车辆调度的研究当中，传统的做法依据静态配送车辆优化调度理论。

但客观世界存在着大量的不确定性，需要一种可以求解动态车辆路径优化问题的方法。

2 动态车辆路径问题的相关理论动态车辆路径问题的提出。

车辆路径问题是物流管理当中最为典型的问题，1959年由Dantzig 和 Ramser[2]提出之后立即引起了很大反响。

理论上讲，车辆路径问题属于组合优化问题，其对应的优化目标是在满足基本约束条件的前提下，使得配送货物的车辆的行驶总里程、使用的配送车辆数量、行驶时间的组合达到最小。

动态车辆路径问题的定义。

静态车辆路径问题中，在对物流配送路径进行优化之前的相关信息（客户、车辆、客户请求、调度及其他相关信息等）是已知且固定的；而动态车辆路径优化问题中的很多信息都是不确定且不可预知的，可能还会有部分信息是模糊的、随机的，在进行路径规划时要根据实时信息对车辆路径进行实时的规划调整和优化。

3 动态车辆路径问题模型动态需求特征分析。

车辆在配送的路程当中存在着大量的不确定性：如拥堵、恶劣天气、车辆故障、客户信息改变等，这都将直接影响配送车辆行驶时间或者速度的变化，导致等待甚至改变路线，进而造成车辆的调度成本的增加。

Vol 18,No 1管 理 工 程 学 报Journal of Industrial Engineering Engineering Management2004年第1期车辆路径问题的禁忌搜索算法研究郎茂祥,胡思继(北京交通大学交通运输学院,北京100044)摘要:论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。

计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。

关键词:车辆路径问题;禁忌搜索算法;优化中图分类号:F502 文献标识码:A 文章编号:1004-6062(2004)01-0081-04收稿日期:2002-06-18 修回日期:2002-12-30作者简介:郎茂祥(1969 ),男(汉),山东高唐人,北京交通大学交通运输学院副教授,博士,主要研究方向为交通运输规划与管理。

0 引言车辆路径问题(VRP,Vehicle Rou ting Problem)是由Dantzig 和Ramser 于1959年提出的[1]。

该问题一直是运筹学与组合优化领域的前沿与热点问题。

在现实生产和生活中,邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。

研究车辆路径问题具有重要的理论和现实意义。

车辆路径问题作为一个NP 难题,随着客户数量的增加,可选的车辆路径方案数量将以指数速度急剧增长。

因此,用启发式算法求解该问题就成为人们研究的一个重要方向。

求解车辆路径问题的方法很多,常用的有旅行商法、动态规划法、节约法、扫描法[2]、分区配送算法[3]、方案评价法等。

禁忌搜索算法的出现,为求解车辆路径问题提供了新的工具。

Gendreau 、Jiefeng 、Barbarosoglu 、蔡延光等都曾利用禁忌搜索算法求解车辆路径问题[4-8],并取得了一些研究成果。

车辆路径规划模型的优化算法研究车辆路径规划是一种重要的优化问题，目的是确定一条最优路径，使车辆在满足各种限制条件下，尽快到达目的地。

随着交通网络的复杂性和车辆数量的增加，车辆路径规划变得更加困难和复杂。

因此，研究车辆路径规划模型的优化算法成为提高交通效率和减少交通拥堵的关键。

1. 研究背景与意义车辆路径规划在现代交通系统中具有广泛的应用价值。

通过优化车辆路径，可以有效减少交通拥堵、降低能源消耗、提高交通效率和交通安全性等方面的问题。

因此，对于车辆路径规划模型的研究具有重要的理论和实际意义。

2. 相关研究现状目前，关于车辆路径规划优化算法的研究已取得了一定的进展。

常见的研究方法包括基于遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法、粒子群优化算法等。

这些算法在不同的场景下都有一定的优势和适用性。

3. 优化算法的原理介绍（1）遗传算法：遗传算法是一种基于生物进化思想的优化算法。

通过模拟自然界的进化过程，通过选择、交叉和变异等操作，形成新的个体并使其逐步优化，最终获得最优解。

（2）模拟退火算法：模拟退火算法是一种基于物理退火原理的启发式优化算法。

它通过随机选取一定数量的解，并通过一定的接受准则来判断是否接受新解，从而逐步优化解的质量。

（3）禁忌搜索算法：禁忌搜索算法是一种基于搜索与回溯的优化算法。

它通过记录和管理已经搜索过的解，并根据一定的禁忌策略来避免陷入局部最优解，从而找到更好的解。

（4）蚁群算法：蚁群算法是一种模拟蚂蚁寻找食物的行为而得到的优化算法。

蚂蚁通过释放信息素来引导其他蚂蚁选择路径，通过间接的信息传递方式来完成路径规划。

（5）粒子群优化算法：粒子群优化算法是一种模拟鸟群搜索食物的行为而得到的优化算法。

通过模拟粒子的飞行和搜索行为，通过个体和社会的信息交流来达到优化目标。

4. 优化算法在车辆路径规划中的应用优化算法可以应用于车辆路径规划的多个方面，例如：（1）路网建模：通过构建适当的路网模型，能够更好地反映实际道路网络的特征。

车辆路径问题：研究综述及展望作者：史春燕黄辉来源：《物流科技》2014年第12期摘要：车辆路径问题是物流系统优化中的关键内容之一，是现代物流管理研究中的重要内容。

文章梳理分析了车辆路径问题（VRP）的分类、模型及算法等，详细综述了多车型、多车场、时间窗车辆路径问题研究现状，指出联盟车辆调度问题、考虑车辆（供应）时间窗的车辆调度问题可能是VRP问题未来新的研究趋势。

关键词：车辆路径；多车型；多车场；时间窗中图分类号：U116.2 文献标识码：A车辆路径问题是运输组织优化中的核心问题，也是运筹学中的一类经典的组合优化问题，旨在借助构造适当的车辆行驶路线以实现运输成本的最优化。

随着市场经济的发展和物流专业化水平的提高，车辆路径问题从提出之初就受到广泛关注。

到目前为止，该问题的应用不仅仅局限在汽车交通运输领域，在航空、通讯、电力、工业管理和计算机应用等领域也有一定的应用。

1 车辆路径问题车辆路径问题来源于交通运输，最早是由Dantzig和Ramser[1]于1959 年发表在《Management Science》上的文章《The Truck Dispatching Problem》中首次研究了亚特兰大炼油厂向各加油站发送汽油的运输路径优化问题，并提出了基于线性规划的求解过程。

在随后的几十年里，VRP问题得到不断的扩充和发展。

1.1 分类自车辆路径问题被提出后，Linus（1981），Bodin和Golden（1981），Assad（1988），Desrochers（1990）等许多学者从不同视角，按不同标准对该问题进行了分类[2]，例如：按车辆类型分，可分为单车型问题和多车型问题；按配送中心（车场）数目分，可分为单配送中心（车场）问题和多配送中心（车场）问题；按任务特征分，可分为纯送（取）货问题和装卸混合问题；按有无时间约束分，可分为无时间窗问题和有时间窗问题，另外可以按车辆装载情况、按优化目标数、按车辆对车场的所属关系、按已知信息的确定性分等不同分类标准进行分类。

无时限单向配送车辆优化调度问题的禁忌搜索算法无时限单向配送车辆优化调度问题，是指在制定配送路线时不考虑客户对货物送到（或取走）时间要求的纯送货（或纯取货）车辆调度问题。

无时限单向配送车辆优化调度问题可以描述为：从某配送中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足一下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。

一、禁忌搜索算法的原理禁忌搜索算法是解决组合优化问题的一种优化方法。

该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。

在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。

为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。

另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。

二、算法要素的设计1.禁忌对象的确定禁忌对象是指禁忌表中被禁的那些变化元素。

由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。

一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。

根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。

举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。

基于实时信息的取送货动态车辆路径问题研究孙宝凤;史俊妍;杨雪;郑再思【摘要】为适应点对点、实时城市配送对动态响应和快速决策提出的新要求,研究了多种实时信息作用和影响下的取送货动态车辆路径问题.采用将动态问题转化为一系列静态问题的建模方法,建立了基于实时信息的取送货动态车辆路径模型;设计了动态算法框架,运用构造算法获得初始可行解,运用禁忌搜索算法改善初始可行解质量.实验表明,本文的模型和算法能有效解决基于实时信息的取送货动态车辆路径问题,将初始可行解的质量(实时物流配送成本)改善了34％.【期刊名称】《宁波大学学报（理工版）》【年(卷),期】2019(032)003【总页数】8页(P87-94)【关键词】动态车辆路径规划;取送货问题;动态算法;构造型算法;禁忌搜索算法【作者】孙宝凤;史俊妍;杨雪;郑再思【作者单位】吉林大学交通学院,吉林长春 130022;吉林大学交通学院,吉林长春130022;吉林大学交通学院,吉林长春 130022;吉林大学交通学院,吉林长春130022【正文语种】中文【中图分类】U491目前，具有点对点、小批量、多批次特点的实时城市配送快速发展，需求倍增，对物流配送的及时响应和灵活性提出了新的技术要求.考虑取送货的动态路径规划是提升配送服务高效性的技术途径之一，简称DVRP-PD问题[1].目前基于实时信息的取送货动态车辆路径问题的研究比较少.为了满足顾客对物流配送高效的要求，Ferrucci等[2]以惩罚成本最小为首要目标，以车辆运营成本最小化为第二目标，采用了禁忌搜索算法得出调度方案，结果表明：根据动态事件持续调整运输计划提高了调度方案的质量.戈丽娜[1]将取送货问题转化为整数线性规划模型，目标函数是使总运行距离最小化，未考虑车辆在行驶过程中与派遣中心的信息沟通和意外事故的情况.杨茹[3]在取送货动态车辆路径问题的研究上将单初始解的禁忌搜索算法改进为多初始解的禁忌搜索算法，并将局部禁忌表扩展为全局禁忌表，多初始解的禁忌算法可以节约2.52%的成本，但同时也降低了运算效率.Jia 等[4]提出了周期控制和事件驱动的滚动时域方法解决取送货动态车辆路径问题.Marjolein等[5]研究了考虑装卸货成本的取送货旅行商问题.Escuín等[6]针对带时间窗的动态取送货问题提出了系统等待策略.Lin等[7]提出了一定时间范围内的动态问题可以被视作一系列各个时刻的静态问题的研究方法.现有文献为DVRP-PD问题给出了研究框架，即首先将动态问题分解为一系列静态子问题，再逐一研究单一动态信息对决策的影响.然而，新请求增加信息研究较多[4-5]，考察配送过程中全面动态信息对决策的影响分析却较为缺乏.为此，本文研究基于实时信息的DVRPPD 问题，即在新请求逐渐出现、旧请求改变、交通堵塞、配送车辆抛锚这4种动态信息作用下的DVRP-PD 问题.首先界定问题，建立基于实时信息的DVRP-PD 模型；然后，针对模型设计动态求解算法，给出算法步骤；进而对已建立的模型和采用的算法进行试验与分析；最后得到研究结论.1 模型建立1.1 问题描述在实际生活中，同城快递和网络外卖等在配送服务时，每一个请求在下单后录入到配送服务商的系统中，配送人员按照请求信息，先到达取货点进行取货服务，再将取到的货物运送到送货点，由收货人签收.在这一过程中，每个请求有对配送服务时效性的要求，而且这些请求在一天内不断地出现，还存在已下单的请求要求修改配送信息的情况.对于运输服务商，需要考虑交通状况和车辆抛锚的意外事件，在满足请求要求的同时降低配送成本.因此本文研究的基于实时信息的DVRP-PD问题可定义如下：考虑每一个请求的取货点和送货点必须满足前驱后继关系且只被访问一次，同时满足配对关系，即同一请求的取货点和送货点必须由同一辆车访问，且不超过配送车辆的最大配送量和最大行驶距离，考虑违反时间窗限制的附加成本和配送过程中实时变化的信息，目标是使配送总成本最小.除了新请求在调度过程中不断地出现并修改，一些有动态本质的事件也会出现，例如车辆拥堵造成的车辆减速和车辆抛锚等.由于无法提前得到这些动态事件的信息，只能实时处理这些问题.在本文中即使车辆拥堵的持续时间是未知的，顾客的请求也不能由另一辆车辆进行转运.但是，如果发生了车辆抛锚的事件，这辆车上的货物必须在抛锚的位置由另一辆车装载并完成运输.车辆由第三方物流公司提供，每辆车有一名司机，每辆车的装载量、人工费用和以运行距离为基础的行驶成本都相同.对于违反时间窗限制的司机(无论是由于交通拥堵还是车辆抛锚)，将按照超出时间窗的程度给以惩罚.顾客对旧请求的改变要求只要是发生在车辆执行前就可以接受.一辆车一旦从车场被派出，就会不断寻求新的请求让这辆车完成.找不到合适的请求时，车辆就返回车场.车辆运营成本与车辆数量和总行驶距离有关.车辆总是选择两地间的最短路径行驶.由于基于实时信息的DVRP-PD问题的时效性尤其重要，因此，目标函数应为最小化超出时间窗的惩罚成本和车辆运营成本的总和.1.2 符号表示(1)常量：n为客户请求的个数(车场用0表示)；P为请求i∈ { 1，…，n}的取货点，P={ 1，…，n}；D为请求i∈ { 1，…，n}的送货点，D={ n+1，…，2n}；qi为i节点的货物需求量，当 qi＞ 0 时，qi表示取货点的货物需求量；qi+n表示相应送货点的货物需求量，qi+n=- qi；Wp(t)为t时刻网络中所有车辆所在地的集合；为t时刻网络中所有车辆所在地的个数；Wp0(t)为t时刻网络中所有车辆所在地和车场的集合；Wu(t)为 t时刻车辆路径中尚未接受服务的客户请求(尚未接受服务的客户请求取消)和新增加的动态客户请求的集合，Wu(t)⊆P∪D；Wu0(t)为t时刻车辆路径中尚未接受服务的客户请求(尚未接受服务的客户请求取消)、新增加的动态客户请求和车场的集合，Wu(t)⊆N；Wup0(t)为t时刻所有车辆所在地、车辆路径中尚未接受服务的客户请求(尚未接受服务的客户请求取消)、新增加的动态客户请求和物流中心的集合；iT为车辆完成一项请求(从物流中心出发至取货完毕回到物流中心，成为一次取货任务)的最大行驶时间；KP为动态调整前车辆调度计划使用的车辆数；K为可使用的车辆总数；T为车辆完成一次任务(从车场出发至回到车场，称为一次任务)的最大行驶时间；Trk(t)为t时刻车辆k从所在地出发时的已累积行驶时间(若车辆从车场出发，则Trk(t)=0)，r∈Wp0(t)，k∈ { 1，2，…，K}；Q为每辆车的额定车载量；Qik(t)为t时刻车辆k从客户i出发时已累积的载重(若车辆从车场出发，则Qik(t)=0)，k∈{1，2，…，K}；di为请求 i的取货作业时间与送货作业时间，i∈P∪D；tij为车辆由点i行驶到点j的时间，i，j∈P∪D；[ei，li]为客户请求i的服务时间窗，其中 ei为时间窗的开始时间，il为时间窗的结束时间，i∈{1，，}n…；α为晚于时间窗1h的惩罚费用；β为每台车辆的固定使用成本(包括车辆的折旧费、维修费等)；c为单位路径成本.(2)变量：Bi为车辆到达点i的时间，i∈P∪D；wi为车辆在取货点i的等待时间，wi=max{0，Bi-ei}，i∈P；tdi为车辆在点i服务完毕后出发的时间，i∈P时，tdi=Bi+wi+di，i∈D时，tdi=Bi+di；tli为请求i晚于时间窗(接受服务)的时间，tli=max{tdi-li，0}，i∈D；zk为0-1变量，如果生成初始车辆调度计划的车辆k被使用，则 zk=1，否则zk=0，k∈ { 1，2，…，K} ；nx为与动态调整前的车辆调度计划相比，新使用的车辆数，，k∈{1，2，…，K}.(3)决策变量：1.3 模型建立在一个特定时刻t，存在无向图 G(N，A)，其中N={ 0，…，2 n}为节点集合，A 为弧集合.对于每一个请求i∈ {1，…，n}，在取货点 i有起始时间窗限制，当车辆在该时刻之前到达时，车辆必须等待，但不产生惩罚费用；在送货点 +n i有结束时间窗限制，当车辆在该时刻之后到达时，产生惩罚费用.为了加入同一请求，相应取送货节点的顺序有前驱后继的约束和取送货车辆约束.后者是指这一请求的取送货节点必须由同一辆车服务，定义集合S′，任意S⊆S′中，至少有一个请求i的取货点满足i∉S且送货点n+i∈S[8].本文提出基于实时信息的DVRP-PD模型为：目标函数(1)表示 t时刻动态调整后的车辆调度计划的总费用最少，总费用包括车辆总行驶费用、晚于时间窗的惩罚费用和新使用车辆的固定使用成本费用3部分. 约束(2)和(3)表示每一个节点必须得到服务，只能由一辆车完成；约束(4)表示前驱后继约束，表示对于请求i，取货点i必须在相应的送货点n+i之前得到服务，并且这对节点必须由同一辆车服务；约束(5)表示车辆到达路径中相邻 2节点时间之间的关系；约束(6)和(7)表示对t时刻所有车辆所在地的访问是单向的，只能发车，然后回到车场；约束(8)表示配送网络中所使用车辆的数量；约束(9)和(10)表示容量约束；约束(11)表示车辆 k为完成承担的任务量而行驶的距离之和不大于车辆的剩余行驶距离；约束(12)表示决策变量的取值范围；约束(13)表示t时刻调整后动态车辆调度计划新使用的车辆数.2 求解算法2.1 动态算法如图1所示，动态算法或在线算法本质为动态环境中的算法框架.动态算法将问题分割成许多静态子问题，以方便构造型算法和改善型算法求得静态子问题的解.图1中对调度时域子间隔进行求解部分，采用启发式算法进行求解.细分为2个阶段：第1阶段采用构造型算法，求出初始解；第2阶段采用改善型算法(禁忌搜索算法)，改善初始解的质量.图1 动态算法流程2.2 构造初始解初始可行解一般采用构造型算法，可以借鉴解决静态的带时间窗的取送货问题(Pickup and Delivery Problem with Time Windows，PDPTW)的算法，例如贪心插入算法.贪心插入算法从一条空路径开始，随机选择一个未安排的请求插入.对于每一个请求而言，检查现存路径中所有可行的取货点和送货点插入位置.这里可行位置指满足取货点在送货点之前的约束、取货点与相应送货点在同一条路径上的约束、容量约束和时间窗约束.并且，初始化一条新的路径插入该请求.比较所有可行位置，选择适应度函数最小的插入位置.采用此方法将所有未被安排的请求插入到路径中.适应度函数为：采用插入算法取得初始解，步骤如下：步骤1新建一条空路径；步骤2设置LocalMin为无穷大；步骤3从所有未进行规划安排的请求中随机选择一个请求，如果没有需要安排的请求则结束算法；步骤4从所有路径中选择一条路径，如果没有路径则新建一条空路径插入该请求；步骤5从步骤4中选择的路径中取货点的可行插入位置选择一个位置，插入步骤3中请求的取货点，如果没有取货点可行插入位置则跳转至步骤 4；步骤6在步骤5的基础上相应送货点的可行插入位置中选择一个位置，插入步骤3中请求的送货点，如果没有送货点可行插入位置则跳转至步骤 5；步骤 7计算新路径的适应度值 cost，如果小于LocalMin则将cost的值赋给LocalMin，将这条路径赋给 r_best，将这个请求赋给 request_best，将取货点位置赋给 p_position，将送货点位置赋给d_position，跳转至步骤 6；步骤 8将请求 request_best的取货点和送货点分别插入到路径 r_best的p_position位置和d_position位置，如果路径为空路径则直接返回已经完成插入的路径，否则消除步骤 1中的空路径；跳转至步骤3.2.3 改善初始解采用禁忌搜索算法对初始解进行改善.2.3.1 邻域移动采用邻域移动获得候选解.如图2所示，从初始解的一条路径中随机移除一对取货点和送货点，再重新插入到初始解中的一条路径中.图2 邻域移动及禁忌对象2.3.2 禁忌表(1)禁忌对象.禁忌对象为边，如图2所示，转换后的粗线边为禁忌对象.边AB为间接取货边，边DE为间接送货边，边GH为直接取货边，边HE为直接送货边.所有引起这些边发生变化的邻域移动都是禁忌的.(2)禁忌表长度和停止准则.禁忌表长度和停止准则与静态子问题中需要重新规划的请求数量成正比.静态子问题中需要规划的请求数量在求解过程中是动态的，需要在每一次运行禁忌搜索算法前实时确定.(3)选择策略.以候选解集为整个邻域，从中选择一个适应度函数为最小的解，作为下一次迭代的初始解.(4)渴望水平.当邻域中存在一个解的适应度函数值最小，且比此次迭代的初始解的适应度函数值小，则无论这个移动是否是禁忌的，都接受这个解.(5)算法步骤：步骤1取得本次静态子问题中需要插入的请求数量，并设置禁忌表长度和最大迭代次数；步骤2 当迭代次数小于等于最大迭代次数时，求得初始解的适应度函数值global_cost，设置候选解的个数为非禁忌的请求个数，否则结束程序；步骤3 随机选择非禁忌请求，将其移除路径，并记录间接取货边和间接送货边，将移除的非禁忌请求重新插入到初始解中，选择适应度函数值最小的插入位置，并将新路径储存在候选解中，直到没有可以选择的随机非禁忌请求；步骤 4计算候选解的适应度函数值，并按照从小到大的顺序进行排序；步骤 5如果最小的适应度函数值小于global_cost，则直接接受这个候选解，更新禁忌表，否则，接受不受到禁忌且适应度函数值最小的候选解，并更新禁忌表；步骤 6更新非禁忌请求，更新迭代次数，转至步骤2.3 实验及分析为了测试上述模型及算法的有效性，随机生成一组随机点作为实验初始数据，并进行路径规划和动态更新的测试.本文所有程序用 MATLAB编写，实验环境为Intel(R) Core(TM) i7-4790 CPU 3.60GHz.3.1 实验数据以 Li等[9]的数据为基础，数据来源 https：//www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/.为了适应动态请求，每个请求都有一个出现时间.其中，为请求最晚到达时间；a 为紧迫度，取值范围为[0.1，1]，步调为 0.1，a越大，紧迫度越高，规划请求的时间越少，也就是请求刚到便需要分配出去.考虑车辆速度受到交通拥堵的影响，在不同时段和不同位置有所不同，按照规划静态子问题的时间和车辆位置为不同位置的车辆配置不同的车辆速度，即vijT表示在时段T内弧ij的速度.为了清楚地说明本文的算法和模型在处理新请求逐渐出现、旧请求改变、车辆拥堵和车辆抛锚的实时信息时，路径和调度规划的更新，假定有 4个请求，为 i(i=1，2，3，4)，i+和i-分别为取货点和送货点，即(1+，2 +，3+，4+)是取货点集合，(1-，2 -，3-，4-)是送货点集合.车辆的容量为20，起始点和返回点为车场.每一项请求的需求量、每个节点的位置坐标和每个节点的时间窗见表1.表1 实验初始数据节点需求量位置时间窗车场 0 (15 000，15 000)1+1 (17 033，8 186) [8：00，9：00]1--1 (23 245，16 818) [8：00，9：00]2+4 (28 662，11 573) [8：01，9.01]2--4 (21 071，7 432) [8：01，9.01]3+3 (6 819，22 566) [8：02，9.02]3--3 (15 367，17 305) [8：02，9.02]4+5 (21 412，9 298) [8：40，9：40]4--5 (28 644，8 680) [8：40，9：40]3.2 实验结果请求 1，2，3 是在 8：05 时同时规划的，可以视为静态请求，动态请求见表2.表2 动态事件序号时间事件1 8：30 1+的取货时间推迟至 8：50，同时1-推迟至9：50前送货2 8：40 增加请求4，需求量为5，取货点为 4+，送货点为4-3 8：50 由于交通拥挤，车2需要延迟10 min 4 9：05 车 2 抛锚在 8：05 时，请求 1，2，3 和这 3 个请求的具体信息已知.路径规划的结果如图3(a)所示，配送总成本为274.61元.在8：30时，1+的要求取货时间由8：00调整为8：50，即推迟了50min.因此，如果按原计划车辆2不得不在节点1+等待至8：50，这样会使得车辆2无法在9：00 前到达节点1-，无法在 9：02 前到达节点3-，从而产生高额的惩罚费用.通过重新规划路线，得到图 3(b)的路线，通过路线的调整，使得路线上产生的成本和惩罚成本相对降低，为252.37元.在 8：40 时，增加了请求 4，将需求量为 5 的货物由节点4+运送至节点4-.通过更新路线，如图3(c)所示，配送总成本为241.39元.在8：50时，车辆2遇到交通拥堵，到达节点1+和节点1-的时间往后顺延 10 min，如图 3(d)所示，配送总成本为265.39元.在9：05时，车辆2抛锚了，重新规划路线时由车辆1先到达车辆2抛锚地点取货再送到相应的送货点，车辆2由拖车送回车场修理，如图3(e)所示，配送总成本为293.87元.图3 路径规划结果3.3 实验结果分析3.3.1 全调度时域范围内解的质量分析在规模为 53个请求的动态取送货问题中，比较调度时域的每一个间隔中构造解和“构造+禁忌”解的适应度函数的值，即总成本.如图 4所示，纵坐标是调度时域每一个间隔适应度函数的值，横坐标是调度时域的间隔数.由此可见，经过改善的“构造+禁忌搜索”算法的结果总体上优于构造解的结果，解的质量比初始解大约提高了34%.图4 构造解与“构造+禁忌”解的比较3.3.2 不同调度时域间隔下解的质量比较通过图 4可以看出，在整个调度时域过程中，构造解与“构造+禁忌”的解在开始时相差不大，中间相距较大.为了容易分辨，在规划时域开始时，路径数量相对较少，分别取构造解和“构造+禁忌”解在间隔 1，2，4，6 时的路径规划图进行对比，分别如图5～8所示.图中“p”和“d”分别代表取货和送货节点；红色实心圆代表车场，红色空心圆圈代表车辆在间隔间的位置；线条的颜色相同则代表同一辆车，其中虚线代表已经行驶过的路径，实线代表已规划好但还未行驶的路径.间隔3与间隔2、间隔5与间隔6具有相似性，故不做分析.图5 间隔1的解图5和图6分别代表间隔1和间隔2结束时的路径规划，其中(a)代表“构造+禁忌”法得到的路径规划，(b)代表构造算法得到的路径规划.可以看出，在间隔1和间隔2时，2种规划算法并没有区别，二者在间隔1和间隔2的总成本都分别为263.09和1141.8元，运算时间分别为0.03和0.48s.图6 间隔2的解图7 间隔4的解如图7所示，间隔4“构造+禁忌”法的总成本开始优于构造法.“构造+禁忌”法得到的路径规划总成本为1315.9元，运算时间为0.67s；构造算法得到的路径规划总成本为 1346.6元，运算时间为0.16s.“构造+禁忌”法优化了路径的调度顺序，且运算时间不超过1s.图8亦呈现出同样特征.图8 间隔6的解4 结论本文采用已有的动态取送货问题的研究框架，即将动态问题分解为一系列静态子问题，综合考虑了新需求出现、需求改变、交通堵塞和配送车辆抛锚4种动态信息，并建立了基于实时信息的取送货问题的模型；将已有的静态数据改编为适用于动态问题的数据，采用动态算法进行求解，并进行结果分析，得出的主要结论如下：(1)本文的模型和算法能够有效地解决基于实时信息的取送货动态车辆路径问题.设计了动态算法框架，将构造算法与禁忌搜索算法相结合，运用构造算法获得初始可行解，运用禁忌搜索算法改善了初始可行解的质量，改善幅度约为34%.(2)算例中动态请求规模为 53，模型及其算法适用于点对点、小批量、多批次的实时配送，可以降低现实中实时配送的成本，并改善配送服务的质量.(3)全调度时域范围为1～31个间隔，算例表明，“构造+禁忌搜索”算法总成本曲线低于构造法总成本曲线，因此经过改善的“构造+禁忌搜索”算法解的质量总体上优于构造解的结果，且每次运行的计算时间不超过1s.(4)不同调度时域间隔下，解(总成本)的质量是变化的.其中，当未处理节点数较少时，如间隔 1和2情形，解是相同的，体现不出2种规划算法的差异.当节点数增多时，如间隔3至6，乃至31情形时，2种规划算法的区别较大.禁忌搜索算法优化路径中节点的调度顺序，从而改善了解的质量.参考文献：【相关文献】[1]戈丽娜.配送过程中提货送货问题的静态动态方法的应用效果研究[D].哈尔滨：哈尔滨工业大学，2016.[2]Ferrucci F，Bock S.Real-time control of express pickup and delivery processes in a dynamic environment[J].Transportation Research Part B：Methodological，2014，63：1-14.[3]杨茹.集送货一体化的动态车辆调度问题研究[D].天津：南开大学，2007.[4]Jia Y J，Wang C J，Wang L M.A rolling horizon procedure for dynamic pickup and delivery problem with time windows[C].IEEE International Conference on Automation and Logistics，Shenyang，2009：2087-2091.[5]Marjolein V，Kees J R，Iris F V，et al.The pickup and delivery traveling salesman problem with handling costs[J].European Journal of Operational Research，2017，257(10)：118-132.[6]Escuín D，Larrodé E，Millán C.A cooperative waiting strategy based on elliptical areas for the dynamic pickup and delivery problem with time windows[J].Journal of Advanced Transportation，2016，50(8)：1577-1597.[7]Lin C H，Choy K L，Ho G T S，et al.A decision support system for optimizing dynamic courier routing operations[J].Expert Systems with Applications，2014，41(15)：6917-6933.[8]Ropke S，Cordeau J，Laporte G.Models and branchand-cut algorithms for pickup and delivery problems with time windows[J].Networks，2007，49(4)：258-272.[9]Li H，Lim A.A metaheuristic for the pickup and delivery problem with timewindows[C].IEEE International Conference on Tools with Artificial Intelligence，2001：160-167.。