控制与决策  2019, Vol. 34 Issue (6): 1195-1202  
0

引用本文 [复制中英文]

葛显龙, 薛桂琴. 基于场景动态度的两级配送路径问题[J]. 控制与决策, 2019, 34(6): 1195-1202.
[复制中文]
GE Xian-long, XUE Gui-qin. Two-echelon distribution routing problem based on scenes dynamic degree[J]. Control and Decision, 2019, 34(6): 1195-1202. DOI: 10.13195/j.kzyjc.2017.1532.
[复制英文]

基金项目

国家自然科学(71502021, 71602015);教育部人文社会科学(14YJC630038, 15XJC630007);博士后科学基金特别项目(2016T90862);重庆市基础与前沿研究项目(cstc2016jcyjA0160);重庆市教委人文社会科学研究项目(17SKG073);重庆市科学技术研究项目(KJ1500702)

作者简介

葛显龙(1984-), 男, 教授, 博士, 从事路径优化及其应用等研究, E-mail:gexianlong@cqjtu.edu.cn;
薛桂琴(1992-), 女, 硕士生, 从事城市物流配送的研究, E-mail:xuegqmail@126.com

通讯作者

葛显龙, E-mail: gexianlong@cqjtu.edu.cn

文章历史

收稿日期:2017-11-13
修回日期:2018-04-15
基于场景动态度的两级配送路径问题
葛显龙 1,2, 薛桂琴 1     
1. 重庆交通大学 经济与管理学院,重庆 400074;
2. 重庆交通大学 智能物流网络重庆市重点实验室,重庆 400074
摘要:针对城市配送过程中出现的交通限行和需求不确定性等问题, 将配送周期划分为初始配送阶段和动态补货阶段, 路径中包含枢纽型物流中心、配送型物流中心和客户, 研究其共同构成的两级车辆配送路径优化问题.考虑到问题的动态性, 提出前摄性需求配额策略及响应性补货策略, 构建基于场景动态度的两级动态车辆路径问题数学模型.设计融合扫描算子的禁忌搜索算法, 完成车辆初始阶段的配送路径优化; 根据场景动态度, 设计修复/更新性动态客户的响应策略, 快速响应动态需求.最后, 通过仿真算例验证模型和算法的有效性, 实验结果表明, 所提出的设计策略能够有效降低动态客户对低动态度应用场景初始路径的干扰, 并简化高动态度场景下的路径优化复杂度.
关键词动态车辆路径问题    前摄性调度    禁忌搜索算法    交通限行    需求不确定性    动态度    
Two-echelon distribution routing problem based on scenes dynamic degree
GE Xian-long 1,2, XUE Gui-qin 1     
1. School of Economics and Management, Chongqing Jiaotong University, Chongqing 400074, China;
2. Key Laboratory of Intelligent Logistics Network, Chongqing Jiaotong University, Chongqing 400074, China
Abstract: Aiming at the problems such as traffic limitation and demand uncertainty in the process of city distribution, this paper divides the distribution process into initial stage and dynamic replenishment stage, and studies the optimization of the two-echelon dynamic vehicle routing of the hub logistics center, the distribution logistics center and customers. Taking into account the dynamic events, this paper proposes a proactive demand quota strategy and a responsive replenishment strategy, and establishes the mathematical model of the two-echelon dynamic vehicle routing problem in dynamic circumstance. A tabu search algorithm based on a fusion scan operator is designed to optimize the delivery route in the initial stage. Meanwhile, according to the scene dynamic degree, this paper raises a repair/update dynamic customer response strategy to respond quickly to the dynamic demand. Finally, a simulation example is given to illustrate, the effectiveness of the proposed model and algorithm. The experimental results demonstrate that the proposed scheduling strategy can effectively reduce the dynamic client interference on the initial path of low-dynamism scenario and simplify the path optimization complexity of high-dynamism scenarios.
Keywords: dynamic vehicle routing problem    proactive scheduling    tabu search algorithm    traffic restriction    demand uncertainty    dynamic degree    
0 引言

