優(yōu)化時(shí)間窗改進(jìn)Dijkstra算法的無人駕駛磁懸浮車路徑規(guī)劃

關(guān)鍵詞：軌道交通；磁懸浮車；智能路徑規(guī)劃；Dijkstra算法；優(yōu)化時(shí)間窗中圖分類號(hào)：U292.4 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2025）07-021-2080-06doi：10.19734/j. issn.1001-3695.2024.12.0515

Abstract：Aiming at thecharacteristicsof multi-vehicleoperationonthesame trackandhigh vehicle densityofautonomous maglev，thispaper studiedapath planning algorithmformaglevbasedonoptimizedtime windowand improvedDijkstra’salgorithm，whichtook intoaccountaseriesofrealisticproblemssuchaspathconflictandschedulingcost，andcombinedDijkstra's algorithmwiththetime windowtosequentiallplanthepathsof individualmaglevs.Firstly，itpre-processed hemapiformationbeforepathplanning，then generatedtheshortestpath index according tothemap nodes，andfoundthepathsaccordingto theindex.Secondly，itusedthetime windowtocheckthepathswithorwithoutconflicts.Then，itanalyzedtheconflictpaths specificall，andchanged thespeedofvehicletoavoidtheobstaclewithshorterconflicttime，itavoidedthepathsreplanning， andoptimizedtheorderruning timeonthebasisofcolision-free.Finally，itusedtheOpenTCSsoftware tosimulatethealgorithm.Theresults show thatunder thesame conditions，theaverage executiontimeofthe Dijkstraalgorithm after optimizing the time window is 0.328ms ，and the vehicle running time per kilometer is 36.64 s. Under the premise of no conflict paths， it improvedthereal-timeperformanceoftheordersandthevehicleoperation eficiency.Astheoperating kilometers increases， theadvantagesof thealgorithmbecomeincreasinglyapparent.Theproposedalgorithmcanmettherequirementsofcolisionfree path planning for autonomous magnetic guided vehicles.

Keywords：rail transit；maglevguidedvehicle；inteligentpath planning；Dijkstraalgorithm；optimize time window

0引言

永磁懸浮無人駕駛軌道交通系統(tǒng)是未來城市公共交通的主要形式之一，車輛同向三軌運(yùn)行，分低、中、高三線軌道，車輛一般運(yùn)行于中、高速車道，啟動(dòng)、停車階段運(yùn)行于低速車道，不同軌道之間設(shè)置變道系統(tǒng)，且同軌道同時(shí)多車運(yùn)行，所有車輛集中控制、無人駕駛，車流密度大，運(yùn)輸效率高。傳統(tǒng)的軌道交通屬于單軌運(yùn)行，調(diào)度車輛后，車輛發(fā)車時(shí)間和路線均已確定，不需要再進(jìn)行路徑規(guī)劃，也不再有車輛沖突問題。三線軌道交通是需求響應(yīng)式交通，根據(jù)客戶要求的時(shí)間和地點(diǎn)接駁，由于路線不確定，車輛存在碰撞隱患，所以需要依靠高效準(zhǔn)確的路徑規(guī)劃算法和調(diào)度策略保證車輛安全運(yùn)行。出租車、網(wǎng)約車等傳統(tǒng)交通工具路況復(fù)雜，規(guī)劃可選的路徑數(shù)量多，本文的路徑規(guī)劃僅限三線軌道，增加了約束條件，需要根據(jù)實(shí)時(shí)路況進(jìn)行調(diào)度。關(guān)于永磁懸浮軌道交通車輛（maglevguidedvehicle，MGV）調(diào)度系統(tǒng)的研究報(bào)道不多，因此，深入研究其路徑規(guī)劃與調(diào)度系統(tǒng)具有十分重要的意義。

