论文总字数：8362字

摘 要

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

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

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

车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下：

设有一个起始站，共有 辆货车，车辆容量为，有位顾客，每位顾客的需求量为。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

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

2.1 车辆路径问题的难点

对于解决车辆路径问题有一个难题，那就是NP完全问题，NP问题是世界七大数学难题之一。NP问题是指可以在多项式的时间里猜出一个解的问题，简单来说就是多项式复杂程度的非确定性问题。NP问题通常有个算法，它不可以直接告诉你答案是什么，但是能告诉你，某个可能的结果是正确的还是错误的。这个能告诉你“猜算”的答案正确与否的算法，如果可以在多项式时间内算出来，就可以叫做多项式非确定性问题。但如果这个问题的所有可能性答案，都是能够在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。

完全多项式非确定性问题可以用穷举法得到答案，一个一个的检验下去，最终能够得到结果。但是这样算法的复杂程度是指数关系，因此计算的时间随着问题的复杂程度成指数的增长，很快便变得不可以计算了。而车辆路径问题就属于一种NP问题。

剩余内容已隐藏，请支付后下载全文，论文总字数：8362字