摘要:根据GIS中网络计算的实际情况，根据A*算法和Dijkstra算法中快速搜索技术的实现入手，采用最短路径算法结合GIS的方法，提出了一种解决物流运输中车辆路径问题的高效率实现的方法。

引言:

在竞争日益激烈的现代商业社会，企业只有以市场为核心去适应不断变化的 环境并及时对市场做出发应，才能在竞争中立于不败之地。物流管理正是以实 现上述要求为目标的。而物流配送是现代化物流管理中的一个重要环节。它是指 按用户的定货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货 人的活动。在物流配送业务中，存在许多优化决策的问题。本文只讨论物流配送 路径优化问题。合理选择配送路径，对加快配送速度、提高服务质量、降低配送 成本以及增加经济效益都有很大影响。 所谓的车辆路径问题(Vehicle Routing

Problem)VRP。它也是目前在物流系统中较受关注的一个方面。它是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低。

一、系统介绍

求解物流配送路径优化问题的方法有很多是路径引导的功能。本设计主要功能是从给定的车辆位置和多个目标点位置，计算车辆遍历所有目标点的代价最优值，并给出代价值和路径描述，并在地图上进行路径显示。路径引导模块的主要过程:初始化路网->得到车辆信息和目标点信息->求车辆遍历所有目标点的代价最优值和遍历次序(仅求遍历次序，而不需求走什么道路)->求每个目标点遍历的最优路径(求具体的道路)->输出遍历次序和路径描述

二、 车辆遍历所有目标点的代价最优值算法

本设计中的遍历次序的算法采用的是等代价搜索法，它是A,算法的一种简化版本。等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法,它与A,算法的 相似之处都是每次只展开某一个结点(不是展开所有结点),不同之处在于:

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.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=min,dj, dk+lkj,

式中，lkj是从点k到j的直接连接距离。

3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i: di=min,dj, 所有未标记的点j,

点i就被选为最短路径中的一点，并设为已标记的。

找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前 4)

一点,设置: i=j*

5) 标记点i。如果，则算法完全推出，否则，记k=i，转到2) 再继续。直到所有点已标记。

3.2 本文提出的Dijkstra算法实现

GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向(如果是无向图也可归为有向图的特例)，且不同的方向可能有不同的权值。更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑。在具体实现时为了能实现高速优先，如果是高速，在标记两点间距离是按实际

距离的1/2或1/3来标记，以实现高速优先考虑。在最后算总路程时把它乘上缩小的倍数。即保证总路程不变。

本系统利用GPS定位系统实现对物流系统的相关车辆进行监控、调度、指挥、管理，以提高物流业务的效率，有效的控制物流成本，保障司机和货物的安全，提高管理水平和服务质量。系统的主要功能有:GPS定位，地图与路径显示，路径引导、报警求助，通讯与数据交换，其中路径引导是本系统的关键。路径引导的功能:从给定的多个车辆位置和多个目标点位置，计算车辆遍历所有目标点的代价最优值，并给出代价值和路径描述，在地图上进行路径显示。