為了提高城市軌道車輛調(diào)度的效率，文獻(xiàn)[1]將遺傳算法和貪婪算法結(jié)合，優(yōu)先處理較早的叫車請(qǐng)求，但車輛的運(yùn)行路徑較為單一，沒有針對(duì)各訂單分別規(guī)劃路徑。文獻(xiàn)[2]提出了一種智能化的樞紐站軌道交通換乘線路調(diào)度方法，以最小行駛時(shí)間總和為優(yōu)化目標(biāo)，建立調(diào)度模型。文獻(xiàn)[3]依靠歷史數(shù)據(jù)對(duì)客流量進(jìn)行預(yù)測，動(dòng)態(tài)調(diào)整發(fā)車時(shí)間。在路徑規(guī)劃方面，經(jīng)典算法中， A^* 算法在柵格化地圖中有較好的效果[3]，針對(duì)有向帶權(quán)圖結(jié)構(gòu)，Dijkstra算法通過廣度優(yōu)先遍歷得出最短路徑，計(jì)算速度較快；元啟發(fā)式算法從較為早期的模糊邏輯算法和模擬退火算法發(fā)展到神經(jīng)網(wǎng)絡(luò)、遺傳算法及蟻群算法[4等，其普遍特點(diǎn)是具有一定的泛化能力，且有多種可調(diào)參數(shù)以適應(yīng)不同的建模環(huán)境。然而對(duì)于在線動(dòng)態(tài)調(diào)度系統(tǒng)，元啟發(fā)式算法的收斂速度慢、結(jié)果不穩(wěn)定等缺陷并不適用于高頻次使用。文獻(xiàn)[4]對(duì)遺傳算法進(jìn)行改進(jìn)，設(shè)計(jì)了基于遺傳算法的多AGV路徑規(guī)劃算法，并采用改進(jìn)的靜態(tài)地圖法來解決多AGV路徑?jīng)_突問題，但其算法收斂速度較慢、時(shí)效性較差;文獻(xiàn)[5]對(duì)地圖信息進(jìn)行預(yù)處理，降低算法計(jì)算時(shí)間復(fù)雜度，并創(chuàng)建訂單融合引擎來優(yōu)化總時(shí)間，但其未考慮多車路徑?jīng)_突問題；文獻(xiàn)[6]定義了AGV的優(yōu)先級(jí)，提出一種改進(jìn)差分進(jìn)化算法的無路徑?jīng)_突路徑規(guī)劃算法，但其未考慮不同行駛速度下的路徑規(guī)劃；文獻(xiàn)[7]提出了一種改進(jìn) A^* 算法的全局動(dòng)態(tài)路徑規(guī)劃方法，但未考慮車輛沖突問題；文獻(xiàn)[8]通過實(shí)時(shí)改變路徑的權(quán)重，減少了車輛沖突，但其不適合大型地圖的路徑規(guī)劃，易產(chǎn)生數(shù)據(jù)不同步問題。

由已有文獻(xiàn)可知，傳統(tǒng)軌道交通車輛路線固定，無法適應(yīng)定制化出行，遺傳算法、混合粒子群算法等啟發(fā)式算法收斂速度慢、結(jié)果不穩(wěn)定，不滿足實(shí)時(shí)性要求，Dijkstra算法作為單源最短路徑搜索算法，具有搜索效率高、結(jié)果穩(wěn)定的優(yōu)點(diǎn)。本文主要針對(duì)的是專人專車的個(gè)性化服務(wù)，是新型軌道交通，因此，本文將Dijkstra算法作為路徑規(guī)劃的基礎(chǔ)算法，與時(shí)間窗結(jié)合并進(jìn)行改進(jìn)，考慮多車之間的路徑?jīng)_突，通過判斷各路段的時(shí)間窗是否存在重疊做出相應(yīng)動(dòng)作，進(jìn)而實(shí)現(xiàn)磁懸浮車的路徑規(guī)劃。

1MGV路徑規(guī)劃模型

1.1 問題描述

如引言所述，傳統(tǒng)路徑規(guī)劃主要關(guān)注個(gè)體車輛從起點(diǎn)到終點(diǎn)的最優(yōu)路徑選擇，實(shí)現(xiàn)單車運(yùn)行成本最低的目標(biāo)。區(qū)別于傳統(tǒng)車輛的路徑規(guī)劃和軌道交通運(yùn)行場景，本文三線軌道交通路徑規(guī)劃運(yùn)量大，同軌道多車密集運(yùn)行，車輛根據(jù)路徑需要在三軌之間合理變道，是全新的運(yùn)營場景，也是本文路徑規(guī)劃的難點(diǎn)。傳統(tǒng)路徑規(guī)劃算法一般不考慮實(shí)時(shí)路徑信息和其他車輛，此時(shí)規(guī)劃出的路徑極易與其他車輛發(fā)生路徑?jīng)_突。若車輛在行駛過程中有突發(fā)情況導(dǎo)致變速、停車或者路徑發(fā)生變化時(shí)，同樣也會(huì)產(chǎn)生路徑?jīng)_突，因此需要一種實(shí)時(shí)的動(dòng)態(tài)路徑規(guī)劃算法。針對(duì)這種動(dòng)態(tài)環(huán)境，多MGV路徑規(guī)劃要求MGV控制系統(tǒng)對(duì)時(shí)間和空間資源進(jìn)行合理分配，協(xié)調(diào)所有MGV有序運(yùn)行，在保證MGV無碰撞的前提下規(guī)劃出最優(yōu)路徑，從而保證每輛車都能順利且快速地運(yùn)行。

1.2路徑規(guī)劃環(huán)境模型的建立

采用有向圖 G=（N，A） ，其中 N={n₁，n₂，n₃，…，n_n} 表示一系列節(jié)點(diǎn)， A={a¹，a²，a³，…，a^m} 表示一系列有權(quán)重的邊。節(jié)點(diǎn)表示車站或各個(gè)車道之間的變速系統(tǒng)，邊的權(quán)重代表各個(gè)點(diǎn)之間有效路徑的長度。為降低分析難度，對(duì)MGV模型及路徑作如下規(guī)定：