车辆路径问题是目前研究最广泛、最深入的组合优化问题之一.近年来, 随着电子商务的飞速发展, 消费者的消费习惯发生了明显的变化, 需求动态化趋势日趋明显, 使得求解车辆路径问题(Vehicle routing problem, VRP)变得越来越复杂.传统的车辆路径问题仅考虑配送中心与客户之间的路径优化问题, 但是在多批次小批量的配送场景下, 物流企业纷纷在客户较为集中的区域设置配送型物流中心, 以响应快速变化的客户需求, 实现客户需求的快速配送[1-2].此外, 国内各大城市纷纷推出交通限行相关规定, 使得在不同道路等级上可行驶的车辆类型受到限制, 因此目前在城市配送中, 往往使用核定运力较大的车型将货物运输到郊区, 再换由核定运力较小的车型运往市内, 满足市民日常生活所需.这就催生了许多关于两级动态车辆路径问题(Two-echelon dynamic vehicle routing problem, 2E-DVRP)的研究[3-4].

两级动态车辆路径问题是指在客户需求存在不确定性的配送环境下, 将整个配送网络划分为两个配送等级.第一等级的配送网络包含枢纽型物流中心和配送型物流中心, 负责将客户需要的货物运输到位于客户附近的配送型物流中心; 第二等级的配送网络包含配送型物流中心和客户, 负责末端客户的最后一公里配送.文献[5]将两级车辆路径问题与随机需求量车辆路径问题相结合; 文献[6]以配送中心选址成本和车辆路径成本为目标, 构建配送中心选址-路径优化的双层规划模型; 文献[7-9]构建了有能力约束的定位-路径问题的数学模型; 文献[10]研究了动态不确定情况下的应急定位-路径问题, 建立了模糊机会随机规划模型.针对2E-VRP的求解, 现有算法主要分为两大类: 1)精确求解算法, 如分支定价算法[11]、分支切割算法[12]等; 2)近似求解算法, 如遗传算法[13]、模拟退火算法[14]、禁忌搜索算法[15-20]等.上述文献从不同角度对2E-VRP问题的模型构建和求解算法进行了深入的研究, 但并未根据动态车辆路径的动态特性对配送周期内动态客户需求量进行评估, 并将评估结果反映到两级配送网络中.此外, 场景动态度与车辆调度复杂度息息相关, 场景动态度愈高, 配送路径优化的难度愈大, 然而现有文献较少涉及针对不同动态等级应用场景的差异化处理问题.

基于此, 本文在动态两级车辆路径问题的相关研究成果的基础上, 设计前摄性需求配额策略和响应性补货策略, 结合场景动态度构建多阶段两级动态车辆路径问题的数学模型及其求解算法, 并设计仿真算例验证模型和算法的有效性.

1 问题描述

本文研究的问题包含两级配送网络:一级配送网络是配送车辆从枢纽型物流中心为配送型物流中心服务; 二级配送网络是配送车辆从配送型物流中心出发为客户服务.问题满足如下假设:

1) 假定使用无向图G=(N, A)表示配送网络. A=AFAS表示弧段集合, 由两部分构成: AF表示枢纽物流中心和配送物流中心的弧段集合, AS表示配送型物流中心及其服务客户之间的弧段集合. N=N0NFNS表示节点集合, 其由3部分组成: N0表示枢纽型物流中心, NF表示一级配送网络中的配送型物流中心, NS表示二级配送网络中的客户.

2) 考虑交通通行情况, 不允许跨级配送, 即禁止直接由枢纽型配送网络向用户提供配送服务.两级配送网络使用不同的车型:假定一级配送网络使用的车型为V1, 其核定运力为Q1, 规定任意配送型物流中心单次配送量不超过车辆核定运力; 二级配送网络使用车型为V2, 其核定运力为Q2, 规定任意客户单次配送量不大于车辆核定运力.

3) 假定一级配送网络的需求可拆分, 即在整个配送周期内, 一个配送型物流中心的需求量可由初始配送和补货阶段按照不同额度比例配给, 且要求每个配送阶段车辆只能访问任意配送型物流中心一次.不同阶段的需求配给额度由设计的前摄性配额准则决定.

