黄务兰，张　涛

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



基于改进遗传算法的带时间窗车辆路径问题研究*

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

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

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

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

引用格式：黄务兰，张涛. 基于改进遗传算法的带时间窗车辆路径问题研究[J].微型机与应用，2016,35(13)：21-24.

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]。……