a）MGV行駛的最高速度為 120km/h ，加速度為 減速度為 。b）每臺(tái)MGV同一時(shí)間只能承擔(dān)一個(gè)訂單任務(wù)。c）如圖1和2所示，每 1km 布置一個(gè)車站；每隔 1km 布置一個(gè)低-中速變道系統(tǒng)，位于兩個(gè)車站中間；每隔 1km 布置一個(gè)中-高速變道系統(tǒng)，與車站位置相差 50m_? d）三個(gè)車道的基準(zhǔn)速度分別為：低速道 40km/h ，中速道80km/h ，高速道 120km/h ;如車輛有變道需要，適當(dāng)進(jìn)行變速。e）三條車道均只能單向行駛，每個(gè)車站都有掉頭系統(tǒng)，車輛可以經(jīng)由掉頭系統(tǒng)行駛至回程的三個(gè)車道上。

f）安全距離設(shè)定為 50m 。

1.3路徑規(guī)劃數(shù)學(xué)模型的建立

在服務(wù)器的調(diào)度區(qū)段內(nèi)，所有MGV到達(dá)目的地的時(shí)間總和最短，即為運(yùn)行效率最大的目標(biāo)，如式（1）所示。

P_end，k=P_start，k+1

t_costⁱ?t_ecostⁱ

其中： i∈MGV 集合； k 為第 k 輛MGV的訂單集合。

t_{e，window（i）}^out?t_{e，window（i+1）}ⁱⁿ

以上約束條件可以作為遞推式，通過Dijkstra算法和時(shí)間窗思想，計(jì)算出每臺(tái)MGV的最短路徑序列與時(shí)間窗序列，達(dá)到無碰撞規(guī)劃的效果。

式（2）中， i∈ 所有訂單集合，表示第 χ_i 個(gè)原始訂單的開始時(shí)間、接乘客時(shí)間、到達(dá)目的地時(shí)間與結(jié)束時(shí)間滿足的先后關(guān)系；式（3）（4）中 ，k，k+1∈OrderList_n ，表示對(duì)于每一臺(tái)MGV的任務(wù)隊(duì)列，第 k 個(gè)訂單的結(jié)束時(shí)間與結(jié)束坐標(biāo)等于第 k+1 個(gè)訂單的開始時(shí)間與開始坐標(biāo)；式（5）表示訂單 i 的總耗時(shí)等于路徑中消耗的時(shí)間與在上車點(diǎn)接乘客及到達(dá)目的地的時(shí)間之和；式（6）表示某一個(gè)訂單的實(shí)際耗時(shí)不可能小于其理論最短路徑通過需要的時(shí)間；式（7）表示對(duì)于某一段路徑 e ，時(shí)間窗隊(duì)列中的不同時(shí)間窗不能重合。

論文中的參數(shù)符號(hào)說明如下： M 為MGV集合， t_end/start^i，k 為第k 輛MGV的第 i 個(gè)訂單的結(jié)束/起始時(shí)間，OrderN為訂單集合， OrderList_?n 為 n 號(hào)MGV的訂單列表集合， ，t_end，k 為第 k 個(gè)訂單的結(jié)束時(shí)間， t_start，k+1 為第 k+1 個(gè)訂單的開始時(shí)間， p_{start，k+1} 為第k+1 個(gè)訂單開始時(shí)MGV 的坐標(biāo)， p_end，k 為第 k 個(gè)訂單結(jié)束時(shí)MGV的坐標(biāo)， t_costⁱ 為第 i 個(gè)訂單的實(shí)際消耗時(shí)間， t_ecostⁱ 為第 χ_i 個(gè)訂單的理論消耗時(shí)間，WindowList為邊 p 的時(shí)間窗隊(duì)列，Path-List_o 為第 σ_o 個(gè)訂單的路徑列表。 t_{start（carry/set/end}ⁱ 為單個(gè)訂單的起始/接乘客/到達(dá)目的地/結(jié)束訂單的時(shí)間， P_star/end 為MGV的初始/結(jié)束位置點(diǎn)， t_{p，win（i）}^in/out 為路徑 p 第 χ_i 個(gè)時(shí)間窗的開始/結(jié)束時(shí)間，OperationTime，為第 n 個(gè)MGV的總運(yùn)行時(shí)間，ExpectTime為第 χ_i 個(gè)MGV到達(dá)路徑 p 時(shí)的預(yù)計(jì)總運(yùn)行時(shí)間。

2基于時(shí)間窗的實(shí)時(shí)避碰算法

2.1基于時(shí)間窗改進(jìn)Dijkstra算法的路徑規(guī)劃

