摘要:根據(jù)GIS中網(wǎng)絡(luò)計(jì)算的實(shí)際情況，根據(jù)A*算法和Dijkstra算法中快速搜索技術(shù)的實(shí)現(xiàn)入手，采用最短路徑算法結(jié)合GIS的方法，提出了一種解決物流運(yùn)輸中車輛路徑問(wèn)題的高效率實(shí)現(xiàn)的方法。

引言:

在競(jìng)爭(zhēng)日益激烈的現(xiàn)代商業(yè)社會(huì)，企業(yè)只有以市場(chǎng)為核心去適應(yīng)不斷變化的 環(huán)境并及時(shí)對(duì)市場(chǎng)做出發(fā)應(yīng)，才能在競(jìng)爭(zhēng)中立于不敗之地。物流管理正是以實(shí) 現(xiàn)上述要求為目標(biāo)的。而物流配送是現(xiàn)代化物流管理中的一個(gè)重要環(huán)節(jié)。它是指 按用戶的定貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送交收貨 人的活動(dòng)。在物流配送業(yè)務(wù)中，存在許多優(yōu)化決策的問(wèn)題。本文只討論物流配送 路徑優(yōu)化問(wèn)題。合理選擇配送路徑，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送 成本以及增加經(jīng)濟(jì)效益都有很大影響。 所謂的車輛路徑問(wèn)題(Vehicle Routing

Problem)VRP。它也是目前在物流系統(tǒng)中較受關(guān)注的一個(gè)方面。它是指在客戶需求位置已知的情況下，確定車輛在各個(gè)客戶間的行程路線，使得運(yùn)輸路線最短或運(yùn)輸成本最低。

一、系統(tǒng)介紹

求解物流配送路徑優(yōu)化問(wèn)題的方法有很多是路徑引導(dǎo)的功能。本設(shè)計(jì)主要功能是從給定的車輛位置和多個(gè)目標(biāo)點(diǎn)位置，計(jì)算車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值，并給出代價(jià)值和路徑描述，并在地圖上進(jìn)行路徑顯示。路徑引導(dǎo)模塊的主要過(guò)程:初始化路網(wǎng)->得到車輛信息和目標(biāo)點(diǎn)信息->求車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值和遍歷次序(僅求遍歷次序，而不需求走什么道路)->求每個(gè)目標(biāo)點(diǎn)遍歷的最優(yōu)路徑(求具體的道路)->輸出遍歷次序和路徑描述

二、 車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值算法

本設(shè)計(jì)中的遍歷次序的算法采用的是等代價(jià)搜索法，它是A,算法的一種簡(jiǎn)化版本。等代價(jià)搜索法也是基于寬度優(yōu)先搜索上進(jìn)行了部分優(yōu)化的一種算法,它與A,算法的 相似之處都是每次只展開(kāi)某一個(gè)結(jié)點(diǎn)(不是展開(kāi)所有結(jié)點(diǎn)),不同之處在于:

1、 從A點(diǎn)開(kāi)始依次展開(kāi)得到AB(7)、AC(3)、AD(10)、AE(15)四個(gè)新結(jié)點(diǎn),

把第一層結(jié)點(diǎn)A標(biāo)記為已展開(kāi),并且每個(gè)新結(jié)點(diǎn)要Record下其距離(括號(hào)中的

數(shù)字);

2、 把未展開(kāi)過(guò)的AB、AC、AD、AE四個(gè)結(jié)點(diǎn)中距離最小的一個(gè)展開(kāi),即展開(kāi)AC(3)

得到ACB(8)、ACD(16)、ACE(13)三個(gè)結(jié)點(diǎn),并把結(jié)點(diǎn)AC標(biāo)記為已結(jié)點(diǎn),

展開(kāi);

3、 再?gòu)奈凑归_(kāi)的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開(kāi),即展開(kāi)AB(7)結(jié)點(diǎn),得到

ABC(12)、ABD(20)、ABE(19)三個(gè)結(jié)點(diǎn),并把結(jié)點(diǎn)AB標(biāo)記為已展開(kāi); 4、 再次從未展開(kāi)的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開(kāi),即展開(kāi)ACB(8)結(jié)點(diǎn)… …

(不再展開(kāi)AD、AE);

5、 每次展開(kāi)所有未展開(kāi)的結(jié)點(diǎn)中距離最小的那個(gè)結(jié)點(diǎn),直到展開(kāi)的新結(jié)點(diǎn)中出現(xiàn)目

