基于ObjectARX 的物流配送最短路徑實(shí)現(xiàn)方法

唐長(zhǎng)鐵

AutoCAD作為當(dāng)前一種最通用的計(jì)算機(jī)輔助設(shè)計(jì)軟件，在測(cè)繪、規(guī)劃和制圖中得到廣泛應(yīng)用，當(dāng)前幾乎所有的城市規(guī)劃圖都是采用AutoCAD軟件進(jìn)行繪制的。ObjectARX是Autodesk公司針對(duì)AutoCAD平臺(tái)的二次開(kāi)發(fā)推出的一個(gè)功能強(qiáng)大的軟件開(kāi)發(fā)包，它支持面向?qū)ο缶幊?，共享AutoCAD的地址空間，與以往的AutoCAD開(kāi)發(fā)工具AutoLisp和VBA開(kāi)發(fā)的應(yīng)用程序相比，能更快地訪問(wèn)AutoCAD圖形數(shù)據(jù)庫(kù)，大大提高應(yīng)用程序的運(yùn)行速度。

物流配送是現(xiàn)代物流系統(tǒng)的一個(gè)重要環(huán)節(jié)，合理選擇配送路徑，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。本文通過(guò)VC++和ObjectARX的結(jié)合實(shí)現(xiàn)在AutoCAD圖中直接提取道路數(shù)據(jù)，并確定兩點(diǎn)間最短路徑，為物流配送方案提供一種有價(jià)值的選擇。

1 算法基本思路

配送最短路徑的實(shí)現(xiàn)其主要解決的問(wèn)題就是道路數(shù)據(jù)的提取和兩點(diǎn)間最短路徑的確定。在ObjectARX開(kāi)發(fā)環(huán)境中，針對(duì)AutoCAD數(shù)據(jù)庫(kù)中的數(shù)據(jù)對(duì)象都有相應(yīng)的類存在，并且每個(gè)類都封裝了相應(yīng)的屬性和方法供用戶使用，利用相應(yīng)的類就可以實(shí)現(xiàn)在AutoCAD圖中直接提取道路數(shù)據(jù)。兩點(diǎn)最短路徑的確定是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，最短路徑算法有很多種，目前最具有代表性的有Dijkstra算法、A*算法和Floyd算法。本文通過(guò)格式化存儲(chǔ)提取的道路數(shù)據(jù)進(jìn)行相關(guān)運(yùn)算建立道路距離矩陣，改進(jìn)周文峰等提出的最短距離選擇模型，采用Floyd算法，實(shí)現(xiàn)兩點(diǎn)間最短路徑的確定。

2 實(shí)現(xiàn)算法

2.1 道路數(shù)據(jù)提取

AutoCAD是以數(shù)據(jù)庫(kù)的方式組織圖形數(shù)據(jù)的，存儲(chǔ)在數(shù)據(jù)庫(kù)中的數(shù)據(jù)都是以對(duì)象的形式存在。每一個(gè)實(shí)體對(duì)象在創(chuàng)建時(shí)數(shù)據(jù)庫(kù)都會(huì)分配一個(gè)唯一的ID號(hào)，并返回給用戶。通過(guò)使用一個(gè)對(duì)象ID，用戶可以獲得一個(gè)指向一個(gè)實(shí)際數(shù)據(jù)庫(kù)的指針，從而對(duì)對(duì)象執(zhí)行操作。因此通過(guò)獲取道路實(shí)體對(duì)象ID，就可以實(shí)現(xiàn)在道路實(shí)體對(duì)象上提取所需要的數(shù)據(jù)。在AutoCAD數(shù)據(jù)庫(kù)中，所有的可見(jiàn)幾何實(shí)體都存儲(chǔ)在模型空間塊表記錄中，因此只要遍歷這個(gè)塊表記錄便可獲得所有實(shí)體對(duì)象ID。在ObjectARX中，每個(gè)實(shí)體對(duì)象都有相應(yīng)的屬性和方法，利用相應(yīng)的方法就可以提到每個(gè)實(shí)體對(duì)象的坐標(biāo)及其各種屬性。