基于Dijkstra算法和時(shí)間窗思想，按照訂單順序分配各個(gè)車輛的行駛路徑，分別將車輛信息順序記錄在每個(gè)路徑中，車輛通過后，刪除該車輛在時(shí)間窗隊(duì)列的記錄。將時(shí)間窗作為邊的特性，一條邊分配一輛MGV，表示其通過的時(shí)間范圍。如圖3所示，MGV3在start時(shí)刻，由于時(shí)間窗的約束將無法通過這條邊。為了避免多MGV運(yùn)行時(shí)發(fā)生路徑?jīng)_突，基于時(shí)間窗思想，構(gòu)建不等式：

ExpectTime_v2^p+t_{p，win（i）}^out-t_{p，win（i）}ⁱⁿp，win（i）ⁱⁿ-OperationTime_v1

ExpectTime_v2^pgt;t_{p，win（i）}^out-OperationTime_v1

其中： ExpectTime_υ2^p 表示到當(dāng)前路段 p 為止，車輛 v₂ 根據(jù)無碰撞路徑規(guī)劃算法所規(guī)劃路徑的總時(shí)間； t_{p，win（i）}^in/out 分別為當(dāng)前路段 p 的第 i 個(gè)時(shí)間窗的開始和結(jié)束時(shí)間； OperationTime_υ1 為車輛 v₁ 的當(dāng)前運(yùn)行時(shí)間。式（8）表示車輛 v₂ 按照Dijkstra算法規(guī)劃的最短路徑，經(jīng)過的每一條路徑需滿足 v₂ 行駛完該路徑時(shí)， v₁ 仍未到達(dá)。式（9）表示車輛 v₂ 到達(dá)該路徑時(shí)， v₁ 已經(jīng)離開該路徑。

Dijkstra算法基于貪心策略從起點(diǎn)開始逐步擴(kuò)展，最終找到從起點(diǎn)到終點(diǎn)的最短路徑，時(shí)間窗基于預(yù)測式思想，從“時(shí)間”和“空間”兩個(gè)維度確定車輛信息，兩個(gè)維度均發(fā)生重疊時(shí)，代表車輛即將發(fā)生沖突，隨即重新規(guī)劃路徑以避免沖突。時(shí)間窗和Dijkstra 結(jié)合的算法與Dijkstra 算法的求解思路一致。引入時(shí)間窗屬性，對(duì)選擇的邊計(jì)算額外的時(shí)間代價(jià)，驗(yàn)證是否滿足時(shí)間窗要求，如果不滿足，則改變沖突路徑的權(quán)值，重新利用Dijkstra算法進(jìn)行路徑規(guī)劃。圖4為結(jié)合時(shí)間窗改進(jìn)Dijkstra算法的流程，首先對(duì)地圖信息進(jìn)行預(yù)處理，根據(jù)地圖信息計(jì)算路徑長度，設(shè)置起點(diǎn)并利用Dijkstra算法進(jìn)行路徑搜索，判斷起點(diǎn)與終點(diǎn)是否相同，如果不同，則獲取最短路徑序列PathList，遍歷最短路徑序列；將每一段路徑時(shí)間窗的開始時(shí)間、結(jié)束時(shí)間和車輛運(yùn)行時(shí)間代入式（8）和（9）計(jì)算，滿足條件，表明不會(huì)發(fā)生碰撞，不滿足條件則更新沖突路段權(quán)值，重新利用Dijkstra算法規(guī)劃路徑，獲取新的最短路徑序列。當(dāng)所有路徑時(shí)間窗滿足式（8）和（9）之后，判斷最短路徑序列中的路徑是否能到達(dá)終點(diǎn)，如果能，添加時(shí)間窗隊(duì)列，算法執(zhí)行結(jié)束，否則繼續(xù)遍歷最短路徑，直至最短路徑可以到達(dá)終點(diǎn)，算法結(jié)束。

結(jié)合時(shí)間窗改進(jìn)的Dijkstra算法通過驗(yàn)證路徑上的時(shí)間窗，在已規(guī)劃MGV路徑的基礎(chǔ)上，運(yùn)用改進(jìn)的Dijkstra算法繼續(xù)規(guī)劃下一MGV，實(shí)現(xiàn)了多MGV之間的無碰撞路徑規(guī)劃。

2.2 多MGV路徑總耗時(shí)優(yōu)化

為了實(shí)現(xiàn)所有MGV到達(dá)目的地的時(shí)間總和最短的目標(biāo)，路徑規(guī)劃要考慮是否造成時(shí)間窗沖突及沖突的時(shí)長，再結(jié)合所在的車道、沖突兩車的運(yùn)行速度等因素，判斷是否可以進(jìn)行避讓，以此避免路徑重新規(guī)劃，縮短路徑總耗時(shí)。

如圖5所示，MGV1已經(jīng)規(guī)劃好了路徑與時(shí)間窗，并將在t_v1ⁱⁿ～t_v1^out 時(shí)段占用該路徑;MGV2的最短路徑時(shí)間窗 t_v2ⁱⁿ～t_v2^out 與已經(jīng)規(guī)劃好的MGV1發(fā)生了時(shí)間窗沖突，其沖突時(shí)長為

