1、Good is good, but better carries it.精益求精，善益求善。一種解決地下礦山車隊管理問題的最短路徑算法-Ashortest-pathalgorithmforsolvingthefleetmanagementprobleminundergroundminesMichelGamache,RenaudGrimard,PaulCohenEuropeanJournalofOperationalResearch,2004,166(2005):497506一種解決地下礦山車隊管理問題的最短路徑算法翻譯：二一三年十月摘要：本文通過對地下礦山鏟運機（LHD）車隊管理問題的研究，基

2、于最短路徑算法，解決了車輛新任務調度、路徑選擇和行程安排等問題。每一決策，須考慮礦山現狀、運輸網絡中所有單線雙向路段的交通現狀和實際運行中的制約因素。如無論鏟運機前進或后退，都須保證鏟斗能在靈活裝卸。關鍵詞：車隊管理，調度，路徑選擇，行程安排，地下開采1引言在地下開采中，一個主要的基礎設施成本涉及巷道開拓的挖掘工程。巷道構成了運輸網絡的基礎，是采礦作業必不可少的條件。因此，在規劃階段，采礦工程師設法盡可能多的減少巷道開拓，從而創造出幾乎僅由單線雙向路段構成的緊湊運輸網絡。此外，為了限制額外空間的需要，地下礦井往往選擇鏟運機型車隊來完成在裝載點和卸載點之間的裝載、運輸和傾倒礦石、廢石及回填材料的

3、工作。在這種有限的網絡中，鏟運機必須共用路段。這種情況導致一個有效的車隊管理系統的必要性。在由車隊管理系統做出的決定中，一個就是每次都能為基本上已裝載或傾倒完物料的鏟運機選擇一個新的目的地從而形成一個新的有效的任務。該調度決策基于一個預先確定的標準：最大限度減少周期時間，最大限度減少等待時間或空閑時間等。此外，調度決策必須考慮到交通，即網絡上運行的其他鏟運機，從而全局性地改善車輛的機動性和隱性地提高整個作業效率。因此，這項任務不僅包括從起點到終點的車輛調度，還包括為這些車輛尋找路徑，以避免在裝載點或卸載點發生碰撞，排隊等候以及死鎖條件。由于這些困難與運輸網絡的性質有關，目前幾乎所有的地下礦山，

4、鏟運機是在起點或終點的轉變開始時預先分配的。起點與終點之間的路徑總是相同的，車輛在路口的優先權是以操作者管理的一系列規則為基礎（例如先進，先出）和/或由交通信號燈管理。這樣的操作條件較簡單，但并不適用于所有由環境決定的潛在情況。鑒于鏟運機必須在一些裝載點和交叉路口等待而其他一些裝載點此時正好可以使用，可見生產率是可以提高的。基于上述考慮，地下礦山車隊管理決策包括三個主要組成部分：調度，路徑選擇和行程安排。該行程安排的目的是為一輛或多輛鏟運機選擇一個新的目的地（裝載或卸載點）。路徑選擇包括在起點到終點之間選擇最佳路線（路段）。最后，調度包括決定車輛在運輸區段上的運行速度和輪候時間，以避免車輛之間

5、的沖突。為了實現最優決策，在一個特定的問題中這三個組成部分必須同時解決。本文依據露天礦山調度和自行搬運車（AGV）管理系統的開發思想提出了一種同時處理這三個組成部分的一體化解決方案。文章第2節介紹已出版的前人的著作。第3節詳細介紹所提方案的內容。最后，第4節介紹該方法的擴展延伸。2前人工作露天礦已經使用調度系統近30年。由于監測系統的可用性以及露天礦調度問題的每個決策不需要考慮路徑選擇和行程安排的事實而使這種系統的使用變得簡單。Munirathinam和Yingling在1994年提出了露天礦山調度系統的調查研究。他們的結論之一是調度系統應以計劃驅動策略為基礎。計劃驅動系統由兩部分組成。其中之

6、一是通過求解一個線性或非線性的數學模型來設立一個最優生產計劃。該計劃表明，對于每一種類型的材料，在來源地和目的地之間的運輸都應該保證生產能力最大化或運輸成本最小化。它還需遵守調配和容量方面的限制。計劃驅動系統的第二個組成部分是如何調度卡車駛向鏟裝設備，以盡量減少實際生產率與第一個組成部分所確立的生產計劃之間的偏差。為了有效率，計劃驅動系統必須經常更新，因為開采狀況隨著輪班持續變化。計劃驅動策略也應是地下礦井調度系統的一部分。只有少數文章涉及地下開采運輸車隊管理系統的問題。其中，NikosVagenas于1991年曾從事半自動鏟運機（RAL，即自動運行但必需人工裝載和傾倒）的管理。該系統采用最短