為了實(shí)現(xiàn)在AutoCAD圖形中直接提取道路，必須要求道路繪制在一個(gè)特定的圖層上，且用多段線繪制，那么提取道路的過(guò)程就是在模型空間塊表記錄中搜尋出處于特定圖層的多段線，然后調(diào)用多段線對(duì)象相應(yīng)的方法來(lái)獲取道路控制點(diǎn)數(shù)據(jù)。實(shí)現(xiàn)步驟如下:

第1步:道路ID的獲取。首先獲取當(dāng)前數(shù)據(jù)庫(kù)的對(duì)象，通過(guò)數(shù)據(jù)庫(kù)對(duì)象得到塊表對(duì)象，然后定義塊表記錄遍歷器，遍歷模型空間塊表記錄所有對(duì)象，獲取處于道路中心線圖層的所有實(shí)體ID。其主要實(shí)現(xiàn)代碼如下:

第2步:獲取道路控制點(diǎn)數(shù)據(jù)。為了建立道路關(guān)系所對(duì)應(yīng)的距離矩陣，需要獲取道路起點(diǎn)、終點(diǎn)、道路轉(zhuǎn)折點(diǎn)以及道路交點(diǎn)。其主要實(shí)現(xiàn)過(guò)程如下:

對(duì)道路轉(zhuǎn)折點(diǎn)的獲取，ObjectARX并沒(méi)有提供相應(yīng)的方法來(lái)實(shí)現(xiàn)，只提供了用來(lái)獲取頂點(diǎn)的方法，但頂點(diǎn)既包括轉(zhuǎn)折點(diǎn)同時(shí)也包括我們所不需要的點(diǎn)。這樣只能通過(guò)利用現(xiàn)有的方法來(lái)間接得到所需要的數(shù)據(jù)點(diǎn)。經(jīng)過(guò)分析發(fā)現(xiàn)在道路轉(zhuǎn)折點(diǎn)處，兩個(gè)方向的直線斜率是不相等的，利用這個(gè)特性，我們通過(guò)排除法就能得到多段線上所有轉(zhuǎn)折點(diǎn)的數(shù)據(jù)。通過(guò)以上兩個(gè)過(guò)程，所有的道路關(guān)鍵點(diǎn)數(shù)據(jù)已經(jīng)存儲(chǔ)到AcGePoint3dArray類型的一維數(shù)組中，其中每元素對(duì)應(yīng)著一條多段線上所有的控制點(diǎn)。

2.2 最短路徑實(shí)現(xiàn)

兩點(diǎn)間最短路徑的確定是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，到目前為止，前人已經(jīng)發(fā)展了多種算法，比較經(jīng)典的算法有Dijkstra算法、A*算法和Floyd算法。周文峰等根據(jù)上述算法提出了最短距離公交出行線路選擇模型，并實(shí)現(xiàn)兩個(gè)站點(diǎn)間最短距離確定。通過(guò)改進(jìn)上述模型如圖1所示，我們實(shí)現(xiàn)了在道路交通網(wǎng)中任意兩控制點(diǎn)間最短距離的確定。

圖1 改進(jìn)的兩點(diǎn)間最短距離確定模型

有了實(shí)現(xiàn)的基本思路后，這部分的主要工作就是在ARX豐富類庫(kù)的基礎(chǔ)上，結(jié)合VC++編程來(lái)完整地實(shí)現(xiàn)上述模型。實(shí)現(xiàn)步驟如下:

第1步:道路數(shù)據(jù)點(diǎn)格式化存儲(chǔ)。