t_conf=t_v1ⁱⁿ-t_v2ⁱⁿ

其中： t_conf 為沖突的時(shí)長。

當(dāng)發(fā)生時(shí)間窗沖突時(shí)，根據(jù)沖突時(shí)間 t_conf，v₂ 應(yīng)有兩種選擇：a）沖突時(shí)間過長，根據(jù)改進(jìn)的Dijkstra算法重新規(guī)劃無沖突最短路徑;b）沖突時(shí)間較短，通過控制車輛速度實(shí)現(xiàn)車輛避讓，避免碰撞發(fā)生。

為了將上述兩種可能的情況引入算法，構(gòu)建特征量：

Δ=t_v1ⁱⁿ-t_v2ⁱⁿ-t_acpt

其中： t_υ2ⁱⁿ 為后車預(yù)計(jì)到達(dá)沖突路徑的時(shí)間； t_v1ⁱⁿ 為前車預(yù)計(jì)到達(dá)沖突路徑的時(shí)間； t_acpt 為根據(jù) v₁?v₂ 所在的車道、實(shí)時(shí)速度以及MGV最大加速、減速加速度計(jì)算出的可以爭取的理論最大時(shí)間窗。若 ，表明時(shí)間窗沖突可以通過控制車速的方式避免沖突；而若 Δgt;0 ，表明時(shí)間窗沖突過長，無法通過兩車變速避開沖突，需要后車重新規(guī)劃路徑。

如圖6所示，MGV1預(yù)計(jì)在OperationTime，時(shí)刻運(yùn)行至Path_p1 ，并將于 t_v1ⁱⁿ 時(shí)刻進(jìn)入 Path_p3 ;而 MGV2在規(guī)劃路徑時(shí)，預(yù)計(jì)在OperationTimev時(shí)刻運(yùn)行至 Path_p2 ，于 t_ν2ⁱⁿ 時(shí)刻進(jìn)入 Path_p3 ，兩者將發(fā)生時(shí)間窗沖突。因此，需要計(jì)算 t_acpt 進(jìn)而判斷是否可以避讓。

其中： a_p1 為路徑 p₁ 加速段的加速度； l_acc，p1 為路徑 p₁ 加速段的長度； t_acpt 為理論上的最大可接受時(shí)間窗； v_p1 為 p₁ 路徑段的基準(zhǔn)速度。通過對(duì)車輛實(shí)時(shí)速度與基準(zhǔn)速度的比較，精確計(jì)算時(shí)間窗。

通過以上方程組可以計(jì)算得出通過變速避讓的時(shí)間窗大小。為了不影響MGV1和MGV2以及沖突路徑段后續(xù)的時(shí)間窗，只允許在變速階段對(duì)兩輛車進(jìn)行加減速控制;否則，將造成時(shí)間窗沖突的傳遞，在最壞的情況下將導(dǎo)致所有的車輛都發(fā)生時(shí)間窗沖突，使調(diào)度系統(tǒng)崩潰。

2.3其他特殊情況處理

1）車輛行駛途中發(fā)生故障

由于車道屬于單向單車道，當(dāng)路徑上車輛發(fā)生故障無法行駛時(shí)，若其他車輛前往該路徑會(huì)發(fā)生車輛碰撞。所以當(dāng)車輛發(fā)生故障時(shí)，將該路徑權(quán)值增大，并設(shè)置為不可通過路段，清除故障車輛原來規(guī)劃的所有時(shí)間窗，故障排除后利用算法重新進(jìn)行路徑規(guī)劃。同時(shí)，發(fā)生故障后，其他車輛規(guī)劃的路徑中有該路徑應(yīng)立即重新規(guī)劃路徑，重新劃分時(shí)間窗。若無法避免碰撞，則立即實(shí)施緊急剎車。

2）集中控制中心控制車輛動(dòng)作

在達(dá)到保養(yǎng)里程，或者需要集中調(diào)度管理時(shí)，會(huì)由集中控制中心統(tǒng)一下發(fā)指令，將MGV調(diào)度至某一目的地。集中控制中心有最高的優(yōu)先級(jí)，車輛由集中控制中心控制，完成各類指令，在指令下發(fā)后應(yīng)立即執(zhí)行，而后重新為目的地規(guī)劃路徑，若車輛已經(jīng)進(jìn)行了訂單分配，應(yīng)當(dāng)將車輛的訂單取消，將該訂單重新分配給其他車輛。

3）乘客更改目的地

當(dāng)乘客在乘車過程中更改目的地時(shí)，由于涉及到的資源及安全條件較多，需滿足：一個(gè)訂單中只能更改一次目的地；為保證訂單順利完成，需要至少在目的地的兩站前更改。更改目的

