基于多Ａｇｅｎｔ的列車編組計劃優化模型研究

摘要：本文闡述了貨物列車編組計劃的復雜性，引入多Agent技術，建立了基于多Agent的編組計劃優化模型，并重點講述了Agent之間的交互機制以及車流合并過程，最后指出了該方法的優越之處，對于列車編組計劃智能化編制具有借鑒作用。

關鍵詞：編組計劃；多Agent系統；協商機制

中圖分類號：U292.3文獻標識碼：A文章編號：1002-3100(2007)04-0132-02

Abstract: This paper explains the complexity of making freight train formation plan， brings in the multi-agent technology and founds the optimizing model of train formation plan based on multi-agent. Afterwards it gives the collaboration mechanism as well as the process of distribution. At last， it points out the superiority of this method， which can be used for references for intelligent making freight train formation plan.

Key words: train formation plan; multi-agent system; collaboration mechanism

在鐵路運輸組織中，制定列車編組計劃是基礎性工作，是確定各支車流的運送途徑和中轉方式的過程，其優劣程度直接影響鐵路設備的利用率及運輸成本。近年來，國內外學者對于列車編組計劃與車流組織優化的研究主要集中在數學模型的建立和求解方面，比較有代表性的有：0—1規劃法[1]、二次0—1規劃法[2]以及幾種網絡優化模型[3-5]；在模型的求解方面比較成功的是模擬退火算法[6]。但是由于該問題還涉及車輛走行里程、運輸成本、車站能力與區段通過能力等眾多因素，因此，在其建模過程中需進行一定的簡化，造成理論研究同實際情況存在著距離。此外在路網規模龐大，車流數目眾多的情況下，其在模型的求解上也相當復雜，存在著一定的難度。

列車編組計劃的優化是一個十分復雜的問題，具有：（1）復雜性，車流之間相互耦合，某支車流改編方式的變動可能引起其他車流也發生變化；（2）不確定性，車流的組合形式是不確定的；（3）分布性，各支車流是分散的。對于這類問題的求解，目前人工智能領域興起的多Agent方法[7]有較大優勢。

此外，列車編制組計劃的編制過程可看作為資源分配相應任務的過程，其中，每支車流看作需要完成的一種類型的任務量，而車站和區段看作為完成任務的資源，則列車編組計劃轉化為一個任務分配的問題，而目前多Agent在車間的任務分配得到了很好的應用，因此，本文將Agent引入列車編組計劃的優化中，借助Agent的自主性、智能性、主動性以及交互性，將每個任務分配給合理的資源，提高鐵路設備的利用率。

1基于多Agent的列車編組計劃優化模型

1.1模型的創建。列車編制計劃的優化主要涉及的實體為車流、車站以及區段，其整個過程實質上是為各支車流選取適當的車站和區段組織貨物運輸的過程。如上面所說，可以將該問題轉化為任務分配過程來求解，車流尋找路徑的過程看作需要完成的任務，而路網中的所有車站和區段看作資源，則每支車流的運送路徑由相應進行作業的車站和區段組成。分別為每個任務和資源都各設置一個Agent作為代理，通過它們之間直接或間接的交互來為每個資源分配任務。基于多Agent的編組計劃優化模型如圖，包括：（1）負責與人交互的交互Agent；（2）資源Agent，映射車站和區段實體，負責監測發來的任務是否超出了能力限制；（3）任務Agent，映射車流實體，負責與其它的任務Agent交互，尋找合適的合并對象；（4）管理Agent，用來進行沖突處理；最后還有兩個數據庫分別為路網數據庫和編組去向庫。其中，路網數據庫主要存放路網信息，從車流角度來說，存放的是各支車流的所有徑路；編組去向數據庫存放車流選定的所有編組去向信息，是由任務Agent不斷寫入以及刪除的。

1.2Agent之間的交互機制。列車編組計劃的優化中主要的交互是車流與車流之間的相互作用，在此本文借用招商機制來實現它們之間的合并問題。當某支車流或合并車流達到直達運送的絕對條件時，發布公告，成為已定招商者；而當其每站改編的車小時節省大于等于0.8cm時，也發布公告，成為暫定招商者，其他車流為投資者，不斷檢測公告中是否存在與其有部分相同路徑，然后計算投資的效益來決定是否投資。當一輪投資完后，各暫定招商者判斷合并車流是否滿足絕對條件，若滿足轉為已定招商者，反之招商失敗，還原所有車流的狀態；對于已定招商者，要計算判斷其內部的合并車流對其始發或終到站是否滿足絕對條件，從而延長其始發或終到站。

1.3運作過程以及招商機制。由于技術站的車流合并過程比較復雜，因此本文只針對技術站的招商過程加以介紹。在車流與車流的交互合并過程中，存在某站的改編任務超過其能力的可能性，需管理Agent來仲裁處理。整個運作步驟如下：

初始狀態：每支車流為一個直達去向。

