摘 要

随着社会的发着，物流产业在生活中扮演的角色越来越重要。随着中国经济的腾飞和网络技术的快速发展，电子商务的兴起势不可挡。作为电子商务的关联产业，物流配送行业因此比以往在社会、经济领域的影响力与日俱增。随之而来，物流配送路径的优化成为现今社会的一个至关重要的课题。选择合适的路径有利于节省时间和成本，从而更有效率的完成各种配送工作。

本文针对实际的交通道路，将道路的交叉口作为节点并进行标号，两节点之间的道路用边来表示，边长为正常车流速度通过的时间。针对目前大部分城市道路都是单向车道设计有向的路径图，利用智能算法对其进行路径优化。

能对路径进行优化的算法有遗传算法，蚁群算法，粒子群算法，弗洛伊德算法，迪杰斯特拉算法等。本文对建立的道路模型构造有向的邻接矩阵，利用迪杰斯特拉算法算出出发点到终点的最佳路径，通过排列经过的节点表示，并计算出花费的最短时间。

由于课题研究的是实时交通流环境下物流配送路径优化方法，所以邻接矩阵同时也必须是一个路权矩阵。通过设备探测并计算出实时下的交通状况，按一定的标准对路径图中的边长进行换算，利用得到的信息重新安排配送路径。

本文利用C语言进行编程，设计出用迪杰斯特拉算法算出实时交通流情况下的最佳路径。文章通过对武汉某地区的道路进行建模，分别研究正常交通状况下路径优化（即静态，此时路径图为无向的）和实时情况下的路径优化（即动态，此时路径图为有向的）。随机选择出发点和终点，对此数学模型进行仿真得出结果。

关键词：物流配送、实时交通流、路径优化、迪杰斯特拉算法、C语言

ABSTRACT

With the development of society, the logistics industry plays an important role in life increasingly. With the rapid development of Chinese economy and network technology, electronic commerce has a trend which cannot be halted. As a business with electronic commerce, logistics and distribution industry has more influences than ever in the social and economic fields. In the following, the optimization of logistics distribution route has become a very important issue in modern society. Choosing the right path is helpful to save time and cost, so as to complete all kinds of distribution work more efficiently.

This article in view of the actual road traffic, road intersections as nodes and label, the path between two nodes with edges, length of path is the time which car spend in pasting the road at the normal speed. At present, most of the urban roads are one-way lane, design directed path graph, using intelligent algorithms to optimize its path.

Algorithms which can optimize the path has genetic algorithm, ant colony algorithm, particle swarm algorithm, freud algorithm, dijkstra algorithm, etc. The road model directed is established to construct the adjacency matrix, using dijkstra algorithm to calculate the best path from the start point to the end by arranging the nodes that pass through and calculate the cost of the shortest time

Because the research of logistics distribution path optimization method under the real-time traffic flow the environment , so the adjacency matrix must be a matrix as to. Detecting and calculating the real-time traffic conditions through equipment.

According to certain standards of path in a graph in which the length of conversion of re arrange the delivery path using information obtained, convering the length of paths in the graph according to certain standards, using the information to arrange the delivery path again.

In this paper, we use dijkstra algorithm to design the optimal path under the real time traffic flow through the C programming language. Based on modeling the road to a certain area in Wuhan, respectively, of normal traffic (routing is static, then path diagram for undirected) and real-time path optimization (i.e. dynamic. At this time path graph for directed).Selecting the start point and end point of randomly, the mathematical model simulation results.

Key words: logistics distribution, real time traffic flow, path optimization, dijkstra algorithm, C language.

目录

第1章 绪论 1

1.1研究背景与目的 1

1.2国内外研究现状 1

1.3研究内容与意义 2

1.4预期目标 2

第2章 问题分析与算法选择 4

2.1问题分析 4

2.2各种算法介绍 4

2.2.1弗洛伊德算法 4

2.2.2粒子群算法 5

2.2.3蚁群算法 6

2.2.4遗传算法 6

2.3迪杰斯特拉算法介绍 8

2.4算法选择 10

第3章 物流配送路径的相关知识了解 12

3.1武汉市交通现状和特点 12

3.2配送路径问题分析 12

3.3图论与路径优化 13

3.3.1图的介绍 13

3.3.2图的分类与相应邻接矩阵的形成 13

第4章 基于迪杰斯特拉算法的路径优化 15

4.1静态路网信息 15

4.2动态路网信息 16

第5章 程序实现与运行结果 19

5.1图的变量类型 19

5.2构造路权矩阵 19

5.3迪杰斯特拉算法的实现 21

5.4运行结果 23

第6章 静态配送路径优化与动态配送路径优化的比较 26

6.1静态配送路径与动态配送路径的不同 26

6.2静态配送路径优化的优点与不足 26

6.3动态配送路径优化的优点和不足 26

第7章 总结 28

参考文献 29

附录 30

致谢 34

第1章 绪论

1.1研究背景与目的

伴随着中国市场经济的跨越式发展，如今物流行业比以往任何一个时期都要兴盛。按照社会的发展，物流在将来人们生活中的地位必将不断提升。计算机技术和信息技术的不断革新促进了电子商务等行业的发展的同时也促进了物流行业的繁荣。

物流这个行业简单来说是一个有关分派，调度，送货的行当。在这行业中，送货的运输成本占据了整个物流业总成本很大比重。缩短运输距离对于行业的发展和国家经济的发展有着重要意义。鉴于发达国家在运输调度上的合理分配，我国在相关方面还有许多工作需要做。如果我国想在经济领域上迎头赶上，物流配送这一行业值得我们花费大力气去研究。优化物流配送路径是一项与创新发展，绿色发展，可持续发展息息相关的工作。