地時(shí)，為了避免對(duì)其他車輛造成過多干擾，需要利用本文算法對(duì)涉及到的車輛進(jìn)行目標(biāo)函數(shù)的計(jì)算，當(dāng)區(qū)段內(nèi)的訂單滿足花費(fèi)總時(shí)間最短時(shí)，才允許更改目的地。

3優(yōu)化時(shí)間窗改進(jìn)Dijkstra算法的路徑規(guī)劃仿真

3.1地圖建模

本文基于Google開發(fā)的軌道交通控制開源軟件框架OpenTCS，開發(fā)并測試了優(yōu)化時(shí)間窗改進(jìn)Dijkstra算法。通過該軟件框架，將每一個(gè)新訂單都進(jìn)行路徑規(guī)劃、時(shí)間窗規(guī)劃、防碰撞處理以及資源分配后，通過Kernal將運(yùn)行指令下發(fā)到每一個(gè)MGV上，并且通過PlantOverview界面，實(shí)時(shí)監(jiān)控各個(gè)MGV的運(yùn)行狀況。

圖7所示為在OpenTCS中建立的部分環(huán)境模型。模型模擬了低-中-高三條軌道，每條軌道長 10km 。模型中包括173個(gè)節(jié)點(diǎn)，208段有向路徑，10個(gè)低-中速變道系統(tǒng)，10個(gè)中-高速變道系統(tǒng)以及13個(gè)車站（其中12、13號(hào)車站為模擬區(qū)段盡頭的高/中速車道）。

3.2 仿真數(shù)據(jù)與分析

在圖7的環(huán)境中，分別設(shè)置各邊的長度，在 10km 長的運(yùn)行區(qū)間內(nèi)，依次下發(fā)十個(gè)訂單，設(shè)置十輛MGV處理訂單，如表1所示。圖8所示為使用優(yōu)化時(shí)間窗的Dijkstra算法的路徑規(guī)劃。

在路徑?jīng)_突方面，由仿真過程可知，若使用Dijkstra算法，僅10個(gè)訂單，即產(chǎn)生7個(gè)沖突，無法進(jìn)行多車調(diào)度；由圖8可知，使用優(yōu)化時(shí)間窗改進(jìn)的Dijkstra算法，避免了路徑?jīng)_突。在算法執(zhí)行用時(shí)方面，如圖9（a）所示，Dijkstra算法規(guī)劃一個(gè)訂單的平均執(zhí)行時(shí)間是 3.0152ms ;結(jié)合時(shí)間窗改進(jìn)的Dijkstra算法與優(yōu)化時(shí)間窗改進(jìn)的Dijkstra算法采用了預(yù)處理地圖信息的方法，是一種“空間換時(shí)間”的策略，平均處理一個(gè)訂單的時(shí)間分別縮短至 0.268ms 和 0.328ms ，遺傳算法規(guī)劃一個(gè)訂單的平均用時(shí)為 4.69ms ，混合粒子群規(guī)劃一個(gè)訂單的平均用時(shí)為 5.32ms ，結(jié)合時(shí)間窗的Dijkstra算法的效率高于其他幾種算法。在路徑耗時(shí)方面，如圖9（b）所示，使用Dijkstra算法規(guī)劃，平均每個(gè)訂單執(zhí)行時(shí)間為 204.7s ；使用混合粒子群算法規(guī)劃，平均每個(gè)訂單的執(zhí)行時(shí)間為206.2s;使用遺傳算法規(guī)劃，平均每個(gè)訂單執(zhí)行時(shí)間為204.9s;使用結(jié)合時(shí)間窗改進(jìn)的路徑規(guī)劃算法，平均每個(gè)訂單執(zhí)行時(shí)間為217.1s，平均每千米里程運(yùn)行時(shí)間多增加了2.14s的運(yùn)行時(shí)間；而優(yōu)化時(shí)間窗后的算法每千米運(yùn)行時(shí)間增加了1.34s，在無碰撞的前提下縮短了運(yùn)行時(shí)間。在訂單總耗時(shí)方面，如圖10所示，Dijkstra算法、遺傳算法和混合粒子群算法規(guī)劃路徑的訂單總耗時(shí)接近，優(yōu)化時(shí)間窗后的算法車輛每千米運(yùn)行時(shí)間為36.64s，行駛距離超過 5km 時(shí)，優(yōu)化時(shí)間窗后的算法規(guī)劃路線行駛時(shí)間平均比結(jié)合時(shí)間窗的Dijkstra算法短9.2s；超過 9km 時(shí)，平均行駛時(shí)間短 18.5s 。各項(xiàng)參數(shù)的直觀對(duì)比如表2所示。因此，行駛距離越長，優(yōu)化時(shí)間窗后的算法優(yōu)勢更明顯，運(yùn)行效率較高，能快速響應(yīng)新的訂單，在動(dòng)態(tài)環(huán)境中具有較好的時(shí)效性，能對(duì)路徑?jīng)_突具體分析，實(shí)現(xiàn)了多磁懸浮車多訂單環(huán)境中總耗時(shí)的進(jìn)一步優(yōu)化。