4) 在二级配送网络中, 客户分为静态客户和动态客户两大类.静态客户是指配送周期开始时就出现在二级配送网络中, 动态客户是指在配送过程中出现在二级配送网络中的新增客户, 分别记为NSsNSd.由于动态客户的产生具有一定的随机性, 将整个配送周期划分成多个配送阶段, 将动态配送网络优化问题转化为静态配送网络优化问题, 构建响应性调度方法, 完成二级配送网络内客户需求配送.

在上述假设的基础上, 使用前摄性/响应性调度策略, 构建由枢纽型配送中心、配送型物流中心和客户三级节点组成的多阶段两级配送服务体系, 如图 1图 2所示.

图 1 初始阶段两级配送网络路径
图 2 补货阶段两级配送网络路径

图 1为第一阶段两级配送路径设计示意图.其中:五角星代表枢纽型物流中心, 负责各配送型物流中心配送中转货物.空心圆表示配送型物流中心, 负责为客户提供配送服务.在配送的初始阶段, 车辆1的送货路线为C1-D4-D5-D6-C2, 车辆2的送货路线为C2-D3-D2-D1-C1, 并为二级配送网络各配送子区域设计最优配送路径.

假定T时刻, 二级配送网络中出现部分新增客户.配送型物流中心D1D3D4D6覆盖区域出现动态客户, 而D2D5服务区域未出现动态客户, 因此在该补货阶段关闭配送型物流中心D2D5, 仅为需要补货的4个配送中心进行配送路径再优化.如图 2所示, 再优化后一级配送网络的补货路径为C2-D6-D2-C2C1-D1-D4-C1, 补货完成后需根据新增动态客户的需求量变化情况, 更新二级配送网络.

2 模型构建 2.1 前摄性需求配额准则

由于配送型物流中心覆盖的服务区域相对较为稳定, 一级配送路径优化的关键在于评估该区域内的需求量.城市配送企业的长期配送, 为其积累了丰富的历史配送数据, 其为各配送子区域需求量评估提供了依据.现假定某一配送型物流中心的历史需求量均值和方差分别为μiσi, 在配送过程中, 为确保一级配送路线设计的稳定性, 基于历史需求量标准差计算每个配送子区域需要补货的概率

(1)

其中: σi为第i个配送型物流中心的历史需求量方差, σmaxσmin分别为评估时间区间内最大和最小历史需求量方差值.

由式(1)可知, pi越大, 子区域内需求量变动越大, 需要补货的概率也越大.

在配送过程中, 子区域新增需求导致初始配送计划的供给量小于子区域实际需求量, 需要辅以补货路径设计以实现全区域客户需求覆盖.因此, 设定的补货概率阈值为Paccept, 确定配送型物流中心i是否为补货子区域, 具体为

(2)

确定某一配送型物流中心覆盖子区域是否为补货子区域后, 考虑到各自区域内的需求不确定程度的差异及其距离配送中心远近, 设计基于历史需求量配置初始路径计划各子区域的需求配额方法, 即

(3)

其中rand(a, b)表示区间[a, b]之间的随机数.

前摄性调度策略对非补货子区域提供高于其历史平均水平的供给量, 补货子区域仅提供其历史均值水平供给量, 确保初始调度计划的稳健性.考虑到动态需求及判定的补货概率, 在满足一级配送网络服务能力的前提下, 允许初始阶段对客户的实际供给配额超过该配送型物流中心在单个阶段的服务能力, 以确保非补货子区域对动态客户具有一定的适应能力.补货子区域对动态客户的适应能力主要依靠补货策略.

2.2 响应性补货策略

传统动态车辆路径问题中, 一般采用动态客户占所有客户的百分比计算待求解问题的动态度, 如下式:

(4)

