基于ObjectARX 的物流配送最短路徑實現方法

唐長鐵

AutoCAD作為當前一種最通用的計算機輔助設計軟件，在測繪、規劃和制圖中得到廣泛應用，當前幾乎所有的城市規劃圖都是采用AutoCAD軟件進行繪制的。ObjectARX是Autodesk公司針對AutoCAD平臺的二次開發推出的一個功能強大的軟件開發包，它支持面向對象編程，共享AutoCAD的地址空間，與以往的AutoCAD開發工具AutoLisp和VBA開發的應用程序相比，能更快地訪問AutoCAD圖形數據庫，大大提高應用程序的運行速度。

物流配送是現代物流系統的一個重要環節，合理選擇配送路徑，對加快配送速度、提高服務質量、降低配送成本及增加經濟效益都有較大影響。本文通過VC++和ObjectARX的結合實現在AutoCAD圖中直接提取道路數據，并確定兩點間最短路徑，為物流配送方案提供一種有價值的選擇。

1 算法基本思路

配送最短路徑的實現其主要解決的問題就是道路數據的提取和兩點間最短路徑的確定。在ObjectARX開發環境中，針對AutoCAD數據庫中的數據對象都有相應的類存在，并且每個類都封裝了相應的屬性和方法供用戶使用，利用相應的類就可以實現在AutoCAD圖中直接提取道路數據。兩點最短路徑的確定是計算機科學與地理信息科學等領域研究的熱點，最短路徑算法有很多種，目前最具有代表性的有Dijkstra算法、A*算法和Floyd算法。本文通過格式化存儲提取的道路數據進行相關運算建立道路距離矩陣，改進周文峰等提出的最短距離選擇模型，采用Floyd算法，實現兩點間最短路徑的確定。

2 實現算法

2.1 道路數據提取

AutoCAD是以數據庫的方式組織圖形數據的，存儲在數據庫中的數據都是以對象的形式存在。每一個實體對象在創建時數據庫都會分配一個唯一的ID號，并返回給用戶。通過使用一個對象ID，用戶可以獲得一個指向一個實際數據庫的指針，從而對對象執行操作。因此通過獲取道路實體對象ID，就可以實現在道路實體對象上提取所需要的數據。在AutoCAD數據庫中，所有的可見幾何實體都存儲在模型空間塊表記錄中，因此只要遍歷這個塊表記錄便可獲得所有實體對象ID。在ObjectARX中，每個實體對象都有相應的屬性和方法，利用相應的方法就可以提到每個實體對象的坐標及其各種屬性。

為了實現在AutoCAD圖形中直接提取道路，必須要求道路繪制在一個特定的圖層上，且用多段線繪制，那么提取道路的過程就是在模型空間塊表記錄中搜尋出處于特定圖層的多段線，然后調用多段線對象相應的方法來獲取道路控制點數據。實現步驟如下:

第1步:道路ID的獲取。首先獲取當前數據庫的對象，通過數據庫對象得到塊表對象，然后定義塊表記錄遍歷器，遍歷模型空間塊表記錄所有對象，獲取處于道路中心線圖層的所有實體ID。其主要實現代碼如下:

第2步:獲取道路控制點數據。為了建立道路關系所對應的距離矩陣，需要獲取道路起點、終點、道路轉折點以及道路交點。其主要實現過程如下:

對道路轉折點的獲取，ObjectARX并沒有提供相應的方法來實現，只提供了用來獲取頂點的方法，但頂點既包括轉折點同時也包括我們所不需要的點。這樣只能通過利用現有的方法來間接得到所需要的數據點。經過分析發現在道路轉折點處，兩個方向的直線斜率是不相等的，利用這個特性，我們通過排除法就能得到多段線上所有轉折點的數據。通過以上兩個過程，所有的道路關鍵點數據已經存儲到AcGePoint3dArray類型的一維數組中，其中每元素對應著一條多段線上所有的控制點。

2.2 最短路徑實現

兩點間最短路徑的確定是計算機科學與地理信息科學等領域研究的熱點，到目前為止，前人已經發展了多種算法，比較經典的算法有Dijkstra算法、A*算法和Floyd算法。周文峰等根據上述算法提出了最短距離公交出行線路選擇模型，并實現兩個站點間最短距離確定。通過改進上述模型如圖1所示，我們實現了在道路交通網中任意兩控制點間最短距離的確定。

圖1 改進的兩點間最短距離確定模型

有了實現的基本思路后，這部分的主要工作就是在ARX豐富類庫的基礎上，結合VC++編程來完整地實現上述模型。實現步驟如下:

第1步:道路數據點格式化存儲。

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

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

利用循環結構取出ptArray數組中的任意兩點，通過ptTotal數組來判斷是否是同一條多段線上相鄰兩點，如果是則調用相應多段線求距離方法求出它們間的距離，輸出到直達距離矩陣中相應的位置，如果不相鄰則在相應位置輸出一個無窮大數。部分實現代碼如下:

第3步:構造總的直達距離矩陣。

對所有多段線直達距離矩陣相應元素進行取小運算，得到總的直達距離矩陣totalDistanceMatrix[Max］[Max］(Max為控制點個數)。

第4步:建立任意兩點間最短距離矩陣。

對總的直達距離矩陣使用Floyd算法，得到任意兩點最短距離矩陣weight[Max］[Max］及任意兩點最短距離路線上所經過的前一個控制點矩陣 path[Max］[Max］。

Floyd(totalDistanceMatrix，Max，weight，path);//調用 Floyd 算法給出道路控制點中的任意兩點，結合 weight[Max］[Max］和 path[Max］[Max］，就可以確定兩點間最短路徑依次經過的控制點，也就確定了最短路徑。

3 結語

本文利用ObjectARX本身具有的技術特點，開發了相應的ARX程序，實現了在AutoCAD圖形中提取道路數據，建立道路交通網的數據模型。通過改進的最短距離選擇模型，實現了任意兩點間最短路徑的確定，從而可以為物流方案的選擇提供一個有價值的參考方案。但在實際中，物流方案的選擇需考慮的因素很多，如交通限制等，因此本程序還有待于進一步完善。

[1]李國泰，王 祎，謝步瀛.圖形區域操作的ARX關鍵技術[J］.東華大學學報(自然科學版)，2007，33(3):367-370.

[2]徐 斐.基于VC++和ObjectARX的選線系統的設計與開發[J］.蘭州交通大學學報，2010，29(4):53-57.

[3]全思湘，方源敏，程永明.基于ObjectARX.net的面狀符號自動繪制的實現方法[J］.測繪通報，2010(10):50-52.

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