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

物流运输系统中最短路径算法及应用物流运输系统中最短路径算法及应用 摘要摘要：根据 GIS 中网络计算的实际情况，根据 A*算法和 Dijkstra 算法中快 速搜索技术的实现入手，采用最短路径算法结合 GIS 的方法，提出了一种解决物流运 输中车辆路径问题的高效率实现的方法。 引言引言： 在竞争日益激烈的现代商业社会，企业只有以市场为核心去适应不断变化的 环境并及时对市场做出发应，才能在竞争中立于不败之地。物流管理正是以实 现上述要求为目标的。而物流配送是现代化物流管理中的一个重要环节。它是指 按用户的定货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货 人的活动。在物流配送业务中，存在许多优化决策的问题。本文只讨论物流配送 路径优化问题。合理选择配送路径，对加快配送速度、提高服务质量、降低配送 成本以及增加经济效益都有很大影响。 所谓的车辆路径问题（Vehicle Routing Problem）VRP。它也是目前在物流系统中较受关注的一个方面。它是指在客户需 求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运 输成本最低。 一、系统介绍一、系统介绍 求解物流配送路径优化问题的方法有很多是路径引导的功能。本设计主要功能 是从给定的车辆位置和多个目标点位置，计算车辆遍历所有目标点的代价最优值， 并给出代价值和路径描述，并在地图上进行路径显示。路径引导模块的主要过程： 初始化路网-得到车辆信息和目标点信息-求车辆遍历所有目标点的代价最优值和 遍历次序（仅求遍历次序，而不需求走什么道路）-求每个目标点遍历的最优路径 （求具体的道路）-输出遍历次序和路径描述 二、二、 车辆遍历所有目标点的代价最优值算法车辆遍历所有目标点的代价最优值算法 本设计中的遍历次序的算法采用的是等代价搜索法，它是 A算法的一种简化 版本。等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法,它与 A算法的 相似之处都是每次只展开某一个结点（不是展开所有结点）,不同之处 在于：它不需要去另找专门的估价函数,而是以该结点到 A 点的距离作为估价值。 例如图 1，从 A 点出发，要遍历 C,B,D,E 四个目标点。具体算法过程如下： 图 1 起点和遍历目标点图 1、 从 A 点开始依次展开得到 AB（7）、AC（3）、AD（10）、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、 每次展开所有未展开的结点中距离最小的那个结点,直到展开的新结点中出现 目标 Case（结点含有 5 个字母）时,即得到了 Result. 由上可见,A算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点,只是 根据某一原则（或某一估价函数值）每次展开距离 A 点最近的那个结点（或是估价 函数计算出的最可能的那个结点）,反复下去即可最终得到答案.虽然中途有时也展 开了一些并不是答案的结点,但这种展开并不是大规模的,不是全部展开,因而耗时要 比宽度优先搜索小得多. 三、目标点遍历的最优路径（求具体的道路三、目标点遍历的最优路径（求具体的道路 3.13.1 迪杰斯特拉算法迪杰斯特拉算法 在计算两个具体目标点间的具体道路时，本设计采用了迪杰斯特拉算法。在设计中 又对迪杰斯特拉算法进行优化，以实现高速公路优先。Dijkstra 算法的基本 思路是：假设每个点都有一对标号 (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 中最小的一个 i： di=mindj, 所有未标记的点 j 点 i 就被选为最短路径中的一点，并设为已标记的。 4) 找到点 i 的前一点。从已标记的点中找到直接连接到点 i 的点 j*，作为前 一点,设置： i=j* 5) 标记点 i。如果，则算法完全推出，否则，记 k=i，转到 2) 再继续。直到所有 点已标记。 3.23.2 本文提出的本文提出的 DijkstraDijkstra 算法实现算法实现 GIS 中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基 本特征的同时，更具有自己在实际中的一些特点。首先，在 GIS 中大多数网络都 是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归 为有向图的特例），且不同的方向可能有不同的权值。更重要的一点是，根据最短 路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必 考虑。在具体实现时为了能实现高速优先，如果是高速，在标记两点间距离是按实 际距离的 1/2 或 1/3 来标记，以实现高速优先考虑。在最后算总路程时把它乘上缩 小的倍数。即保证总路程不变。 本系统利用 GPS 定位系统实现对物流系统的相关车辆进行监控、调度、指挥、管 理，以提高物流业务的效率，有效的控制物流成本，保障司机和货物的安全，提高 管理水