由于问题的动态度对补货策略制定至关重要, 需设计基于所求问题动态度的补货策略, 以增强系统的稳定性.本文制定以下两种补货策略:策略一为更新策略:如果问题的动态度较低, 对原始方案实行适度修复即可消除动态事件的干扰, 则优先对原始方案进行修复或适度改编; 策略二为修复策略:如果问题的动态度较高, 则放弃使用修复性响应策略, 即尝试将动态客户插入原有解决方案中, 以实现动态事件对原始解决方案执行的干扰度最小, 此时, 将动态问题转化为静态问题, 分阶段求解.设定补货缓冲时间, 随着配送过程推进, 截止t时刻各配送型物流中心的新增动态客户需求量为qit, 启动补货阶段.考虑到路径优化的耗时情况, 设置补货缓冲时间, 将截至至补货缓冲时刻产生的动态客户及静态客户, 归并到补货阶段予以服务.

2.3 数学建模

模型中用到的其他记号如下:

xv1ij:一级配送网络中, 如果车辆v1服务完配送型物流中心i后直接行驶到配送型物流中心j为其服务, 则取1, 否则取0;

xv2ij:二级配送网络中, 如果车辆1服务完客户i后为客户j服务, 则取1, 否则取0;

yv1it:一级配送网络中, 如果配送型物流中心i在配送阶段t由车辆v1补货, 则取1, 否则取0;

yv2it:二级配送网络中, 如果客户i在配送阶段t由车辆v2服务, 则取1, 否则取0;

Θ(x):若x为正数, 则取1, 否则取0;

T:一个配送周期划分的阶段数;

dfij:一级配送网络中, 节点i到节点j的距离;

dsij:二级配送网络中, 节点i到节点j的距离;

NSf:第f个配送型物流中心覆盖的客户数;

NSfs:第f个配送型物流中心覆盖的静态客户;

Nf:第f个配送型物流中心;

Qv2i:车辆v2从客户i出发时已累积载货量;

yf:配送型物流中心f的配送能力;

y0:枢纽型配送中心的配送能力.

以两级配送网络配送总路径最短为目标函数,构建前摄性/响应性多阶段两级配送网络优化模型如下:

目标函数

(5)

约束条件

(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)

其中:式(5)表示目标函数, 由3部分组成, 第1项为初始阶段的路径长度, 第2项为补货阶段一级配送网络的路径长度, 第3项为各阶段二级配送网络的路径长度; 式(6)表示一级配送网络流量均衡约束; 式(7)表示二级配送网络流量均衡约束; 式(8)表示从枢纽型物流中心出发的车辆必须返回到枢纽型物流中心; 式(9)表示配送型物流中心配送的车辆不超载; 式(10)表示为客户配送的车辆不超载; 式(11)表示二级配送网络中车辆剩余运力不小于下一个待配送客户的需求量; 式(12)表示各阶段需求量不超过枢纽型物流中心的配送能力; 式(13)表示任意配送型物流中心覆盖客户的各阶段需求量不超过其配送能力; 式(14)表示整个配送周期内, 各配送型物流中心被访问次数不大于划分阶段数; 式(15)表示一级配送网络使用的车辆不能直接访问客户; 式(16)表示所有客户仅被访问一次; 式(17)表示不允许二级配送网络中的车辆回到枢纽型物流中心; 式(18)~(22)表示各二进制变量取值约束.

3 算法设计

考虑动态需求响应, 使用动态度判定问题属于修复性问题还是更新性问题, 进而设计禁忌搜索算法和节约算法.如果由场景动态度确定的补货策略为更新策略, 则使用禁忌搜索算法进行路径优化; 如果由场景动态度确定的补货策略为修复策略, 则先使用禁忌搜索算法得到初始最优路径, 再使用并行节约法将动态事件插入到初始最优路径中.

3.1 禁忌搜索算法路径优化

1) 扫描算子.

由于禁忌搜索算法对初始解的依赖较大, 使用扫描法的初始解, 并采用禁忌搜索算法对初始解进行再优化, 以获取更高性能的解决方案.扫描算子构造初始解的具体步骤为:首先以配送中心为原点, 任一客户点为终点构建极坐标系下的起始向量; 以配送中心为起点, 客户为终点构成向量, 计算该向量与起始向量的夹角; 对向量夹角进行排序, 并结合路径约束条件生成初始客户序列.

