多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法

刘　云，张惠珍

(上海理工大学　管理学院，上海　200093)

多目标带时间窗的车辆路径问题的单亲遗传混合蚁群算法

刘云，张惠珍

(上海理工大学管理学院，上海200093)

摘要：考虑具有最大等待时间、最大运输时间限制且带时间窗的车辆路径问题，建立了以车辆行驶路径最短和使用车辆数最小为目标的数学模型。将单亲遗传算法和基本蚁群算法相结合，使其优势互补，并利用单亲遗传算法的特点，构建出两种求解该问题的单亲遗传混合蚁群算法，分别为：单点单亲遗传混合蚁群算法和多点单亲遗传混合蚁群算法。测试算例的结果表明：求解多目标带时间窗的车辆路径问题时，与基本蚁群算法相比，单亲遗传混合蚁群算法具有计算效率高、收敛性好等优点，尤其单点单亲遗传混合蚁群算法不仅具有较好的计算性能，而且具有较高的稳定性。

关键词：交通工程；车辆路径问题；单亲遗传混合蚁群算法；多目标；时间窗

0引言

带时间窗的车辆路径问题[1](Vehicle Routing Problem with Time Windows, VRPTW)最早由Savelsbergh提出，是在车辆路径问题(Vehicle Routing Problem, VRP)的基础上增加了客户接受配送服务的时间窗要求，较VRP更贴近实际生活。VRPTW已被证实是一个NP难问题，当问题规模较大时，精确算法难以求出其最优解，因此，国内外很多学者利用智能启发式算法来寻找其满意解。常见的求解VRPTW的智能启发式算法有遗传算法[2-3]、蚁群算法[4-7]、模拟退火算法[8-9]、粒子群算法[10-11]等。然而，迄今为止，这些智能启发式算法大都被用于求解单目标的车辆路径问题，在多目标车辆路径优化问题中涉及的并不多。随着电子商务的迅速发展，物流配送任务日益庞大和复杂，追逐单一目标最优已经无法满足商家的发展要求，因此研究多目标的车辆路径问题迫在眉睫。

多目标车辆路径问题是指：给定若干具有一定需求量的客户，若干具有一定装载能力的车辆从配送中心出发，为客户进行配送服务后回到配送中心，同时使总路程最短、车辆数最少、费用最省等多个目标达到最优。与带时间窗的单目标车辆路径问题相比，多目标车辆路径问题更接近于现实生活，对实际问题更有指导意义。本文所研究的多目标VRPTW不仅要求完成配送任务的总路程最短和车辆数最少，而且车辆在配送过程中的等待时间和运输时间不能超过一定限制，本文将该问题称之为“具有最大等待时间和运输时间限制的多目标带时间窗的车辆路径问题”。

单亲遗传算法[12](Partheno-Genetic Algorithm, PGA)取消了传统遗传算法(Genetic Algorithm, GA)中的交叉算子，仅需一个父代，因此即使种群中的个体均相同，也不会影响遗传操作，降低了对种群多样性的要求。此外，单亲遗传算法在寻优效率和“早熟收敛”上都较传统遗传算法具有优势[13]。而蚁群算法(Ant Colony Algorithm, ACA)具有鲁棒性强、可以进行分布式计算，易与其他算法有效结合等优点，但其容易陷入局部最优。本文针对具有最大等待时间、最大运输时间限制的多目标带时间窗的车辆路径问题，在单亲遗传算法和蚁群算法的基础上，吸收这两种方法的长处和优势，克服它们的短处和缺陷，进而提出混合型搜索多目标车辆路径问题的启发式优化算法，并通过测试算例验证其求解性能。

1具有最大等待时间和运输时间限制的多目标VRPTW

1.1问题描述

本文研究的是总路程和车辆数均受限的多目标VRPTW，该问题不仅要求配送车辆完成配送任务所行驶的总路程最短，而且要求在总路程最短的基础上完成任务所使用的车辆数最少。假设所有车辆都相同且容量相等，所探讨的问题也必须同时要满足如下条件：

(1)服务约束：每辆车可以服务多个客户，但一个客户只能由一辆车服务。

