摘要:在互联网飞速发展的时代，物流业在我国经济发展中已经是支柱性产业。合理安排车辆的配送路线，可以降低成本，提高经济效益。本文运用蚁群算法求解带时窗的车辆路径问题（VRPTW）。在这个问题中，有一个物流中心，有多辆车向客户点配送货物。相比于其他算法比如遗传算法，蚁群算法的自适应性更强。它利用对信息素的更新，能够主动的去寻找最优路径。

本文将TSP问题、CVRP问题、VRPTW问题结合起来，由简单到复杂逐步加入约束条件，使得蚁群算法能够更好的求解车辆路径问题。首先，简单介绍一下VRP问题并建立CVRP问题的数学模型。其次，在CVRP问题的数学模型的基础上加入时间窗约束条件得到VRPTW问题的数学模型。再次，在TSP问题蚁群算法的概率公式中加入节约值得到CVRP问题的状态转移概率公式。紧接着，在CVRP问题的状态转移概率的公式中加入时间约束值得到VRPTW问题的状态转移公式。再而，查阅2015年云南省各州市的GDP生产总值，分配各州市货物的需求量并测出各州市的坐标点。最后，把坐标点、货物需求量、时间窗值带入matlab代码中运行，求出最短路径。

本文逐步的在蚁群算法中加入约束条件为有效解决VRPTW问题提供了强有力的的工具，对电子商务和物流配送有一定的理论意义和应用价值。

关键词:  旅行商问题；有容量限制的车辆路径问题；信息素；带时窗的车辆路径问题；  蚁群算法

目录

摘要

Abstract

1绪论-1

1.1背景意义-1

1.2国内外研究现状-1

1.2.1国内外对该问题研究的进展-1

1.2.2对国内同类问题的总结-2

1.3本文主要研究的内容与结构-3

1.3.1主要研究内容-3

1.3.2论文结构-3

2 车辆路径问题概述-4

2.1车辆路径问题（VRP）问题-4

2.1.1 VRP问题的概述-4

2.1.2组成物流配送VRP问题的几个主要因素-5

2.2 CVRP问题的数学模型建立-6

2.3 VRPTW问题的数学模型建立-8

2.4 预设条件-9

2.5 VRP问题的求解方法-10

2.6各解法的优缺点-11

3 蚁群算法简介-12

3.1蚁群算法的产生-12

3.2蚁群算法的基本思想-12

3.3 蚁群算法求解TSP问题的思路-14

3.4 基本蚁群算法的流程图-16

3.5 蚁群算法的应用-17

4 基于蚁群算法的VRPTW问题求解-18

4.1 基于TSP问题求解CVRP问题的基本思路-18

4.2 有容量约束车辆路径问题（CVRP）蚁群算法步骤-20

4.2.1算法框架-20

4.3 基于CVRP问题求解VRPTW问题的基本思路-20

4.4  VRPTW问题的算法框架-21

4.4.1算法框架-21

4.5云南省物流车辆的路径问题-22

4.5.1 条件预处理-22

4.5.2 具体要求-22

4.6云南物流车辆路径问题的程序实现-22

4.6.1 相关数据-22

4.4.2 运行结果-24

4.4.3 结果分析-26

结论-27

致谢-28

参考文献-29

附录-30