（1）每支車流Agent對其所有的可行徑路進行計算判斷，若滿足絕對條件Nt_節^最小≥cm，將其定為直達去向轉為已定狀態；若滿足條件Nt_節^最小≥0.8cm，暫時將其定為直達去向轉為暫定狀態；若都不滿足保持初始狀態，計算有沒有一站節省Nt_節≥cm，如果存在則標記不應該在該站截流。

（2）直達車流Agent發布其直達的消息，其他車流Agent讀到所有消息后計算其收益，若收益為正并且相對于直達車流或車流組合只須進行一次改編，則該Agent向相應的車流Agent發送同意投資的消息，并轉為與對應的招商者相同的狀態，否則不進行投資。若存在多種可投資的方案，選取可獲得收益最大的投資。

（3）各直達車流Agent收到所有投資消息后，作進一步檢查，對于暫定狀態的直達車流，再次判斷合并后車流是否滿足絕對條件，若滿足將所包含的車流轉為已定狀態；若不滿足，回復所有對其投資的車流，表示此直達去向已失效，其他車流收到后恢復初始狀態。

（4）檢測已定狀態中的所有直達去向，判斷合并車流后對于其始發和終到站是否滿足絕對條件，若滿足，延長相應車流的始發或終到站，并處理對其他車流的影響，計算延長前后所有車流的消耗，取消耗最少的方案。將所有已定狀態的車流所標記的不該截流站取消。

（5）車站Agent檢測其改編任務是否超出其改編能力后，若否，轉到6；若是，則向管理Agent發送報告，由管理Agent按如下步驟進行調整。

選取其他的有直達車流始發和終到且剩余改編能力較大的車站，將一部分改編作業轉到該站；若該站存在始發或終到的直達車流，將可投資該直達車流的車流在超負荷車站的改編轉為在該站改編，合并相同徑路的車流，按照上述（2）、（3）、（4）、（5）步驟進行招商處理；若不存在直達車流，試著將在超負荷車站的某些改編作業轉移到該站，按照上述（2）、（3）、（4）、（5）步驟進行招商處理，通過計算其對整體車小時消耗的影響，取車小時消耗相對較少的方案。

（6）若路網中各站車流合并不滿足絕對條件或各部分車站個數≤4，則轉到（8），并將不滿足必要條件的直達去向取消；反之，車站管理Agent設置截流點，其原則為：直達已定狀態中，若存在可銜接的去向且其銜接站的t_節不大于短路網上其他站的，且其改編能力較大，則選取該銜接站；如果不存在，選取處于路網中部的直達去向的始發或到達站的t_節不大于其他各站的，且改編能力較大的站；若都不滿足，選取處于路網中起全部通過車流不滿足充分條件且其改編能力相對較大的車站；若不存在，選擇靠近路網中部的站，且其t_節不大于其他各站的，改編能力較大的。

（7）將所有初始車流以及暫定狀態的直達以及非直達車流在截流點分為左右兩部分。兩部分可以按照上述步驟1、2、3、4、5再進行計算。

（8）取消初始狀態中不滿足必要條件的直達車流，編入區段列車，輸出所有結果。

2結論

論文首次將多Agent技術引用到列車編組計劃的優化過程中：將車流送達目的地過程看作要完成的任務，并設置一個Agent為其尋找合適的徑路；將每個車站和區段看作資源，也設置一個Agent，用來組成路網，供各任務Agent分配其任務。在優化過程中，各任務Agent在路網條件下通過間接交互尋求自身利益最大的同時由管理Agent仲裁管理從而求得總體的滿意解。此外，每一個任務Agent映射一支車流實體，使其具有自主性和智能性，將以前專家才具有的經驗知識分布到各支車流中，由各支車流主動地在路網中尋找合適的運輸路徑，體現了運算的分布性。但是，目前提出的還僅僅是一個模型，以后還需要進一步做深入細致的研究，包括各個Agent需要具備的知識表達、Agent之間的協作規則、沖突處理等，才能實現整個列車編組計劃的優化。

參考文獻：

[1] 曹家明，朱松年. 優化列車編組計劃的0—1規劃法[J]. 鐵道學報，1992，14(4):49-57.

[2] 曹家明，朱松年. 鐵路網上技術直達列車編組計劃優化的二次0—1規劃法[J]. 鐵道學報，1993，15(2):62-70.

[3] 史峰，李致中，孫焰，等. 列車編組計劃網絡優化方法[J]. 鐵道學報，1994，16(2):74-79.

[4] 林柏梁，朱松年. 路網上車流徑路與列車編組計劃的整體優化[J]. 鐵道學報，1996，18(1):1-7.

[5] 李映紅，吳世貴，彭其淵. 貨物列車編組計劃網絡模型的建立及算法[J]. 西南交通大學學報，2002，97(1):68-71.

[6] 林柏梁，朱松年. 優化編組計劃的非線性0—1規劃模型及模擬退火算法[J]. 鐵道學報，1994，16(2):61-66.

[7] 張潔，高亮，李培根. 多Agent技術在先進知道中的應用[M]. 北京：科學出版社，2004.

[8] 李英. 多Agent系統以及其在預測與智能交通系統中的應用[M]. 上海：華東理工大學出版社，2004.