(2)配送中心约束：所有车辆由单一配送中心出发，配送完路径上所有的客户后返回到配送中心。

(3)装载量约束：每条路径上所有客户的需求量之和不能超过车辆的最大载重量WE。

(4)最大运输时间约束：每辆车的运输时间(行驶时间、服务时间以及等待时间之和)不能超过最大运输时间T。

(6)最大等待时间约束：车辆给任一客户配送货物时的等待时间不能超过W，车辆若早于客户最早服务时间ei到达，则需等待一段时间，等待时间过长会影响车辆的配送效率，增加企业成本。

1.2符号定义与数学模型

下面对具有最大等待时间和运输时间限制的多目标带时间窗的车辆路径问题建立数学模型。

决策变量：

数学模型：

(1)

(2)

S.T

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

模型中，式(1)和式(2)分别为要求总路程和车辆数最少的目标函数；式(3)为车辆载重量限制；式(4)表示每一个客户只能由一辆车服务；式(5)表示从配送中心出发的车辆在完成配送任务后要返回配送中心；式(6)表示车辆在服务完客户i后紧接着服务客户j；式(7)表示车辆在服务完客户j之前只服务客户i；式(8)表示消除子回路，式(6)～式(8)共同形成可行回路；式(9)为车辆运行时间限制；式(10)为到达每个客户的时间表达式；式(11)为时间窗限制；式(12)为等待时间表达式。

2单亲遗传混合蚁群算法的设计

2.1单亲遗传算法

单亲遗传算法的遗传算子包括基因重组算子和基因突变算子。基因重组算子又可分为基因换位算子、基因移位算子以及基因倒位算子。单亲遗传算法所有的遗传操作都可分为单点基因操作和多点基因操作。本文所用的遗传算子为单、多点基因换位算子和单、多点基因移位算子，现分别介绍如下：

(1)基因换位算子

基因换位是指交换一条染色体中某两个(些)基因的位置[14]，被交换的基因位置随机生成。

单点基因换位：

基因移位是指将一条染色体中某个(些)子串中基因的位置依次后移，并把该子串中的最后一个基因移到最前面的位置[14]，子串长度随机生成。

单点基因移位：

多点基因移位：

2.2蚁群算法

蚁群算法是意大利学者M．Dorigo等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。蚁群算法采用分布式并行计算机制，易与其他方法结合，具有较强的鲁棒性等特点。但该算法亦有搜索时间较长，易陷入局部最优的缺点。路径上信息素的更新和蚂蚁状态的转移是蚁群算法的重要组成部分。本文针对基本蚁群算法收敛速度慢和易陷入局部最优等缺点，蚂蚁的状态转移规则采用了确定性选择和伪随机比例选择相结合的方法，以便有效抑制算法的早熟现象，并加快算法的求解速度。

2.2.1信息素更新规则

本文利用式(13)～(15)对客户i和客户j路径上的信息素进行更新：

(13)

(14)

(15)

2.2.2状态转移规则

本文采用了确定性选择和伪随机比例选择相结合的方法确定蚂蚁的状态转移，即当蚂蚁位于客户i时，会以概率q0使用确定性选择规则或以概率1-q0使用伪随机比例选择规则(pseudo random proportional action choice rule)选择下一个客户j。

确定性选择规则：

(16)

伪随机比例规则：

(17)

2.3单亲遗传混合蚁群算法的步骤

将单亲遗传算法和蚁群算法相融合，本文构建了求解多目标车辆路径问题(1)～(12)的单亲遗传混合蚁群算法，其算法框图如图1所示。

图1　算法流程图Fig.1　Flowchart of algorithm

单亲遗传混合蚁群算法的优化步骤如下：

步骤1：初始化各参数，确定蚂蚁数m和最大迭代次数NC_max。

步骤2：m只蚂蚁从配送中心出发。对于蚂蚁k，按照式(16)、(17)计算其转移概率，确定下一个服务的客户j，若客户j满足载重量(3)、车辆运行时间(9)、 时间窗(11)、等待时间(12)等约束条件，则将客户j加入蚂蚁k的禁忌表中;否则，车辆回到配送中心，并重新启动下一辆车执行未完成的配送任务。

