基于时间窗的多车场车辆路径问题研究

闫 凯，李爱光，郭 健，陈 冰

（1.信息工程大学， 河南 郑州 450001）

基于时间窗的多车场车辆路径问题研究

闫 凯1，李爱光1，郭 健1，陈 冰1

（1.信息工程大学， 河南 郑州 450001）

启发式优化算法在解决车辆路径问题时具有较好的收敛性，整体法在解决时间窗的多车场车辆路径问题时具有较好的全局性，结合二者优点，进行了算法研究。首先采用整体法得到车辆路径问题的全局最优解；再采用智能优化算法对配送点进行车场选择，匹配代价最小的车场；最后通过实验验证了该算法在解决时间窗的多车场车辆路径问题上的有效性。

智能优化算法；整体法；时间窗；多车场车辆路径

随着现代物流业的发展，车辆路径规划在物流配送领域的作用日趋明显，设计合理的配送方案，提高配送效率，降低配送成本，已成为物流企业竞争的核心。车辆路径问题（VRP）[1]，即在配送区域范围内，所有配送车辆都从配送中心出发，在满足一定的约束条件（如车辆的最大容载量、货物需求量、行驶里程约束、时间限制等）的情况下，选择合适的配送路线来实现特定的目标（如总行驶距离最短、时间最短、使用车辆数目最少、总体费用最低等）。目前，VRP已广泛应用于军事物流配送、快递投放与取件、垃圾回收和牛奶配送等行业。

随着现代商业的发展，许多大型货运公司在区域范围内建立了多个配送中心，因此多车场车辆路径问题就显得非常重要。多车场车辆路径问题（MDVRP）是单车场VRP的一个拓展，VRP属于完全NP问题，因此MDVRP也属于NP问题。解决MDVRP主要有3种方法：传统方式、整体法和启发式优化法[2-4]。传统方法是首先将多车场问题转换为单车场问题，再按照单配送问题进行处理，常用的转化方法有中垂线分区法、圆域分区法和客户聚类法等；整体法主要是通过虚拟配送中心的方式来实现多配送中心问题，首先设置虚拟配送中心，再从虚拟配送中心出发，选择车场后完成配送任务[5]；启发式优化法主要是采用智能优化方法处理多车场问题，常见的优化算法有遗传算法、蚁群算法、模拟退火算法和混合算法等[6]。传统方法求解MDVRP时，在一定程度上降低了问题的复杂性，但失去了问题的整体性；整体法求解时，注重问题的整体性，但忽略了单一车辆的优化；启发式优化算法通过构造的方式对MDVRP进行求解，注重了单一车辆，忽视了问题的整体性[7-9]。本文拟采用启发式优化算法和整体法求解基于时间窗的VRP，不仅考虑了VRP的整体性，还兼顾了单一车辆的优化。

1 问题描述及数学建模

基于时间窗的MDVRP（图1）可描述为：配送区域内有M个车场，每个车场具有运载能力为Q的车辆Km（m=1,2,…,M）辆，配送区域有N个客户，每个客户的需求量为qi(i=1,2,…,N)，且对于任意客户i都有需求量qi

图1 多配送中心问题

客户编号为0,1,2,…,N；车场编号为N+1,N+2,…, N+M。为建模方便，定义两个变量：

基于时间窗的MDVRP数学模型为：

其中，式（3）表示配送完所有客户点所花费的费用最低，包括车辆启用的固定成本、运行过程中的油料消耗和由于时间延误造成的惩罚费用；式（4）表示车辆的容量限制，即一辆车所配送客户的总需求不能超过车辆的最大容载量；式（5）表示每个车场完成配送任务使用的车辆数目不超过该车场车辆总数；式（6）表示一个客户点的任务只能对应一个车场中的一辆车；式（7）、（8）表示每个客户只能被来自同一车场的同一辆车服务，其他车场的车辆不能对该客户进行服务；式（9）表示所有配送车辆从配送中心出发，完成配送任务后再返回配送中心；式（10）表示车辆不能从一个车场达到另一个车场；式（11）表示客户的时间窗约束，即在规定时间内，客户需求得到满足，否则车辆将增加一定的惩罚成本。

2 多车场问题的解决方法分析