通過(guò)道路數(shù)據(jù)提取，我們獲得了所有多段線的控制點(diǎn)，并將其按行存儲(chǔ)到AcGePoint3dArray類型的一維數(shù)組中。但考慮到這樣一種情況，即兩條多段線的交點(diǎn)有可能處于多段線的起點(diǎn)、終點(diǎn)或轉(zhuǎn)折點(diǎn)處，那么在前面提取到的數(shù)據(jù)點(diǎn)中就會(huì)重復(fù)提取，同時(shí)考慮到后面在建立直達(dá)距離矩陣時(shí)需將所有獲取到的道路數(shù)據(jù)按各自到起點(diǎn)的距離進(jìn)行排序，因此需要對(duì)提取的道路數(shù)據(jù)點(diǎn)進(jìn)行格式化存儲(chǔ)到AcGePoint3dArray數(shù)組中。部分實(shí)現(xiàn)代碼如下:

第2步:建立每條道路的直達(dá)距離矩陣。

利用循環(huán)結(jié)構(gòu)取出ptArray數(shù)組中的任意兩點(diǎn)，通過(guò)ptTotal數(shù)組來(lái)判斷是否是同一條多段線上相鄰兩點(diǎn)，如果是則調(diào)用相應(yīng)多段線求距離方法求出它們間的距離，輸出到直達(dá)距離矩陣中相應(yīng)的位置，如果不相鄰則在相應(yīng)位置輸出一個(gè)無(wú)窮大數(shù)。部分實(shí)現(xiàn)代碼如下:

第3步:構(gòu)造總的直達(dá)距離矩陣。

對(duì)所有多段線直達(dá)距離矩陣相應(yīng)元素進(jìn)行取小運(yùn)算，得到總的直達(dá)距離矩陣totalDistanceMatrix[Max］[Max］(Max為控制點(diǎn)個(gè)數(shù))。

第4步:建立任意兩點(diǎn)間最短距離矩陣。

對(duì)總的直達(dá)距離矩陣使用Floyd算法，得到任意兩點(diǎn)最短距離矩陣weight[Max］[Max］及任意兩點(diǎn)最短距離路線上所經(jīng)過(guò)的前一個(gè)控制點(diǎn)矩陣 path[Max］[Max］。

Floyd(totalDistanceMatrix，Max，weight，path);//調(diào)用 Floyd 算法給出道路控制點(diǎn)中的任意兩點(diǎn)，結(jié)合 weight[Max］[Max］和 path[Max］[Max］，就可以確定兩點(diǎn)間最短路徑依次經(jīng)過(guò)的控制點(diǎn)，也就確定了最短路徑。

3 結(jié)語(yǔ)

本文利用ObjectARX本身具有的技術(shù)特點(diǎn)，開(kāi)發(fā)了相應(yīng)的ARX程序，實(shí)現(xiàn)了在AutoCAD圖形中提取道路數(shù)據(jù)，建立道路交通網(wǎng)的數(shù)據(jù)模型。通過(guò)改進(jìn)的最短距離選擇模型，實(shí)現(xiàn)了任意兩點(diǎn)間最短路徑的確定，從而可以為物流方案的選擇提供一個(gè)有價(jià)值的參考方案。但在實(shí)際中，物流方案的選擇需考慮的因素很多，如交通限制等，因此本程序還有待于進(jìn)一步完善。

[1]李國(guó)泰，王 祎，謝步瀛.圖形區(qū)域操作的ARX關(guān)鍵技術(shù)[J］.東華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，33(3):367-370.

[2]徐 斐.基于VC++和ObjectARX的選線系統(tǒng)的設(shè)計(jì)與開(kāi)發(fā)[J］.蘭州交通大學(xué)學(xué)報(bào)，2010，29(4):53-57.

[3]全思湘，方源敏，程永明.基于ObjectARX.net的面狀符號(hào)自動(dòng)繪制的實(shí)現(xiàn)方法[J］.測(cè)繪通報(bào)，2010(10):50-52.

[4]周文峰，李珍萍，劉洪偉，等.最優(yōu)公交線路選擇問(wèn)題的數(shù)學(xué) 模型及算法[J］.運(yùn)籌與管理，2008，17(5):80-84.