7、路徑算法來選擇起點到終點的最優路線，并采用不同的算法來控制網絡沖突。由Vagenas提出的這個分配方法非常適合在地下礦山使用。該方法考慮到網絡上的車輛之間的關系，以兩個模塊為基礎。第一個，關于半自動鏟運機的運輸路徑選擇，依據四個算法：一是從起點到終點尋找允許使用的最短路徑，二是用于在車輛必須減速時的監測，三是為解決雙向沖突，四是穿越交通分區。第二個模塊，即調度模塊，采用啟發式程序為半自動鏟運機確定目的地。車輛定位是提到的一個問題，但沒有提供如何解決的資料。地下礦山車隊管理呈現出與制造業背景的自行搬運車管理的相似性。Kim和Tanchoco于1991年提出一種似乎特別適合地下礦山車隊管理需要的方

8、法。他們提出了一個有效的算法來為在由雙向路段組成的運輸網絡中運行的自行搬運車尋找無沖突最短時間路線。路由和調度方面的問題同時解決，但車輛的目的地是首先選擇好的。這種解決方案包括在時間窗口圖上尋找一條最短路徑，該圖則是根據網絡中當前和未來的交通情況而確定，即需要知道網絡中其他車輛的路線以及在何時哪些路口是可以通過的。在圖中，一個節點代表運輸網絡的一個交叉路口而一個時窗則顯示在此時相應的路口是空閑的。弧集表示空閑時窗之間的可行鏈接。在創建圖表時，對每一個可行的弧線進行測試，以避免路段上的追尾和迎面沖突。在從一個原點到目的地的任何路徑上節點代表一個無沖突點。最優可行路線是通過Dijkstra最短路徑

9、算法找出的。為了避免在涉及找尋可行弧時不必要的計算，時間窗口圖不顯式構造，而是在主程序執行時隱含考慮。這種方法是對沖突檢測的一個重大改進。雙向路段的使用，使該方法比之前提出的任何方法更切合實際，更適合地下礦井。然而，制造業和采礦環境之間依然存在重要差別。首先，地下礦井周期的變化不能像制造業一樣比較容易地允許作業執行計劃。裝載時間顯示了最廣泛的不同特點，由于這樣的事實，即在鏟運機前的散狀物料需要多次調整前斗進行裝載。搬運和傾倒時間的不同則明顯減少。為使該方法適用于地下礦山環境，則要求根據操作進度來適時調整時間窗口圖。這個問題在第4節討論。第二個重要的區別是有關在兩種環境下使用的車輛類型。鏟運機可

10、以前進，后退，但在裝載和傾倒階段其鏟斗只能位于車體前方。自行搬運車則不存在這個問題。然而，對于鏟運機來說，預先計劃從起點到目的地的輪流運行秩序，以確保車輛能準確到達，是車隊管理系統的一個本質特征。此問題的解決方法在第3節中討論。Krishnamurthy等人于1993年依據一系列解決自行搬運車管理問題的生產技術提出了一種方法。他們的解決方案考慮了同時進行對多個自行搬運車的任務分配。有趣的是，在一個限制只有幾秒鐘的時間允許決策過程的實際情況下，該方法是不適用的。然而，他們圖形構成的一些內容將在本文提出的方法中重新使用。Langevin等人于1994年也提出了一個最佳和更具全局性的方法：同時安排兩

11、輛自行搬運車，但再次因為決策過程太長而不能在實時系統中運用。此外，這種方法為所有在輪班過程中執行的任務找到了最優排序，由于前面提到的操作具有一定的隨機性，所以在我們的文章中也存在一些不恰當之處。3解決方案這里提出的解決方案受到了Kim和Tanchoco（1991）所提出的方法的啟發，也包括一些由Vagenas（1991）和Krishnamurthy（1993）等人提出的圖形設計的內容。提出這種方法，是因為在類似的解決方案中它能解決路徑選擇和調度方面的問題。該模型已進行了調整，將調度決策包含到相同的解決過程中。然而，對網絡提出了重要變化，以確保鏟運機用正確的方向（鏟斗在前）到達目的地，并減少死鎖