在当前物流配送中对车辆调度问题的研究主要集中在配送规模较大、范围广、客户数量多的多配送中心模式，且在实践中发现一般规模较大的物流企业都采用多配送中心车辆调度模式，因此研究多配送中心车辆调度问题具有重要的现实意义[10]。目前解决多配送中心车辆调度问题主要采用传统方法、整体法和启发式优化法。

2.1 分区法求解VRP

传统方法是将多配送中心车辆调度问题看作是多个单配送中心车辆调度问题的组合，先将其分离再进行优化[11]。传统方法的研究重点在于如何将多配送中心车辆调度问题拆分成多个单配送中心车辆调度问题，然后在全局的基础上对其解进行优化。拆分过程中主要按照距离最近或划分边界的原则确定各配送点与配送中心的对应关系；实际应用中一般以配送中心的总配送路程最短优先，因此选取距离最近原则来划分客户。传统方法的求解方式有圆域分区法、中垂线分区法和最近邻域法（图2）。传统方法具有一定的可行性，但在拆分过程中失去了问题的整体性，仅在各配送中心范围内取得费用最少，很难在整体上取得最优解。

图2 分区法解决多配送中心车辆调度问题

2.2 整体法求解VRP

与传统方法的思路相反，整体法在解决多配送中心车辆调度问题时将配送过程看作一个整体，首先设置虚拟的配送中心，然后使所有配送车辆从虚拟配送中心出发，到达实际配送中心后，按照就近原则选择要服务的客户点，完成配送任务后，返回实际配送中心[12]。整体法从全局角度考虑了问题的最优解，但是在解决时间窗的多配送中心车辆调度问题时，距离最近并不意味整体消耗最少，配送点的选择不仅要考虑配送点之间的距离，而且要考虑配送点的时间窗要求（图3）。

2.3 启发式优化法求解VRP

启发式优化法的思想是把多配送中心车辆调度问题看作是复杂的多个问题的组合，在此基础上进行优化研究[13]。与传统方法和整体法不同，启发式优化法是通过一系列方法来简化求解计算过程，以降低求解搜索的复杂程度。常用的启发式优化算法有遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法和人工神经网络算法等。启发式优化算法在求解VRP时，首先对路径进行编码，再通过不断更新节点的顺序获取VRP的最优解。它具有较好的收敛性，求解质量高，但过分关注求解每一辆车的最优路径，忽视了问题的整体性（图4）。

图3 整体法解决多配送中心车辆调度问题

图4 启发式优化方法求解多配送中心车辆调度问题

3 混合算法设计

启发式优化算法在解决单车场问题时具有较好的收敛性，整体法在求解多车场问题时具有较好的全局性。鉴于此，首先设置虚拟配送中心将多配送中心车辆调度问题转化为单车场VRP，然后采用启发式优化算法求解单车场VRP，最后为每个配送点选择车场。混合算法流程如图5所示。

混合算法的一般步骤为：

1）参数设置，主要包括选择自适应的交叉率和变异率，蚁群信息素的总量、蚂蚁个数以及α、β；

2）确定染色体编码方式和适应度函数的计算方式；

3）对所有节点进行染色体编码，并计算染色体的适应度值，选择父代中较好的一部分染色体遗传到下一代，子代进行自适应的交叉和变异过程，并产生新的染色体；

4）计算新染色体适应度值，并根据适应度值进行折半排序；

5）计算相邻两代染色体适应度值的平均值，并计算相邻两代染色体的进化率，若相邻两代染色体的进化率不超过3%或超过遗传算法中设置的最大迭代次数，则将该组染色体的适应度值转化成蚁群算法中初始状态下的信息素浓度，否则重新进行选择、交叉和变异操作；

6）将所有蚂蚁随机放置在任意一个顶点，蚂蚁根据状态转移规则选择下一个待访问的节点，当蚂蚁选择完所有节点后，形成多条访问路径；

图5 混合算法设计流程图

7）计算当前所有路径适应度值，并标记适应度值最好的蚂蚁；

8）更新当前最优路径上的信息素浓度，然后更新所有路径上的信息素浓度；

9）判断当前迭代次数与最大迭代次数的关系，若当前迭代次数小于蚁群算法的最大迭代次数，则将每只蚂蚁重新放置在各节点处，按照状态转移规则重新访问所有节点，否则停止蚁群算法，得到当前一组最优路径；

