车辆最短路径问题研究

菜单

摘要:物流系统有五个要素：运输距离、运输环节、运输工具、运输时间和运输费用。其中运输路径化是一个重要的问题，也是实际过程中比较难解决的问题。本文针对物流系统送货的重点——车辆路径问题进行研究研究，建立了物流系统送货的路径优化问题的数学模型，并在动态规划算法的基础上进行优化与改进，经过改进的算法能够最大限度的缩短车辆运输的路径与提高车辆的运载量，减少车辆发货的车次，极大的提高效益,在实际生活中取得了不错的效果。54205

毕业论文关键词:物流系统，车辆最短路径，动态规划

Abstract: Logistics system has five elements: transportation distance, transportation, transport, transport time and transport cost. Transportation is an important problem, and it is also difficult to solve in the process of the actual problem. To the point of delivery - logistics system to study the vehicle routing problem research, this article is to establish the mathematical model of logistics delivery path optimization problem, and on the basis of dynamic programming algorithm is optimized and improved, and the improved algorithm can maximize the reduction of the vehicle transport path and improves vehicle carrying capacity, reduces vehicle delivery number and greatly increases the efficiency, then achieves good effect in actual life.

Keyword: logistics system, vehicle shortest path, dynamic programming

0 引言…4

1 车辆路径问题…4

2 车辆路径问题的难点与解决方法…4

2.1 车辆路径问题的难点…4

2.2 车辆路径问题的方法…5

2.2.1 分支界限法5

2.2.2 模拟火退法6

2.2.3 蚁群算法…6

2.2.4 动态规划…6

3 改进的动态规划求解车辆最短路径问题 …6

3.1 问题描述 6

3.2 问题分析 7

3.3 算法设计 7

3.4 建立模型 9

3.5 应用实例…10

结论12参考文献13

致谢14

0 引言

随着现代经济的不断发展，全球化经济面临着巨大挑战，很多国家经济发展都处在一个非常尴尬的位置，而我国却找到了机遇和发展的机会，许多产业都大势已去，没有剩余价值可捞，遭遇行业洗牌。而物流业却是一个非常好的发展机遇，在这机遇中也蕴含着挑战。在激烈的市场竞争中要站稳脚跟，必须力求用最小的代价取得利益最大化。由于物流系统中运输占据着很大的比例，所以我们对物流运输的损耗很关心。影响物流运输合理化的因素很多，其中起决定作用的有五个方面，称作合理运输的“五要素” ──运输距离、运输环节、运输工具、运输时间、运输费用。只有将五要素处理好了，经济就能更快发展。

本文研究的是五要素其中之一──运输距离的问题，车辆走的路径短了那么效益也就上来了。以前很多人用蚁群算法做的，我在这基础上又以动态规划来进行解析，进行优化提出车辆最短路径问题，使得论文的结果不仅仅限于物流业，对快递业也有相同作用。车辆最短路径问题及其现代解决方法。

1 车辆路径问题

1959年Dantzig和Ramse首次对闭合式VRP进行了研究，描述的是将汽油送往各个加油站的实际问题，并首次提出了相应的数学规划模型以及求解算法，这问题很快引起了组合数学、运筹学、计算机应用等学科专家的极大重视。车辆问题的定义一般是：它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。本文研究的车辆最短路径问题是其的一个重要分支。