12、的發生。3.1圖形構成從礦場的初始運輸網絡開始，基本的網絡代表路段（弧），交叉口、卸載和裝載點（節點）一一繪制。表示交叉點的節點是重復設置的，以表明在這些地點（路段的端點）車輛可以安全地等待其他車輛行進到相鄰的路段（參見圖1）。在地下礦井中，這些節點扮演另一個重要角色：在其所代表的地區車輛可以改變方向，即從正向變為反向運動。根據網絡上的其他鏟運機的位置和任務，一個時間窗口圖便可以推算出來。圖2給出了對應于圖1所示運輸網絡的一個簡化時間窗口圖形例子。對應于某特定車輛的路徑“K-J-H-I-L-M-N-O-Q”用黑色表示。黑色矩形表示節點被占用的時間段，弧代表路徑上的路段；例如從“K”到“J”的弧

13、表示該車輛使用路段“KJ”。圖1.基本網絡對于每一個節點，一個白色的空間表示一個時間窗口，在此時窗內，節點（路口）是空閑的。兩條路徑不能同時占用同一個節點。弧線與時窗連接在一起表示一個路段的使用是安全可行的。已經做過相應測試，以確保節點之間有一條物理鏈路，以確保第二個時間窗口可以及時到達，以及避免在一條弧段發生迎面碰撞或追尾（當兩弧交叉且使用相同的節點對時可能發生這樣的沖突）。Kim和Tanchoco（1991）已對這些測試的更多細節進行過表述。圖2.時間窗口網格圖圖中第二條通路“R-P-N-M-L-I-H-D-B-C-G”與灰色矩形連接在一起表示一條無沖突途徑。該路徑是眾多可行路線中一條可以

14、安排給一臺要求新任務的鏟運機運行的路線。其目的是隱性地評估所有可能的路徑并按照指定的標準從其中選擇一條最優路徑。圖3是一個更加完整的圖，稱為離散圖。在該圖中，每一層次代表運輸網絡的一個交叉口而每個層次的節點表示交叉口空閑的時間單元，這些節點在圖2中由白色空間表示。節點之間的弧線代表可行的鏈接。該圖僅構建了從當前時間開始的一個預定的時間范圍，這關聯到一輛鏟運機對新任務的要求。鑒于知道車輛要求新任務的位置（起始節點），則可到達的目的地的集合是確定的。例如，如果車輛位于節點“Q”（代表裝載點），它之后可以到達節點“G”或節點“K”，這兩個節點代表傾倒點。選擇可行的目的地不僅取決于起始點，還取決于將要

15、搬運的材料的類型。對于每一個調度決策，特定的起始點與所有可行目的地之間的最短路徑是經過評估的。在最短路徑之間進行選擇取決于預定的調度準則。最短路徑是使用Dijkstra算法找出的。所選路徑上的每個節點表示運輸網絡中的鏟運機將沿著該路線運行，也表示車輛通過路口的時段，并且間接地限定了車輛在每個路段的運行速度。這個采用Dijkstra最短路徑算法的決策方案允許將分配任務的兩個方面（路徑選擇和行程安排）作為一個單一問題來考慮。圖3.加入匯聚節點3.2調度決策通過在離散圖上添加一個匯聚節點且僅將代表可行目的地的節點與匯聚節點連接起來（見圖3），這可能將第三個問題，即調度決策，包含到決策過程中。為了實現

16、這一目標，弧線上的成本就所選擇的客觀標準來說必須具有代表性。通過選定的調度準則來看，起始點與匯聚節點之間的最短路之后將被定為可行路徑，同樣確定下來的還有行程安排和目的地。弧上的成本可表示在運輸網絡的路段上所花的時間或在節點處的等待時間。在這樣一個模型里，匯聚節點的輸入弧的成本為零。因此，最短路徑代表從起始點到匯聚節點所用的時間最短。為了確定目的地，在解決方案中就需要去看匯聚節點的前趨弧線。考慮到另一個調度準則，網絡中弧線的成本也可能需要修改。例如，如果采用一個類似于那些露天礦山所使用的計劃驅動調度準則，則其目的是使生產水平和最優生產計劃的指標水平之間的偏差最小化。匯聚節點的輸入弧將采用這種偏差