標(biāo)Case(結(jié)點(diǎn)含有5個(gè)字母)時(shí),即得到了Result. 由上可見(jiàn),A,算法和等代價(jià)搜索法并沒(méi)有象寬度優(yōu)先搜索一樣展開(kāi)所有結(jié)點(diǎn),只是 根據(jù)某一原則(或某一估價(jià)函數(shù)值)每次展開(kāi)距離A點(diǎn)最近的那個(gè)結(jié)點(diǎn)(或是估價(jià)函數(shù)計(jì)算出的最可能的那個(gè)結(jié)點(diǎn)),反復(fù)下去即可最終得到答案.雖然中途有時(shí)也展開(kāi)了一些并不是答案的結(jié)點(diǎn),但這種展開(kāi)并不是大規(guī)模的,不是全部展開(kāi),因而耗時(shí)要比寬度優(yōu)先搜索小得多.

三、目標(biāo)點(diǎn)遍歷的最優(yōu)路徑(求具體的道路

3.1 迪杰斯特拉算法

在計(jì)算兩個(gè)具體目標(biāo)點(diǎn)間的具體道路時(shí)，本設(shè)計(jì)采用了迪杰斯特拉算法。在設(shè)計(jì)中

又對(duì)迪杰斯特拉算法進(jìn)行優(yōu)化，以實(shí)現(xiàn)高速公路優(yōu)先。Dijkstra算法的基本思

路是:假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào) (dj, pj)，其中dj是從起源點(diǎn)s到點(diǎn)j的最

短路徑的長(zhǎng)度 (從頂點(diǎn)到其本身的最短路徑是零路(沒(méi)有弧的路)，其長(zhǎng)度等于

零);pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的

最短路徑算法的基本過(guò)程如下:

1) 初始化。起源點(diǎn)設(shè)置為:? ds=0, ps為空;? 所有其他點(diǎn): di=?, pi=?;

? 標(biāo)記起源點(diǎn)s，記k=s,其他所有點(diǎn)設(shè)為未標(biāo)記的。

2) 檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置: dj=min,dj, dk+lkj,

式中，lkj是從點(diǎn)k到j(luò)的直接連接距離。

3) 選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj 中最小的一個(gè)i: di=min,dj, 所有未標(biāo)記的點(diǎn)j,

點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。

找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i的點(diǎn)j*，作為前 4)

一點(diǎn),設(shè)置: i=j*

5) 標(biāo)記點(diǎn)i。如果，則算法完全推出，否則，記k=i，轉(zhuǎn)到2) 再繼續(xù)。直到所有點(diǎn)已標(biāo)記。

3.2 本文提出的Dijkstra算法實(shí)現(xiàn)

GIS中的網(wǎng)絡(luò)一般為各種道路、管網(wǎng)、管線等，這些網(wǎng)絡(luò)在具有圖理論中的基本特征的同時(shí)，更具有自己在實(shí)際中的一些特點(diǎn)。首先，在GIS中大多數(shù)網(wǎng)絡(luò)都是有向帶權(quán)圖，如道路有單雙向問(wèn)題，電流、水流都有方向(如果是無(wú)向圖也可歸為有向圖的特例)，且不同的方向可能有不同的權(quán)值。更重要的一點(diǎn)是，根據(jù)最短路徑算法的特性可以知道，頂點(diǎn)的出度是個(gè)重要指標(biāo)，但是其入度在算法里則不必考慮。在具體實(shí)現(xiàn)時(shí)為了能實(shí)現(xiàn)高速優(yōu)先，如果是高速，在標(biāo)記兩點(diǎn)間距離是按實(shí)際

距離的1/2或1/3來(lái)標(biāo)記，以實(shí)現(xiàn)高速優(yōu)先考慮。在最后算總路程時(shí)把它乘上縮小的倍數(shù)。即保證總路程不變。

本系統(tǒng)利用GPS定位系統(tǒng)實(shí)現(xiàn)對(duì)物流系統(tǒng)的相關(guān)車輛進(jìn)行監(jiān)控、調(diào)度、指揮、管理，以提高物流業(yè)務(wù)的效率，有效的控制物流成本，保障司機(jī)和貨物的安全，提高管理水平和服務(wù)質(zhì)量。系統(tǒng)的主要功能有:GPS定位，地圖與路徑顯示，路徑引導(dǎo)、報(bào)警求助，通訊與數(shù)據(jù)交換，其中路徑引導(dǎo)是本系統(tǒng)的關(guān)鍵。路徑引導(dǎo)的功能:從給定的多個(gè)車輛位置和多個(gè)目標(biāo)點(diǎn)位置，計(jì)算車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值，并給出代價(jià)值和路徑描述，在地圖上進(jìn)行路徑顯示。