4結(jié)束語

對(duì)地圖信息進(jìn)行預(yù)處理，將Dijkstra算法與時(shí)間窗結(jié)合，利用Dijkstra算法進(jìn)行路徑規(guī)劃，依靠時(shí)間窗校驗(yàn)路徑?jīng)_突；沖突時(shí)間較短的路徑依靠車輛變速的方式避免路徑重規(guī)劃，實(shí)現(xiàn)了無碰撞基礎(chǔ)上訂單總運(yùn)行時(shí)間的進(jìn)一步優(yōu)化。仿真結(jié)果表明，相同條件下的路徑規(guī)劃用時(shí)，混合粒子群算法的平均執(zhí)行時(shí)間為 5.32ms ，遺傳算法的平均執(zhí)行時(shí)間為 4.69ms ，優(yōu)化時(shí)間窗后的Dijkstra算法的平均執(zhí)行時(shí)間縮短為原來的 11% ，算法的執(zhí)行效率高于遺傳算法和混合粒子群算法，略低于結(jié)合時(shí)間窗的Dijkstra算法，但是，優(yōu)化時(shí)間窗算法平均每千米的運(yùn)行時(shí)間減少了0.8s，減少了車輛的運(yùn)行成本。本文研究的路徑規(guī)劃算法具有實(shí)時(shí)性高、規(guī)劃耗時(shí)短的優(yōu)點(diǎn)，可滿足無人駕駛磁懸浮車的路徑規(guī)劃要求。在未來的研究中，可以采用并行計(jì)算，同時(shí)放松更多的邊；調(diào)整算法搜索范圍，減少盲目搜索代價(jià)，進(jìn)一步提高算法的運(yùn)行效率。

參考文獻(xiàn)：

[1]李爽，楊明，王春香，等.面向全自動(dòng)控制交通系統(tǒng)的車輛調(diào)度算法[J].上海交通大學(xué)學(xué)報(bào)，2017，51（2）：174-179.（Li Shuang，YangMing，WangChunxiang，etal.Schedulingalgorithmforvehi-clesincybernetic transportation system[J].Journal of ShanghaiJiaoTongUniversity，2017，51（2）：174-179.）

[2]林遵虎，蔡秉江，薛松，等.一種智能化的樞紐站軌道交通換乘線路調(diào)度方法[J]．電子設(shè)計(jì)工程，2024，32（24）：167-170，175.（LinZunhu，CaiBingjiang，Xue Song，etal.Aninteligent rail tran-sittransferline schedulingmethod forhub station[J].ElectronicDesignEngineering，2024，32（24）：167-170，175.）

[3]曹馳.高峰時(shí)段城市軌道交通列車調(diào)度策略研究[J].人民公交，2024（20）：73-75.（Cao Chi.Study on train scheduling strategy ofurban rail transit duringpeak hours[J].People’s Public Trans-portation，2024（20）：73-75.）

[4]藺一帥，李青山，陸鵬浩，等.智能倉儲(chǔ)貨位規(guī)劃與AGV路徑規(guī)劃協(xié)同優(yōu)化算法[J].軟件學(xué)報(bào)，2020，31（9）：2770-2784.（LinYishuai，LiQingshan，LuPenghao，etal.Shelf and AGVpathcoo-perative optimizationalgorithmusedinintelligentwarehousing[J].Journal of Software，2020，31（9）：2770-2784.）

[5]Yuan Zhiheng，Yang Zhengmao，Lyu Lingling，et al．A bi-level pathplanning algorithm for multi-AGV routing problem[J]. Electronics，2020，9（9）：1351.

[6]Unsal O，Oguz C.Constraint programming approach to quay craneschedulingproblem[J].TransportationResearchPartE：Logis-ticsandTransportationReview，2013，59：108-122.

[7]余娜娜，李鐵克，王柏琳，等.自動(dòng)化分揀倉庫中多AGV調(diào)度與路徑規(guī)劃算法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2020，26（1）：171-180.（Yu Nana，Li Tieke，Wang Bailin，etal.Multi-AGVsschedulingandpath planning algorithm inautomated sorting warehouse[J].Computer Integrated Manufacturing Systems，2020，26（1）：171-180.）

[8]邵乾虔，徐奇，邊展，等.考慮了交箱時(shí)間不確定性的場橋堆存作業(yè)優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2015，35（2）：394-405.（Shao Qianqian，Xu Qi， Bian Zhan，et al. Stockpiling operating op-timization foryard crane with containers delivery time uncertainty[J].Systems Engineering-Theory amp; Practice，2015，35（2）：394-405.）

[9]Zou Wenqiang，PanQuanke，Tasgetiren MF.An effective discreteartificial bee colony algorithm for scheduling an automatic-guided-vehiclein a linear manufacturing workshop[J].IEEE Access，2020，8：35063-35076.