17、。另一種可能性是將各種標準結合起來。例如，從起始點到目的地之間的最短時間路線可以作為第一客觀標準而與生產計劃的偏差則可作為第二標準。最短路徑算法首先為每個目的地選擇最短路線，然后從這些路線中選擇與生產目標偏差最小的一條。為此目的，最短路徑算法進行了修正，即離散圖上的每個節點，除匯聚節點外，各路線之間的優勢由時間標準來定，而匯聚節點的優勢由第二標準來定。因此，與生產目標偏差有關的成本只算在匯聚節點的輸入弧上，而其他弧的成本表示在這些弧上花費的時間。通過在離散圖上使用最短路徑算法，決策時間將足夠短，能夠在幾秒鐘之內為車輛分配一個新任務，以遵守該問題中無法避免的實時約束條件。事實上，大部分時間都用于

18、分析圖形構成。圖4.車輛方向改變3.3確保車輛在目的地定向正確運輸網絡中的一些路口允許車輛改變行進方向，以便正確地駛向（即鏟斗在前）目的地。圖4說明了兩種情況下車輛改變方向的例子，第一例對應于車輛以前進方式到達目的地，而以后退離開的情形。因此，每當車輛以正確定向抵達目的地，那在開始下一個任務時，它必須先倒車。第二個例子顯示車輛利用路口改變方向。在巷道A中，車輛后退行駛，之后，它后退進入路口B，并以前進方式離開路口進入巷道D。在基本圖形中，其路線依次是“A-B1-B2-B3-D”。從這兩個例子得出一條通用的規則：每當車輛通過一個由奇數個節點構成的路口（在本例中由節點序列B1、B2、B3表示）時，

19、改變方向是有效的；每當車輛通過一個由偶數個節點構成的路口時，將保持方向不變。圖4中的第二個案例，將車輛的路線以“A-B1-B2-C”代替原來路線“A-B1-B2-B3-D”，那么它會保持相同的方向，如事實表明的，它通過關聯到B1和B2兩個節點的同一路口。這個簡單的規則代表任何案例。圖5.重疊的網絡可以用兩種方法確保車輛到達目的地時定向正確。第一種是使用一個能保存車輛定向記錄的資源（一個二進制變量）。在匯聚節點，約束將檢驗車輛是否定向正確。在這種情況下，將使用相同的圖形，但卻通過利用資源制約條件解決一個最短路徑問題的途徑來獲得決策方案。為了避免資源使用以及由于參與地下調度系統的圖形尺寸相對較小，

20、從而提出第二種辦法，即重疊離散圖形。一層表示一個對應于向前移動的離散圖形拷貝，而第二個拷貝則對應于后退移動。在之前的離散圖形中對應一個路口節點的所有輸入弧將從新圖的每個層中刪除并由跨層弧代替，其中尾節點和頭節點位于不同的層（見圖5）。當路徑使用一個跨層弧時，車輛方向將改變（其中一些變向的發生是虛擬的）。例如，讓我們考慮一下圖4案例2中描述的路徑“A-B1-B2-B3-D”。在新圖的后退移動層中，沒有弧線把節點A和節點B1連接起來，因為弧（A，B1）是路口節點B1的輸入弧。路徑將利用跨層弧（A，B1）把后退移動層上的節點A和向前移動層上的節點B1連接起來。向前移動層上的節點B1將被連接到后退移動

21、層上的節點B2，因為在向前移動層上沒有連接節點B1和節點B2的弧。（路徑“A-B1-B2”是一個虛擬變向的例子。）路徑繼續從后退移動層的節點B2到達向前移動層的節點B3。最后，向前移動層的節點B連接到同一層的節點D上，因為節點D不是一個路口節點。同樣，圖2中給出的兩條路徑遵循相同的規則。沿路徑“K-J-H-I-L-M-N-O-Q”運行的第一輛車在經過節點序列“K-J-H-I”之后改變了行駛方向，但在經過節點序列“M-N-O”之后保持向前移動。相似地，沿路徑“R-P-N-M-L-I-H-D-B-C-G”的第二輛車在經過節點序列“R-P-N”之后保持后退移動的方式運行，但在經過節點序列“D-B-C