2) 邻域解构造.

算法禁忌搜索过程中, 对当前解决方案进行邻域变换, 拓展可搜索到的解空间范围, 从而增加算法的寻优能力.本文定义以下4种邻域优化算子: T1:随机选择的客户从车辆中移除并重新随机插入; T2:随机交换两个随机选择的客户; T3:随机选择两个子路线段互相交换; T4:随机选择两个客户, 将位于这两个客户之间的所有客户逆序.对每次邻域操作, 采用以下两种接受策略.策略A:首次改进, 即在邻域变换后获得的第一次改进后停止本次优化; 策略B:最佳改进, 将同一算子重复运行N次, 选择试验中出现的最佳改进.如果运行N次运算后, 当前解仍未改善, 则终止本次邻域操作.对于每条路径及路径上的每个客户, 以均匀概率(分别为1/4和1/2)随机并独立地选择5种局部优化算子和两种接受策略中的一个组合, 所有操作的搜索深度均为N次.

3) 禁忌对象与禁忌表构造.

为避免算法陷入局部最优, 需判断邻域解是否优于历史最优解.如果邻域解优于历史最优解, 则更新历史最优解, 并将该邻域解视为禁忌对象.判断禁忌表是否被充满:如果禁忌表已满, 则移除禁忌表的第一个元素后, 将其他元素左移一位, 将禁忌对象插入到禁忌表的尾部; 如果禁忌表未满, 则直接将禁忌对象插入到第一个不为0的位置.如果邻域解劣于历史最优解, 则将搜索深度加1, 继续判断下一个邻域解是否满足禁忌条件.

4) 解的质量评价.

评价解的质量主要考虑目标函数值和车辆是否超载两个层面.如果生成路径不满足车辆核载要求, 则视为不可行解, 直接从解空间中移除.

3.2 节约法路径修复

节约法是通过计算待插入节点与已有节点的距离节约值, 选取距离最大的节约点位置, 将待插入节点插入到路径中.具体实现步骤如下.

Step 1:判断当前系统是否接受动态客户插入, 接受则转向Step 2, 否则转向Step 5;

Step 2:计算动态客户与系统中已有客户之间的距离, 并计算其路径节约值, 转向Step 3;

Step 3:取路径节约值最大的节点之间插入该动态客户, 转向Step 4;

Step 4:判断是否还存在待插入动态客户, 是则转向Step 1, 否则转向Step 5;

Step 5:结束.

依据场景动态度设计的配送网络路径优化算法流程如图 3所示.

图 3 基于场景动态度的路径优化算法流程
4 仿真算例 4.1 数据准备

以重庆市轻轨3号线、轻轨6号线和轻轨1号线包围的闭环区域为整个服务区域, 建立两级配送网络.以小什字、红旗河沟两个轻轨换乘站为枢纽型配送中心, 配送型物流中心选择分布在3条线路上的5个轻轨站:分别为3号线上的观音桥、两路口轻轨站, 1号线上的七星冈轻轨站以及6号线上的江北城、红土地轻轨站.客户为随机选取的分布在配送型物流中心周围的居民小区和便利店.此外, 配送型物流中心两路口和较场口、枢纽型物流中心小什字在长江以南, 其余配送型物流中心和枢纽型物流中心均为长江以北.将上述数据映射到100×100的坐标系中, 得到的坐标系如图 4所示.图 4中:星表示枢纽型物流中心, 圆点表示配送型物流中心, 十字表示客户.

图 4 两级配送网络节点分布

考虑到交通限行因素, 在一级配送网络使用核载8吨的东风厢式货车(以下简称D8A和D8B), 车辆数目为两辆; 二级配送网络使用核载两吨的东风厢式货车(以下简称D21D22D23D24D25), 每个配送型物流中心拥有的车辆数目为1辆.为便于仿真, 假定每个子区域的需求量均值由2.0~3.0的均匀分布生成, 方差由0.2~0.4的均匀分布生成.在每个配送子区域内部, 所有静态客户与动态客户需求量相等, 均为0.15.采用文献[21]提出的动态客户产生方式, 具体模式如图 5所示, 即所有客户均在配送周期的前半段产生. 图 5中实线标记不代表具体动态客户数目及时间点, 仅表述动态客户产生遵循的时间模式.补货阶段在T/2时刻启动, 所有动态客户均在在T/2时刻之前产生.