10）对于当前每一条路径，采用2-opt算法进行路径优化，得到一组基于虚拟配送中心的车辆路径，再对所有路径进行排序；

11）计算每辆车到实际配送中心的消耗，再将虚拟配送中心转换成实际配送中心，总消耗最小的转换结果即为当前最优的配送方案。

4 案例分析

为了验证混合算法的有效性，实验采用标准的MDVRPTW问题进行实验验证。实验环境为Inter酷睿i5，内存8 G，操作系统为Windows10，编程语言为C++，开发环境为VS2010。

标准的MDVRPTW问题是：有3个配送中心A、B、C，每个配送中心货物充足，有15个配送点，每个客户点具有一定的需求量，也有一定的时间窗限制，具体的车辆路径实验数据如表1、2所示[14]。

为了验证算法的有效性，实验分别采用MDVRP的传统方法（中垂线法）、整体法、启发式优化算法以及本文设计的混合算法对多车场的时间窗问题进行求解。实验中设定车辆的单位油耗为8，车辆的启动成本为60，配送过程早到所产生的等待成本为0.5，晚到所产生的惩罚成本为1.5，测试结果如表3所示。

表1 客户点的实验数据

表2 配送中心的实验数据

表3 测试结果统计

由表3可知，分区法、整体法和启发式优化算法在求解带时间窗的MDVRP时，分区法的效果最差，整体法次之，启发式优化算法最好，而混合算法比启发式优化算法的平均费用降低了85个单位。因此，采用混合算法可降低带时间窗的MDVRP的费用。

5 结 语

本文针对基于时间窗的MDVRP建立了配送方案的最小费用模型，分析了分区法、整体法和启发式优化算法在解决MDVRP时的优劣；并结合整体法和启发式优化算法，进行了混合算法的设计，最后通过实验验证了混合算法在解决带时间窗的MDVRP的有效性。

[1] 杨从平.基于蚁群算法的快递物流配送路径优化[J].物流工程与管理,2014(4)：65-67

[2] 姚婷婷.车辆调度有及其遗传算法[D].兰州：西北师范大学,2013：2-3

[3] 邹彤,李宁,孙德宝,等.多车场车辆路径问题的遗传算法[J].计算机工程与应用,2004(21)：82-83

[4] 杨元峰.多车场多车型车辆路径问题的改进遗传算法[J].计算机与现代化,2008(9)：10-13

[5] 钟石泉,贺国光.多车场有时间窗的多车型车辆调度及其禁忌算法研究[J].运筹学学报,2005(4)：67-73

[6] 李小花.多车场带容量限制弧路径规划问题研究[D].重庆：重庆大学,2009：23-25

[7] 戴树贵,陈文兰,潘荫荣,等.多配送中心车辆路径安排问题混合蚁群算法[J].四川大学学报(工程科学版),2008(6)：154-158 [8] 孙世权.多配送中心车辆路径优化问题的研究[D].西安：西安电子科技大学,2012：3-4

[9] 汪平.多生产点烟草企业的原材料运输车辆路径问题研究[D].武汉：华中科技大学,2010：12-14

[10] 高志刚.多车辆配送路径分析及与GIS平台的集成技术研究[D].武汉：武汉理工大学,2005：10-11

[11] 王诗瑶,王文发,富文军,等.大规模单车场VRP问题中扫描法的改进[J].现代电子技术,2014(24)：34-36

[12] 高特,李莉,钟莲,等.乌鲁木齐市社区蔬菜直销统一配送路径优化[J].物流技术,2014(11)：168-170

[13] 张立峰,赵方庚,孙江生,等.战时备件配送的MDVRP问题及其遗传算法求解[J].计算机应用与软件,2010(2)：194-196 [14] 钟石泉.物流配送车辆调度智能优化方法研究[D].天津：天津大学,2004：3-5

P208

B

1672-4623（2017）05-0035-04

10.3969/j.issn.1672-4623.2017.0051.1

闫凯，硕士研究生，主要研究方向为运筹地理信息系统。

2016-10-31。

项目来源：国家自然科学基金资助项目（7130939）。