22、”之后將其運行模式改為向前移動。為確保車輛都能以正確定向抵達目的地，在圖中向前移動層上表示可行最終目的地的節點（圖5中的裝載點）是唯一能鏈接到匯聚節點的一些節點。根據這個新圖形，Dijkstra算法可以再次引用來尋找到解決方案。3.4死鎖情況當無法給一輛鏟運機指派目的地時就發生死鎖。使用本文提出的解決方案時也可能出現死鎖情況。依次地調度車輛是導致死鎖的原因之一。例如，就圖6所示的網絡而言，可以看到有一個裝載點、一個卸載點和兩條路徑，在起始時（時刻0），位于節點B的車輛V1被指派到節點A，并將于時刻20達到目的地。在時刻0和時刻20之間，車輛V2和V3被指派到節點A，并在各自的路段等候，以避免跟

23、車輛V1發生正面沖突。在時刻20，系統必須再次調度車輛V1，但現在如果系統不重新安排車輛V2和V3則不可能找到一個可行的解決方案：即產生了一種死鎖情況。為了避免或盡量減少出現這種情況的風險，該系統可以增加做出決定的時間范圍。系統能夠在一條更長的路線上調度車輛，而不是僅在半周期內調度，即半周期再加上一段從目的地到某一特定節點的安全路線，假設在該特定節點可以再次調度車輛。在現實中，這個額外的安全路線在解決過程中并不一定適用，因為只會將車輛派到與半周期相關的目的地。然而，額外的路線會在為其他車輛所采取的即將到來的調度決定中采用。事實上，系統會認為第一輛鏟運車占據了額外的路線。考慮前面的例子（見圖7）

24、，將安全節點C添加到網絡中。在時刻0，車輛V1被安排從節點B駛向節點A，并于時刻20到達。系統記錄了這一信息，并于車輛V1在節點A裝載之后增加了從節點A到節點C的路線。在車輛V2和V3收到對它們的調度決定之后，它們將不能夠在節點A和節點C等待。在時刻20，車輛V1會申請一個新任務，而系統正好能提供給它，因為至少有一個可行的方案。圖6.死鎖情況這種方法有時會得出次優的方案，因為有些路段要留作專用，但它減少了出現死鎖情況的風險。圖7.一個安全節點4解決方案前景實時的解決車隊管理問題是一個復雜的任務。由于地下采礦作業的隨機性，做出調度決策的時間不能太久。因此，調度決策將更加頻繁，這暗示了高效決策策略

25、的使用。此外，對在短時間內做出調度決策的需要淡化了對生產優化問題的全局視野。為了減少這些制約因素的影響，一種計劃驅動調度的方法被建議使用，因為它在露天礦山的使用是很普遍的（見Munirathinam和Yingling，1991）。基于第一層次的最優生產計劃保證了該問題有一定的全局視野。這一計劃也在不斷更新，以便能始終反映礦井的實際狀況。調度決策包括盡量減小實際與最優生產計劃的偏差。對這個系統的一些測試工作已經完成（見Gamache等，2001）。這些測試結果表明，調度決策在同一時間僅涉及一輛鏟運機則會導致較差的生產水平。在每次循環中，因為系統僅為一輛車尋找最佳目的地，所以它沒有考慮那些即將派出

26、的車輛。關于該方法造成糟糕決策的例子是顯而易見的。為了盡量減少這種缺乏遠見的方法的影響，啟發式算法目前已開發出來，用于重新檢核已分配給鏟運機的路線各部分情況，以改進該決策方案。本文提出的系統可以描述為車隊管理研究項目的第一代。如前所述，這第一代有一些暫時的局限性：它認為決定論的服務和運行時間，而且一次只為一輛車做出決策，忽略了這個決策對后續車輛的影響。然而，這一系統已經整合了地下礦山車隊管理系統的三個重要方面：調度，路徑選擇和行程安排。目前的系統以一種確定的方式工作。事實上，即便為了規避對采礦作業隨機性的把握不全面，一些安全因素已被整合在每個決策中，這一策略依然不是十分充分。第二代地下礦山車隊管理系統正在改進。它會考慮在采礦過程中的各種突發事件，如車輛故障，在巷道內意外停止等。正在進行的改進包括處理各種運行和服務時間問題的能力。與此同時，不僅能為某輛鏟運機也能同時為其后續車輛迅速做出調度決策的第三代系統也正處于開發階段。已證明，在露天礦調度系統中，這種策略顯著提高了生產效率。在上述領域的進展是令人鼓舞的，應及時報導出來。參考文獻1