物流运输系统中最短路径算法及应用

1、 物流运输系统中最短路径算法及应用摘要：根据GIS中网络计算的实际情况，根据A*算法和Dijkstra算法中快速搜索技术的实现入手，采用最短路径算法结合GIS的方法，提出了一种解决物流运输中车辆路径问题的高效率实现的方法。引言： 在竞争日益激烈的现代商业社会，企业只有以市场为核心去适应不断变化的 环境并及时对市场做出发应，才能在竞争中立于不败之地。物流管理正是以实 现上述要求为目标的。而物流配送是现代化物流管理中的一个重要环节。它是指 按用户的定货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货 人的活动。在物流配送业务中，存在许多优化决策的问题。本文只讨论物流配送 路径优化问题。合

2、理选择配送路径，对加快配送速度、提高服务质量、降低配送 成本以及增加经济效益都有很大影响。 所谓的车辆路径问题（Vehicle Routing Problem）VRP。它也是目前在物流系统中较受关注的一个方面。它是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低。 一、系统介绍求解物流配送路径优化问题的方法有很多是路径引导的功能。本设计主要功能是从给定的车辆位置和多个目标点位置，计算车辆遍历所有目标点的代价最优值，并给出代价值和路径描述，并在地图上进行路径显示。路径引导模块的主要过程：初始化路网-得到车辆信息和目标点信息-求车辆遍历所有目标点的代价最

3、优值和遍历次序（仅求遍历次序，而不需求走什么道路）-求每个目标点遍历的最优路径（求具体的道路）-输出遍历次序和路径描述二、 车辆遍历所有目标点的代价最优值算法本设计中的遍历次序的算法采用的是等代价搜索法，它是A算法的一种简化版本。等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法,它与A算法的 相似之处都是每次只展开某一个结点（不是展开所有结点）,不同之处在于：它不需要去另找专门的估价函数,而是以该结点到A点的距离作为估价值。例如图1，从A点出发，要遍历C,B,D,E四个目标点。具体算法过程如下：图1 起点和遍历目标点图1、 从A点开始依次展开得到AB（7）、AC（3）、AD（10）、

4、AE（15）四个新结点, 把第一层结点A标记为已展开,并且每个新结点要Record下其距离（括号中的数字）; 2、 把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开,即展开AC（3） 结点,得到ACB（8）、ACD（16）、ACE（13）三个结点,并把结点AC标记为已展开;3、 再从未展开的所有结点中找出距离最小的一个展开,即展开AB（7）结点,得到 ABC（12）、ABD（20）、ABE（19）三个结点,并把结点AB标记为已展开; 4、 再次从未展开的所有结点中找出距离最小的一个展开,即展开ACB（8）结点 （不再展开AD、AE）; 5、 每次展开所有未展开的结点中距离最小的那

5、个结点,直到展开的新结点中出现目标Case（结点含有5个字母）时,即得到了Result. 由上可见,A算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点,只是 根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点）,反复下去即可最终得到答案.虽然中途有时也展开了一些并不是答案的结点,但这种展开并不是大规模的,不是全部展开,因而耗时要比宽度优先搜索小得多.三、目标点遍历的最优路径（求具体的道路 3.1 迪杰斯特拉算法在计算两个具体目标点间的具体道路时，本设计采用了迪杰斯特拉算法。在设计中又对迪杰斯特拉算法进行优化，以实现高速公路优先。Dijks

6、tra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1) 初始化。起源点设置为： ds=0, ps为空; 所有其他点: di=, pi=?; 标记起源点s，记k=s,其他所有点设为未标记的。2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：dj=mindj, dk+lkj式中，lkj是从点k到j的直接连接距离。3) 选取下一个点。从所有未标记的结点中，选取dj 中

7、最小的一个i：di=mindj, 所有未标记的点j点i就被选为最短路径中的一点，并设为已标记的。4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j*5) 标记点i。如果，则算法完全推出，否则，记k=i，转到2) 再继续。直到所有点已标记。3.2 本文提出的Dijkstra算法实现 GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归为有向图的特例），且不同的方向可能有不同的权值。更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑。在具体实现时为了能实现高速优先，如果是高速，在标记两点间距离是按实际距离的1/2或1/3来标记，以实现高速优先考虑。在最后算总路程时把它乘上缩小的倍数。即保证总路程不变。本系统利用GPS定位系统实现对物流系统的相关车辆进行监控、调度、指挥、管理，以提高物流业务的效率，有效的控制物流成本，保障司机和货物的安全，提高管理水平和服务质量。系统