图 5 动态客户产生模式

根据上述参数设置, 生成的某周期各配送子区域需求情况如表 1所示.

表 1 各配送子区域需求量分布

假定补货概率阈值为0.5, 则由式(2)可确定5个配送型物流中心的初始阶段需求配额, 如表 2所示.

表 2 各配送型物流中心初始阶段配给额度
4.2 前摄性/反应性路径优化方案

1) 初始阶段路径优化.

根据4.1节部分介绍的相关参数, 只考虑静态客户设计该周期初始阶段的路径.对于一级配送网络, 车辆D8A从红旗河沟出发, 为观音桥、两路口、较场口3个配送型物流中心送货; 车辆D8B从小什字出发, 为江北城和红土地两个配送型物流中心送货, 送货量如表 2所示.由于长江阻隔, 从两路口到江北城之间必须绕道穿越长江, 而观音桥至两路口可直线通达, 因此两路口至江北城的实际行驶距离大于观音桥至江北城的实际行驶距离.送货完毕后, 二级配送型物流中心开始为其覆盖区域的客户进行配送.采用量子遗传算法求解的二级配送网络初始最优路径如图 6所示.

图 6 初始阶段路径

对比表 2图 4可知, 服务初始阶段完成后, 每个配送型物流中心均保持一定存量的配送能力.其中:两个非补货子区域剩余存量分别为江北城1.2吨、两路口1.45吨.由于初始配额设定的原因, 补货子区域的剩余存量相对较少, 分别为观音桥0.66吨、较场口0.56吨、红土地0.54吨.显然, 若不考虑补货, 则非补货子区域对动态客户的适应能力更强, 这更验证了本文设计的初衷:在初始阶段赋予动态度相对较低的配送子区域较高的动态客户需求适应能力, 而动态度较高的配送子区域则通过补货策略实现对动态客户的响应.

2) 补货阶段路径优化.

本文将非补货子区域视为低动态度应用场景, 使用修复性策略进行求解; 而将补货子区域视为高动态度应用场景, 采用更新性策略进行求解.假定补货子区域动态度为50 %, 非补货子区域动态度为30 %, 由式(4)生成T时刻各配送子区域内新增动态客户数目, 如表 3所示.

表 3 补货阶段各配送子区域需求变动情况

表 3数据选取的48个新增动态客户分布情况如图 7所示.在图 7中:星表示枢纽物流中心, 空心圆表示配送型物流中心, 实心点表示新增动态客户.此时一级配送网络的补货路线:车辆D8B的补货路线为红旗河沟-观音桥-红土地-红旗河沟; 车辆D8B的补货路线为小什字-较场口-小什字.二级配送网络路径如图 8所示.

图 7 新增动态客户位置分布
图 8 补货阶段配送网络最优路径

图 8中, 由于新增动态客户导致两个非补货子区域内需求总量超过车辆单次配送能力, 因此结合T时刻的动态客户情况, 对两个非补货子区域的路径进行拆分, 选取距离配送中心最近节点返回配送型物流中心, 如图 9所示.对于3个补货子区域, 由于场景动态度较高, 且动态需求出现时间及位置随机, 频繁变更路线会增加路径复杂度, 且增加司机工作量.因此, 不破坏初始阶段配送路径, 在一级网络完成各中心补货后, 单独为动态客户规划路径.

图 9 非补货子区域初始及补货阶段路径分割
4.3 新旧方案对比

1) 方案调度成本分析.

由于本文涉及配送型物流中心数目较少, 一级配送网络路径优化较为简单.两个配送阶段的路径成本及车辆实载率见表 4.

表 4 一级配送网络配送路径及车辆实载率对比

