带时间窗的物流配送车辆路径问题研究.docx

摘要:车辆路径问题（vehicle routing problem，VRP）的研究最早由Dantzing等于1959年提出，旨在构造适当的车辆行驶路线来实现运输成本的最优化。随着社会经济的快速发展和世界经济一体化进程的加快，特别是电子商务和物流业的快速发展，VRP已经从最初的简单车辆运输演变为一个复杂约束的车辆路径问题，并且产生了许多研究分支，具有时间窗口的车辆路径问题（VRPTW），旨在提高服务质量。增加时间窗后，VRP问题的计算难度和复杂度大大增加。除了考虑VRP问题的空间路径之外，考虑时间表也是必要的，它已引起国内外众多学者的关注，成为VRP研究中最受欢迎的研究方向之一。

为了减少交货时间，本文研究了带时间窗的物流配送车辆路径问题并建立一个整数规划模型。为了加快遗传算法的收敛速度和优化能力，提出一种带有局部搜索的改进遗传算法IGALS( Improved Genetic Algorithm with Local Search)。改进的算法借用精英预订策略，使用的交叉算子结合了点交叉和分段交叉，并提出路段允许延迟的时间概念，并使用局部搜索策略来提高解决方案的质量。

关键词：VRPTW；遗传算法；交叉算子；局部搜索策略；优化改进

目录

摘要

Abstract

1绪论-1

1.1 研究背景与意义-1

1.2国内外发展现状-2

1.2.1国外研究发展-2

1.2.2国内研究发展现状-2

1.3本课题最终目标-3

1.4研究的思路及框架-3

1.5本章小节-3

2带时间窗物流配送车辆路径问题建模-4

2.1问题描述-4

2.2模型假设-4

2.3符号说明-5

2.4模型建立-6

2.4.1目标函数-6

2.4.2限制约束条件-6

3带时间窗物流配送车辆路径问题的求解方法-8

3.1遗传算法介绍-8

3.2算法改进设计-13

3.3本章小结-16

4仿真实验分析与结论-17

4.1数据介绍-17

4.2 实验结果及分析-17

4.3本章小结-19

结    论-20

参 考 文 献-21

致    谢-22