步骤3：所有客户服务结束后，蚂蚁完成一次周游，此时得到问题的一个可行解。更新蚂蚁数k=k+1，若k≤m，转步骤2；否则，转步骤4。

步骤4：从m只蚂蚁的禁忌表中选出最优路径，并对其进行单亲遗传操作(采用不同的基因移位、基因换位操作，即可产生不同的单亲遗传混合蚁群算法),即将该最优解路径A看成一个染色体，按一定的概率q对其作移位或换位变换，生成一条新路径B。

步骤5：若路径B的目标函数值优于路径A的目标函数值，则更新最优路径和最优解，同时将禁忌表中路径A更新为路径B，以新的禁忌表更新信息素；否则，最优路径、最优解、禁忌表保持不变。

步骤6：根据信息素更新规则，式(13)～(15)对信息素进行更新，并清空禁忌表。更新迭代次数NC=NC+1 ，若NC≤NC_max，转步骤2。

步骤7：输出当前最优解和最优路径。

3实例计算

为了测试算法的计算性能，本文利用基本蚁群算法、单点单亲遗传混合蚁群算法和多点单亲遗传混合蚁群算法对文献[15]中的测试算例进行求解，并对比分析各种算法的求解效率与精度。

从这一土地流转的案例中，我们可以看到，农村土地流转实践并非只要按照《土地承包法》的法律条文和完全的市场竞争原则，承包人与农户就可以面对面地讨价还价并达成流转协议。土地流转的过程其实是一个复杂的社会建构过程，在这一过程中，资本角色、政府角色和农户角色都可能要根据特定的社会情境选择各自的行动策略，并围绕土地流转目标建构起流转优先权的社会意义，也就是要赋予农村土地权属和边界的变动以合适的理由或解释，即为什么要进行土地流转，为什么要把土地流转给特定承包者。

测试算例中各参数设定情况如下：利用最大载重量WE为8 t的最少车辆向20个客户(客户数据如表1所示)提供配送服务，每辆车的最大运行时间T为8 h，车辆等待时间wi上限为4.5 h(为避免初次迭代时无法确定第一个客户，故等待时间上限为客户中最迟的时间窗开始时刻，即为客户编号10的时间窗开始时刻4.5 h)，车辆的运行速度v保持恒定为40 km/h。配送中心坐标位置为(70 km，70 km)，配送中心的需求量、服务时间、时间窗均为0。

表1　客户数据

本文利用MATLAB R2011a 对基本蚁群算法、单点单亲遗传混合蚁群算法和多点单亲混合蚁群算法进行编程实现，3种算法在 Intel Core i3-2310M 2.10 GHz (6.00GB RAM)，操作系统为Win7的环境下运行。为便于比较，3种算法中各参数设定相同的数值，参数设定情况为：蚂蚁数m=20，最大迭代次数NC_max=200，信息素挥发系数ρ=0.1，信息素强度Q= 15，信息素因子α=1，显著性因子β=1，时间窗紧度因子γ=2，节约量因子ε= 3，转移概率q0=0.6，换位算子概率q=0.7。

3种算法随机运行25次，优化结果如表2所示。基本蚁群算法求出的最优路径长度为1 201.923 km,最优车辆数为8辆，算法运行平均耗时为65.84 s；单点单亲遗传混合蚁群算法求出的最优路径长度为1 157.415 km,最优车辆数为7辆,算法运行平均耗时为56.25 s；多点单亲遗传混合蚁群算法求出的最优路径长度为1 189.409 km,最优车辆数为7辆,算法运行平均耗时为57.63 s。可见，单点单亲遗传混合蚁群算法与多点单亲遗传混合蚁群算法具有较高的求解效率，其求得的解均优于基本蚁群算法求得的解，并且单点单亲遗传混合蚁群算法的求解性能更优于多点单亲遗传混合蚁群算法。

表2　3种算法计算结果的比较

经过多次测试运算发现，单点单亲遗传混合蚁群算法在其他参数保持不变的情况下，改变转移概率q0的取值，计算结果能够得到进一步优化。当q0=0.4时，随机运行单点单亲遗传混合蚁群算法10次所得的车辆数均为7，路径长度的标准差为16.435 km。较低的标准差说明单点单亲遗传混合蚁群算法具有较好的稳定性。