由此可知, 一级配送网络路径长度与配送型物流中心数量及其空间分布直接相关.在整个配送子区域内, 两辆车的工作量大致相当.同时不可忽视的是, 补货阶段的车辆实载率均低于40 %, 存在一定程度的配送能力浪费.因此, 在实际的应用场景下, 可以考虑使用多种车型搭配以避免在各配送阶段需求出现不均时, 车辆实载率较低的情形.由于动态度约束, 二级配送网络的补货子区域车辆实载率在两个配送阶段保持一致.在非补货子区域, 配送过程中动态客户的出现导致区域需求总额大于单车核载, 故对配送路径进行拆分, 使得第2阶段的实载率明显下降.同时, 前摄性需求配额策略增强了非补货子区域对动态客户的响应能力, 对一级配送网络路径成本的降低具有积极意义.

2) 原始方案调度成本分析.

由于交通限行约束, 原始方案仅使用两吨的东风厢式货车, 车辆调度思路为:在配送开始时刻, 依据车辆载重为静态客户设计最优配送路径; 在T/2时刻, 重新调度新的车辆为动态客户服务.由于长江阻隔, 原始方案中小什字中心负责长江南侧区域及江北城区域, 红旗河沟中心负责长江北侧区域.由此得到的路径成本如表 5所示.

表 5 原始调度方案路径成本分析

对比表 4表 5可知, 本文设计的前摄性/反应性调度方案路径成本为1 123.04, 原始调度方案路径成本为1 182.66.就调度成本而言, 本文方法略优于原始调度方案; 但本文方法在补货阶段, 车辆从配送型物流中心出发, 更接近客户群位置, 客户响应更加及时.

4.4 算法性能测试

为测试本文禁忌搜索算法的寻优能力, 分别使用本文算法及遗传算法对网站http://www.bernabe.dorronsoro.es/vrp/index.html?/results/BestResults.htm提供的基准算例集运行50次, 结果见表 6.

表 6 本文算法、遗传算法与已知最优解对比

表 6可知, 本文设计的禁忌搜索算法在寻优能力上优于遗传算法, 与已知最优解的偏差均在8 %以内, 且当问题规模扩大时, 所设计的禁忌搜索算法仍有较好的寻优表现, 表明本文算法能够较好地满足车辆路径优化的需要.

5 结论

本文考虑交通通行约束, 建立两级城市内物流配送网络, 并设计前摄性/响应性调度策略, 模拟两种动态度下的配送路径优化.得出以下结论: 1)针对不同动态度应用场景, 前摄性调度策略可以增强低动态场景原始方案的可拓展性, 并对补货成本的降低具有积极作用. 2)基于场景动态度的响应性补货策略, 可显著降低动态问题的求解复杂度.此外, 研究中还发现, 各配送子区域的补货量对一级配送网络补货阶段的车辆实载率影响较大, 存在一定程度的调度资源浪费, 下一步将考虑在一级配送网络中引入多车型选择策略, 实现资源的科学合理调度.