[10]盛鵬程，羅新聞，李景蒲，等.智能電動(dòng)車彎曲道路場景中的避障路徑規(guī)劃[J].交通運(yùn)輸工程學(xué)報(bào)，2020，20（2）：195-204.（ShengPengcheng，Luo Xinwen，Li Jingpu，et al.Obstacle avoi-dancepath planning of intelligent electric vehicles in windingroadscene[J]. Journal of Traffc and Transportation Engineering，2020，20（2）：195-204.）

[11］馬昌喜，何瑞春，熊瑞琦.基于雙層規(guī)劃的危險(xiǎn)貨物配送路徑魯棒優(yōu)化[J].交通運(yùn)輸工程學(xué)報(bào)，2018，18（5）：165-175.（Ma Chang-xi，He Ruichun，Xiong Ruiqi.Robust optimization on distributingroutes of hazardous materials based onbi-level programming[J].Journal ofTrafficand TransportationEngineering，2O18，18（5）：165-175.）

[12]Farooq B，Bao Jinsong，Ma Qingwen.Flow-shop predictive modelingfor multi-automated guided vehicles scheduling in smart spinning cy-ber-physical production systems [J]. Electronics，2020，9（5）：799.

[13]李睿，朱笑笑，欒楠.工廠環(huán)境多AGV動(dòng)態(tài)調(diào)度系統(tǒng)的組合優(yōu)化[J].機(jī)械設(shè)計(jì)與研究，2019，35（6）：37-42.（LiRui，Zhu Xiaoxiao，Luan Nan. Multi-AGV dynamic scheduling system and combinationoptimization algorithm for factory environment[J].Machine Designamp; Research，2019，35（6）：37-42.）

[14]程傳奇，郝向陽，李建勝，等.融合改進(jìn) A^* 算法和動(dòng)態(tài)窗口法的全局動(dòng)態(tài)路徑規(guī)劃[J].西安交通大學(xué)學(xué)報(bào)，2017，51（11）：137-143.（Cheng Chuanqi，Hao Xiangyang，Li Jiansheng，et al.Globaldynamicpath planningbased on fusionof improved A^* algorithmanddynamicwindow approach[J].Journal of Xi'an Jiaotong Univer-sity，2017，51（11）：137-143.）

[15]Sun Yinghui，F(xiàn)ang Ming，Su Yixin.AGVpath planning based onimproved Dijkstra algorithm[J].Journal of Physics：ConferenceSeries，2021，1746（1）：012052.

[16]Zhang Zheng，Guo Qing，Chen Juan，et al.Collision-free route plan-ning for multiple AGVs in anautomated warehouse based oncollisionclassification[J]. IEEE Access，2018，6：26022-26035.

[17]Manafi E，Tavakkoli-MoghaddamR，Mahmoodjanloo M.A centroidopposition-based coral reefs algorithm for solving an automated guidedvehicle routing problemwith a recharging constraint[J].AppliedSoft Computing，2022，128：109504.

[18］張崢煒，陳波，陳衛(wèi)東.時(shí)間窗約束下的AGV動(dòng)態(tài)路徑規(guī)劃[J].微型電腦應(yīng)用，2016，32（11）：46-49.（ZhangZhengwei，ChenBo，Chen Weidong. Dynamic routing of automated guided vehicleswith timewindow [J].Microcomputer Applications，2016，32（11）：46-49.）

[19]蘇磊，江輝仙.樓宇內(nèi)部路徑規(guī)劃算法研究及其應(yīng)用綜述[J].測繪與空間地理信息，2014，37（10）：105-109.（SuLei，JiangHui-xian.Building internal path planningalgorithmand itsapplicationre-viewedresearch[J].Geomaticsamp; Spatial InformationTechnolo-gy，2014，37（10）：105-109.）

[20]廖凱文.多AGV路徑規(guī)劃優(yōu)化算法及調(diào)度系統(tǒng)的研究[D].合肥：合肥工業(yè)大學(xué)，202O.（LiaoKaiwen.Research onmulti-AGVpath planning optimization algorithm and scheduling system[D].Hefei：HefeiUniversity of Technology，2020.）

[21]Chen Xuchao，He Shiwei，ZhangYongxiang，et al.Yard crane andAGVschedulingin automated container terminal：amulti-robot taskallocation framework[J].Transportation Research PartC：Emerging Technologies，2020，114：241-271.

[22]Zhong Meisu，Yang Yongsheng，Dessouky Y，etal.Multi-AGVscheduling for conflict-free path planning in automated container ter-minals[J].Computersamp; Industrial Engineering，2020，142：106371.

[23]饒瀚偉.面向智能交通的動(dòng)態(tài)路徑規(guī)劃研究［D].成都：電子科技大學(xué)，2O21.（Rao Hanwei. Research on dynamic path planning forintelligent transportation[D].Chengdu：University of Electronic Sci-ence and Technology of China，2021.）