单点单亲遗传混合蚁群算法10次运行结果的最优路径长度为1 095.510 km，车辆数为7辆，最优配送方案的路线图如图2所示(1代表配送中心，2-21代表20个客户的编号)。7辆车的配送路线分别为：

车辆1：1-8-4-1；

车辆3: 1-2-3-18-1；

车辆4: 1-19-15-12-6-1；

车辆5: 1-11-14-21-7-1；

车辆6: 1-20-13-1；

车辆7: 1-9-17-1。

图2　最优配送方案路径图(单位：km)Fig.2　Routes of optimal delivery scheme(unit:km)

4结论

本文对具有最大等待时间和运输时间限制的多目标带时间窗的车辆路径问题建立了数学模型，然后针对该问题，将单亲遗传算法与蚁群算法相结合，使两种算法相互取长补短，设计出求解多目标车辆路径问题的单亲遗传混合蚁群算法。求解测试算例表明：在基本蚁群算法中引入单亲遗传算子操作后，能够有效改善基本蚁群算法收敛速度慢和易陷入局部最优的缺点。本文所设计的单亲遗传混合蚁群算法不仅具有较好的求解性能，而且能够有效求解多目标带时间窗的车辆路径问题，尤其单点单亲遗传混合蚁群算法具有较高的计算效率和较高的稳定性，是求解多目标带时间窗的车辆路径问题的一种有效算法。

本文所提出的单亲遗传混合蚁群算法不仅为多目标车辆路径问题的求解提供了一种较为有效的工具和手段，而且本文研究内容也拓宽了蚁群算法的改进方法。

参考文献：

References:

[1]SAVELSBERGH M W P. Local Search in Routing Problems with Time Windows [J]. Annals of Operations Research, 1985, 4(1): 285-305.

[2]URSANI Z, ESSAM D, CORNFORTH D, et al. Localized Genetic Algorithm for Vehicle Routing Problem with Time Windows [J]. Applied Soft Computing, 2011, 11 (8):5375-5390.

[3]GHOSEIRI K, GHANNADPOUR S F. Multi-objective Vehicle Routing Problem with Time Windows Using Goal Programming and Genetic Algorithm [J]. Applied Soft Computing, 2010, 10 (4):1096-1107.

[4]DING Q L ，HU X P, SUN L J, et al. An Improved Ant Colony Optimization and Its Application to Vehicle Routing Problem with Time Windows [J]. Neurocomputing, 2012,98(12): 101-107.

[5]张勇. 基于改进蚁群算法物流配送路径优化的研究 [J]. 控制工程, 2015, 22(2):252-256.

ZHANG Yong. Study of Optimizing Logistic Distribution Routing Based on Improved Ant Colony Algorithm[J]. Control Engineering of China, 2015, 22(2):252-256.

[6]何小锋,马良.带时间窗车辆路径问题的量子蚁群算法 [J]. 系统工程理论与实践,2013, 33 (5):1255-1261.

HE Xiao-feng, MA Liang. Quantum-inspired Ant Colony Algorithm for Vehicle Routing Problem with Time Windows [J]. Systems Engineering-Theory & Practice, 2013, 33 (5):1255-1261.

[7]温惠英,徐建闽.基于改进型蚁群算法的车辆导航路径规划研究 [J]. 公路交通科技,2009,26(1):125-129.WEN Hui-ying, XU Jian-min. Research on Vehicle Routing Problem Based on Improved Ant Colony Algorithm[J]. Journal of Highway and Transportation Research and Development, 2009, 26(1):125-129.

[8]王超,穆东. 基于模拟退火算法求解VRPSPDTW问题 [J]. 系统仿真学报, 2014, 26(11): 2618-2623.

WANG Chao, MU Dong. Solving VRPSPDTW Problem Using Simulated Annealing Algorithm[J]. Journal of System Simulation, 2014, 26(11): 2618-2623.

[9]马华伟,靳鹏,杨善林.时变车辆路径问题的启发式算法 [J].系统工程学报,2012,27(2):256-262.