参考文献
[1]
麻存瑞, 柏赟, 赵欣苗. 快递配送车辆路径优化研究[J]. 交通运输系统工程与信息, 2017, 17(4): 182-187.
(Ma C R, Bai Y, Zhao X M. Vehicle routing optimization on express distribution[J]. J of Transportation Systems Engineering and Information Technology, 2017, 17(4): 182-187.)
[2]
叶威惠, 张飞舟. 真实路况下的快递配送路径优化研究[J]. 计算机工程与科学, 2017, 39(8): 1530-1537.
(Ye W H, Zhang F Z. Express distribution route optimization under real-time road condition[J]. Computer Engineering and Science, 2017, 39(8): 1530-1537. DOI:10.3969/j.issn.1007-130X.2017.08.023)
[3]
Nagy G, Salhi S. Location-routing: Issues, models and methods[J]. European J of Operational Research, 2007, 177(2): 649-672.
[4]
Rahmani Y, Cherifkhettaf W R, Oulamara A. The two-echelon multi-products location-routing problem with pickup and delivery: Formulation and heuristic approaches[J]. Int J of Production Research, 2014, 54(4): 1-21.
[5]
Liu R, Tao Y, Hu Q, et al. Simulation-based optimisation approach for the stochastic two-echelonlogistics problem[J]. Int J of Production Research, 2017, 55(1): 1-15. DOI:10.1080/00207543.2016.1261649
[6]
王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.
(Wang D P, Xu Z, Yang C. Study on location-routing problem of logistics distribution based on two-stage heuristic algorithm[J]. Operations Research and Management Science, 2017, 26(4): 70-75.)
[7]
Escobar J W, Linfati R, Baldoquin M G, et al. A granular variable tabu neighborhood search for the capacitated location-routing problem[J]. Transportation Research Part B, 2014, 67(9): 344-356.
[8]
Jepsen M, Spoorendonk S, Ropke S. A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem[J]. Transportation Science, 2013, 47(9): 23-37.
[9]
Feliu J G, Perboli G, Tadei R, et al. The two-echelon capacitated vehicle routing problem[J]. Working Papers, 2008, 45(3): 364-380.
[10]
孙华丽, 王循庆, 薛耀锋. 应急定位一路径的模糊机会约束规划模型[J]. 统计与决策, 2012(7): 45-48.
(Sun H L, Wang X Q, Xue Y F. Fuzzy chance constrained programming model for emergency location and one path[J]. Statistics & Decision, 2012(7): 45-48.)
[11]
Adulyasak Y, Cordeau J F, Jans R. Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems[J]. Informs J on Computing, 2014, 26(1): 103-120. DOI:10.1287/ijoc.2013.0550
[12]
Yuan B, Liu R, Jiang Z. A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements[J]. Int J of Production Research, 2015, 53(24): 7450-7464.
[13]
Janne Huiskonen. Service parts management: Demand forecasting and inventory control[J]. Production Planning & Control, 2011, 25(6): 489-494.
[14]
穆东, 王超, 王胜春. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015, 21(6): 1626-1636.
(Mu D, Wang C, Wang S C. Solving TDVRP based on parallel-simulated annealing algorithm[J]. Computer Integrated Manufacturing Systems, 2015, 21(6): 1626-1636.)
[15]
Cordeau J, Gendreau M, Laporte G. A tabu search heuristic for periodic and multi-depot vehicle routing problems[J]. Networks, 2015, 30(2): 105-119.
[16]
王茜, 吉清凯, 胡祥培. 多车型多车槽VRP的混合导引反应式禁忌搜索算法[J]. 管理工程学报, 2016, 30(3): 179-187.
(Wang Q, Ji Q K, Hu X P. A hybrid guided reactive tabu search for heterogeneous fixed fleet multi-compartment vehicle routing problem[J]. J of Industrial Engineering and Engineering Management, 2016, 30(3): 179-187.)
[17]
代颖, 马祖军. 应急物流系统中的随机定位-路径问题[J]. 系统管理学报, 2012, 21(2): 212-217.
(Dai Y, Ma Z J. Stochastic location-routing problem in emergency logistics systems[J]. J of Systems & Management, 2012, 21(2): 212-217. DOI:10.3969/j.issn.1005-2542.2012.02.009)
[18]
李明燏, 梁丽萍, 鲁燕霞. 基于改进禁忌搜索算法的车辆路径问题模型[J]. 公路交通科技, 2017, 34(10): 108-114.
(Li M J, Liang L P, Lu Y X. A model of vehicle routing problem based on improved tabu search algorithm[J]. J of Highway and Transportation Research and Development, 2017, 34(10): 108-114.)
[19]
Alonso F, Alvarez M J, Beasley J E. A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions[J]. J of the Operational Research Society, 2008, 59(7): 963-976.
[20]
Maischberger M. A parallel iterated tabu search heuristic for vehicle routing problems[J]. Computers & Operations Research, 2012, 39(9): 2033-2050.
[21]
Larsen A. The dynamic vehicle routing problem[D]. Kongens Lyngby: Department of Mathematical Modelling, Technical University of Denmark, 2000