摘要:在互联网飞速发展的时代,物流业在我国经济发展中已经是支柱性产业。合理安排车辆的配送路线,可以降低成本,提高经济效益。本文运用蚁群算法求解带时窗的车辆路径问题(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