黄务兰1,2，张涛1,3

　　（1.上海财经大学 信息管理与工程学院,上海 200433； 2.常州大学 商学院, 江苏 常州 213164；3.上海财经大学 上海市金融信息技术研究重点实验室，上海 200433）

      摘要：该文以最小化配送时间为目标，研究带时间窗的车辆路径问题，建立整数规划模型。为了加快遗传算法的收敛速度和寻优能力，提出一种改进遗法算法IGALS (Improved Genetic Algorithm with Local Search)。改进算法借用精英保留策略，采用点交叉和段交叉算子结合的交叉算子；提出路段允许延迟时间概念，并以此为依据使用局部搜索策略进一步提高解的质量。通过Solomon标准算例测试，验证了改进算法(IGALS)较简单遗传算法(GA)具有更好的全局寻优能力和更快的收敛速度。

　　关键词：带时间窗车辆路径问题；遗传算法；交叉算子；局部搜索；整数规划

0引言

　　车辆路径问题(Vehicle Route Problem，VRP)的研究最早由DANTZIG G和RAMSER J于1959年提出［1］，近60年来始终是运筹学与组合优化领域的研究热点，受到了国内外研究者的广泛关注。为了满足实际需求，学者对VRP问题逐步进行了扩展和变形。其中带时间窗车辆路径问题（Vehicle Route Problem with Time Windows，VRPTW）是在车辆路径问题的基础上加入了时间窗约束。加入时间窗后，极大地增加了VRP问题计算难度和复杂度，除了考虑VRP问题空间方面的路径之外，还必须考虑时间上的排程，因此吸引了许多国内外学者对其进行研究，成为VRP问题研究领域最热门的研究方向之一［24］。本文研究带时间窗路径优化问题，以最小化配送时间为目标建立路径优化数学模型，借用精英策略思想设计交叉算子提高遗传算法的寻优性能，并使用基于延迟时间的局部搜索策略进一步提高解的质量。

1问题描述和数学建模

　　带时间窗车辆路径优化问题描述为：某快递配送中心拥有M辆型号相同且载重量为Q的配送车辆，为N个已知客户做派发快件服务。每个顾客服务位置和需求量已知，客户具有服务时间窗［ETi,LTi］，即最早和最迟开始服务时间，以及持续服务时间STi，如果车辆到达客户i的时间早于ETi，车辆需要在客户i处等待。现要求对该问题进行路径规划，要求在最小化成本的前提下配送完所有客户所花费的总时间最少。为了能更准确地表述模型，引入如下符号体系:M表示可供使用的最大车辆数；N表示客户数目；Q表示车辆的最大载重量；tij表示顾客i到顾客j的路由时间； ［ETi,LTi］表示节点i的时间窗；ATi表示车辆到达节点i的时间；Si表示车辆k开始服务节点i的时间；WTi表示车辆在客户i处的闲置等待时间；STi表示顾客i持续服务时间，为已知量。

　　定义如下决策变量：

　　xijk=1,车辆k由客户i驶向客户j

　　0,其他

　　yik=1,客户i的配送任务由车辆k完成

　　0，其他

　　本文目标是合理安排配送路径，力求配送完所有客户所花费的总时间最少。其中，配送时间分为三部分：车辆的路由时间，可由式(1)表述；车辆因时间窗未开在客户处的等待时间，可由式(2)表述；服务客户的时间，因该时间是一已知量，与决策安排无关，因此不列入目标函数中。

　　式(4)表示客户i只能由一辆车为其配送服务；式(5)表示配送中心最多发出M辆车；式(6)和式(7)表示两个变量之间的关系；式(8)确保每辆车承载的货物总量不超过其最大容量，且不为负；式(9)初始化到达配送中心时间、开始服务时间与持续服务时间都为0；式(10)表示车辆到达客户i的时间先于或等于开始服务时间，且为非负时间；式(11)表示顾客i的持续服务时间为正数；式(12)表示车辆由客户i到达客户j的时间计算公式，即前驱点与后继点的时间关系；式(13)表示服务客户i的时间应满足时间窗约束；式(14)表示实际开始服务客户i的时间计算方法； 式(15)和式(16)分别表示变量xijk和yik的取值范围为0或1。

2求解算法设计

　　2.1改进的交叉算子

　　遗传算法是由美国的HLLAND J H教授［5］最早提出的，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。本文结合实际问题，提出一种改进的遗传算法，称之为IGALS (Improved Genetic Algorithm with Local Search)。

　　本文采用点交叉和段交叉结合的方式，保证遗传算法种群的多样性。其中点交叉采用循环交叉方法，段交叉方法借用精英策略的思想。它将每辆车的行驶线路划分为一段，对每一段线路计算目标值。将单个种子某趟车目标值优的路线保留不变，同时借鉴参与交叉的另一种子中目标值优的某趟车路线来替换目标种子中目标值劣的某车辆路段，交换之后去掉重复节点，这样可以有目的地进一步优化目标种子的解。

　　设有15个节点，参与交叉的父代种子Pr1和Pr2，其中每个种子按单趟车辆线路划分为4段，种子内部适应值最优车辆线路标识为Elite1和Elite2，最坏适应值车辆路段分别标识为Worse1和Worse2，如图1所示。

　　交叉过程中种子内部次序调整如下，即将最坏路段置为第一段，精英路段置为第二段，如图2所示。

　　最后，将交叉种子精英路段替换掉目标种子最坏路段，并去掉后面重复节点。交叉后的两种子如图3所示，其中“*”号表示去掉重复种子留下的空位。去掉目标种子的最坏路段节点，Pr2中的11、13节点是有待进行重新插入的节点，必要时进行重新排序的操作，交叉后的两种子如图4所示。