MA Hua-wei, JIN Peng, YANG Shan-lin. Heuristic Methods for Time-dependent Vehicle Routing Problem [J]. Journal of System Engineering, 2012, 27(2):256-262.

[10]宁涛,陈荣,郭晨, 等. 一种基于双链量子编码的动态车辆路径问题解决策略 [J]. 运筹学学报, 2015,19(2):72-82.

NING Tao, CHEN Rong, GUO Chen, et al. A Scheduling Strategy for Dynamic Vehicle Routing Problem Based on Double Chains Coding [J]. Operations Research Transactions, 2015, 19(2):72-82.

[11]温惠英,孙博. 基于离散粒子群算法的协同车辆路径问题 [J]. 公路交通科技, 2011,28(1):149-153,158.WEN Hui-ying, SUN Bo. Resolving Collaborative Vehicle Route Problem Based on Discrete Particle Swarm Optimization[J]. Journal of Highway and Transportation Research and Development, 2011, 28(1):149-153,158.

[12]李茂军,童调生. 单亲遗传算法及其全局收敛性分析 [J]. 自动化学报, 1999, 25(1):71-75.LI Mao-jun, TONG Tiao-sheng. A Partheno Genetic Algorithm and Analysis on Its Global Convergence [J]. Acta Automatica Sinica, 1999, 25(1): 71-75.

[13]肖鹏,李茂军,张军平,等. 车辆路径问题的单亲遗传算法 [J]. 计算技术与自动化, 2000,19(1):26-30.XIAO Peng, LI Mao-jun, ZHANG Jun-ping, et al. Partheno Genetic Algorithm for Vehicle Routing Problem [J]. Computing Technology and Automation, 2000, 19(1):26-30.

[14]李茂军,罗日成,童调生. 单亲遗传算法的遗传算子分析[J]. 系统工程与电子技术, 2001,23(8):84-87.LI Mao-jun, LUO Ri-cheng, TONG Tiao-sheng. Analysis on the Genetic Operators of Partheno-Genetic Algorithm[J]. Systems Engineering and Electronics, 2001, 23(8):84-87.

[15]李建,张永,达庆利. 第三方物流多车型硬时间窗路线问题研究 [J]. 系统工程学报, 2008,23(1):74-80.LI Jian, ZHANG Yong, DA Qing-li. Research on Heterogeneous Vehicle Routing Problem with Hard Time Windows for the Third Party Logistics [J]. Journal of System Engineering, 2008, 23(1):74-80.

A Partheno-genetic Hybrid Ant Colony Algorithm for Solving Multi-objective Vehicle Routing Problem with Time Window

LIU Yun, ZHANG Hui-zhen

(School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China)

Abstract：Considering the vehicle routing problem which has the restriction of maximum vehicle waiting time, maximum vehicle transport time and time windows, a mathematical model for the shortest length of vehicle travel and the minimum number of the using vehicles as the multi-objective is established. Then, 2 partheno-genetic hybrid ant colony algorithms for solving the problem are proposed by combining partheno-genetic algorithm with basic ant colony algorithm to have their complementary advantages and the features of partheno-genetic algorithm, which are monogene partheno-genetic hybrid ant colony algorithm and polygenic partheno-genetic hybrid ant colony algorithm. The result of the test case shows that the partheno-genetic hybrid ant colony algorithm has the advantages of better computational efficiency and convergence, and especially monogene partheno-genetic hybrid ant colony algorithm is more stable and has better computational performance.

Key words：traffic engineering；vehicle routing problem；partheno genetic hybrid ant colony algorithm；multi-objective；time window

收稿日期：2015-08-20

基金项目：国家自然科学基金项目(71401106)；高等学校博士学科点专项科研基金联合课题项目(20123120120005)；上海市教育委员会科研创新项目(14YZ090)；上海高校青年教师培养计划项目(slg12010)

作者简介：刘云(1992-)，女，江苏盐城人，硕士研究生.(duianly0915@163.com)

doi:10.3969/j.issn.1002-0268.2016.06.015

中图分类号：TP18

文献标识码：A

文章编号：1002-0268(2016)06-0095-06