　　2.2局部搜索策略

　　局部搜索算法也称大规模邻域搜索（Large Neighborhood Search，LNS），是一类改正型算法，它是1998年由SHAW P［6］提出的，算法的每一步迭代都是通过搜索当前解的邻域得到一个改进的解。因时间窗约束，种子在迭代过程中解的质量并不十分理想。基于此，本文设计一种局部搜索(Local Search)策略，提出路段允许延迟时间概念，依据该指标，在可行线路中进行局部搜索，最大限度地减少节点等待时间，进一步优化遗传算法的求解性能，找到使目标值更优的解。

　　设有一条可行线路Routek(v0,v1,…,vi－1,vi,vi+1,…,vn,v0)，其中v0为配送中心， vi(i=1,2,3…n)为车辆要配送货物的客户点，已知客户i的时间窗［ETi，LTi］和配送中心时间窗［0,H］，车辆在vi点的持续服务时间STi，tij为车辆从i到j的时间，WTi为车辆在vi点的等待时间。

　　定义每个节点的最早完成时间Vei和最迟开始时间Vli，最早完成时间Vei表示车辆完成从v0到vi配送任务的最早时间，而最迟开始时间Vli表示车辆顺利完成vi到vn各点的配送任务，应在vi点开始作业的最晚开始时间。

　　Vei和Vli的计算方法如下：

　　Vei=max(ETi+STi,Vei－1+ti－1,i+STi)(17)

　　Vli=min(LTi,Vli+1－ti,i+1－STi)(18)

　　因车辆在配送中心无配送任务，ST0=0，故Ve0=ET0=0，Vl0=LT0=H，从Ve0＝0开始依次计算Ve1、Ve2、…、Ven的值。从Vl0＝H开始依次计算Vln，Vln－1，…，Vl1的值。

　　定义：相邻节点(vi,vj)即某一路段的允许延迟时间用DTij表示:

　　DTij=Vlj－Vei(19)

　　(1)移除策略

　　①移除路由时间tij比较大的客户节点j将其从原始路线中移出；②移除等待时间WTj较大的客户节点j；③移除tij+WTj值较大的客户节点。

　　（2）重插策略

　　①将违反时间窗和载重量的位置排除，这些位置不能插入；②设有可行线路(v0,v1,…,vi－1,vi,vi+1,…，vn,v0)，将vj点插入vi－1到vi之间的充要条件是:

　　DTi－1,i≥ti－1,j+tji－ti－1,i+STj (20)

　　很明显，采用该局部搜索策略会明显降低目标值中的等待时间，充分发挥寻优作用。

3仿真实验和数据分析

　　本文采用Solomon标准测试算例C1、R1、RC1型数据进行测试，它们具有时间范围较短，车辆容量较小的特点，适合模拟本文描述问题。

　　实验采用C++语言，在Visual Studio 2010集成开发环境中编写，程序运行在Win 7系统中的Intel Corei5，2.5 GHz主频(6 GB内存)，64位的Laptop机上。车辆路由速度为单位速度，交叉概率pc=0.75，变异概率pm=0.10，种群规模设为100，表1是两种算法每个算例运行10次的结果，平均目标值为10次取平均的结果。可见，29组测试数据中，改进的混合遗法算法平均目标值全部优于简单遗传算法，最大改进率高达35.54%。改进的混合遗传算法使用局部搜索策略和精英交叉策略，加快了寻优速度，并能有效地避免算法陷入局部最优。

　　算例R101最优结果的迭代过程如图5所示，横轴代表算法迭代次数，纵轴代表最优解的值。简单遗传算法在迭代20 000次左右陷入了局部最优解，最优值为2 724.61，可以看出算法的最大缺陷是“早熟”。改进的混合遗传算法前段收敛速度较快，其中迭代到16 000次左右遇到一个局部较优解，目标值为2 704.58，但是算法很快就跳出该解，最后求得一个更优解，目标值降到2 568.44。改进的混合遗传算法在后段能够跳出局部最优解，主要是局部搜索算法进一步寻优的结果。说明改进的混合遗传算法能够较好地避免“早熟”并有较快的收敛速度。

4结论

　　当前电子商务的快速发展带动了快递物流业的发展，影响快递服务质量的关键因素之一为快递配送时效。本文以最小化快递配送时间为目标，研究带时间窗的车辆路径问题，建立数学模型；为克服遗传算法收敛速度慢和早熟的缺陷，设计并采用了一种段交叉算子和基于延迟时间的局部搜索策略。通过Solomon标准算例测试表明，改进的混合遗传算法较简单遗传算法有较好的全局寻优能力，验证了本文算法的有效性。

参考文献

　　［1］ DANTZIG G, RAMSER J. The truck dispatching problem［J］.Management Science,1959, 6 (1): 8091.

　　［2］ SOLOMON M, DESROSIERS J.Time window constrained routing and scheduling problems: a survey［J］.Transportation Science,1988,22(1):113.

　　［3］ NAZIF H, LEE L S. Optimized crossover genetic algorithm for vehicle routing problem with time windows［J］.American Journal of Applied Sciences,2010,7(1):95101.

　　［4］ 王君.带时间窗车辆路径问题的差分进化混合算法［J］. 计算机工程与应用, 2013，49（2）:2428.

　　［5］ HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificialintelligence［M］.Cambridge: University of Michigan Press,1975.

　　［6］ SHAW P. Using constraint programming and local search methods to solve vehicle routing problem［M］. Springer Berlin Heidelberg, 1998, 1520:417431.