張帥 古玉鋒 凌浩 黎程山

摘 要：立體軌道交通系統(tǒng)的車輛調(diào)度方法還未見報(bào)道，已有車輛調(diào)度算法的實(shí)時(shí)性較差。針對(duì)立體軌道交通車輛的調(diào)度問(wèn)題，研究了一種結(jié)合高、低頻車站判定的訂單分配算法和一種結(jié)合時(shí)間窗的Dijkstra路徑規(guī)劃算法，即智能調(diào)度算法，以提高車輛的運(yùn)行效率。首先，使用訂單分配算法為訂單選擇合適的執(zhí)行車輛，減少乘客的等待時(shí)間。其次，在訂單分配算法的基礎(chǔ)上增加了高、低頻車站的判定，提前給高頻車站調(diào)度車輛，以保證供需平衡。然后，將普通Dijkstra算法和時(shí)間窗判斷相結(jié)合，以實(shí)現(xiàn)多車輛的無(wú)沖突路徑規(guī)劃。最后，對(duì)OpenTCS軟件進(jìn)行二次開發(fā)，并進(jìn)行了調(diào)度算法的仿真。結(jié)果表明，當(dāng)有乘客叫車時(shí)，若只有訂單分配算法，乘客平均等待時(shí)間為8.043 s；結(jié)合高、低頻車站進(jìn)行車輛提前調(diào)度后，平均等待時(shí)間降到了5.724 s，每位乘客減少了2.319 s的等待時(shí)間。路徑規(guī)劃時(shí)，無(wú)論是普通的Dijkstra算法還是結(jié)合時(shí)間窗的Dijkstra算法，規(guī)劃耗時(shí)都在1 ms以內(nèi)，而結(jié)合時(shí)間窗的Dijkstra算法在只增加約0.1 ms耗時(shí)的情況下，解決了車輛的路徑?jīng)_突問(wèn)題。研究的智能調(diào)度算法減少了乘客的等待時(shí)間，提高了車輛的運(yùn)行效率，實(shí)時(shí)性好，能滿足立體軌道交通車輛的調(diào)度要求。

關(guān)鍵詞：立體軌道交通； 智能調(diào)度； 高頻車站； 訂單分配算法； 時(shí)間窗； Dijkstra算法

中圖分類號(hào)：U292.4 文獻(xiàn)標(biāo)志碼：A?文章編號(hào)：1001-3695（2024）05-009-1343-06

doi：10.19734/j.issn.1001-3695.2023.09.0427

Intelligent scheduling algorithm of three-dimensional rail transit system

based on high-frequency station and time window

Abstract：At present， there are almost no reports on vehicle scheduling methods for three-dimensional rail transit system， and the real-time performance of existing vehicle scheduling algorithms is poor. Aiming at the scheduling problem of three-dimensional rail transit vehicles， this paper studied an order allocation algorithm combining high and low frequency station judgment and a Dijkstra path planning algorithm combining time window， namely intelligent scheduling algorithms， to improve the operating efficiency of vehicles. Firstly， it used the order allocation algorithm to select the appropriate execution vehicle for the order to reduce the waiting time of passengers. Secondly， it added the judgment of high and low frequency stations on the basis of the order allocation algorithm， and scheduled vehicles to the high frequency stations in advance to ensure the balance of supply and demand. Then， it combined the ordinary Dijkstra algorithm and time window judgment to realize multi-vehicle conflict-free path planning. Finally， it redeveloped the OpenTCS software and simulated the scheduling algorithm with the software. The results show that the average waiting time of the passenger from calling the vehicles is 8.043 s only using the order allocation algorithm. After the advance scheduling of vehicles combined with high and low frequency stations， the average waiting time is reduced to 5.724 s， and the waiting time of each passenger is reduced by 2.319 s. During the path planning， both the ordinary Dijkstra algorithm and the Dijkstra algorithm combined with time window took less than 1 ms to plan. However， the Dijkstra algorithm combined with time window only increases the time about 0.1 ms， and solves the problems of the vehicle path conflicts. The studied intelligent scheduling algorithm can reduce the waiting time of the passengers and improve the running efficiency of vehicles. The algorithm has good real-time performance and can meet the scheduling requirements of three-dimensional rail transit vehicles.

Key words：three-dimensional rail transit; intelligent scheduling; high frequency station; order allocation algorithm; time window; Dijkstra algorithm

0 引言

目前，交通擁堵已是城市普遍存在的問(wèn)題。為了緩解交通壓力，軌道交通里程越來(lái)越大，如何更科學(xué)合理地調(diào)度車輛、提高運(yùn)營(yíng)效率、提升乘車體驗(yàn)，是當(dāng)前亟待解決的問(wèn)題［1，2］。智能調(diào)度系統(tǒng)可以實(shí)時(shí)地對(duì)每輛自動(dòng)駕駛車輛進(jìn)行調(diào)度，并根據(jù)運(yùn)行任務(wù)規(guī)劃最優(yōu)路線，可以極大地降低運(yùn)營(yíng)成本，減少乘客的等待時(shí)間，提高服務(wù)質(zhì)量。其中，調(diào)度算法是智能調(diào)度系統(tǒng)的核心。

調(diào)度算法需要考慮車輛避障、算法運(yùn)行效率、公司運(yùn)營(yíng)成本和車輛能源補(bǔ)給等問(wèn)題［3，4］，廣泛地應(yīng)用于軍事、物流及公共交通領(lǐng)域。文獻(xiàn)［5］基于克隆選擇算法，考慮公交車運(yùn)行的時(shí)間表，提出了一種公交車調(diào)度方法，該算法得到調(diào)度解的時(shí)間較長(zhǎng)，實(shí)時(shí)性略差。文獻(xiàn)［6］采用競(jìng)拍算法，通過(guò)運(yùn)輸任務(wù)與車輛間的雙向選擇，對(duì)自動(dòng)引導(dǎo)車（automated guided vehicle，AGV）進(jìn)行調(diào)度，該算法沒(méi)有考慮車輛不同速度的情況。文獻(xiàn)［7］為解決公交車的資源分配問(wèn)題，將遺傳算法與禁忌搜索算法相結(jié)合，提高了求解性能，但不適用于實(shí)時(shí)調(diào)度。文獻(xiàn)［8］針對(duì)艦載機(jī)在機(jī)庫(kù)中的調(diào)度問(wèn)題，采用凸殼算法獲取可行路徑，Dijkstra算法進(jìn)行路徑規(guī)劃，算法沒(méi)有考慮多架飛機(jī)同時(shí)調(diào)度時(shí)可能引發(fā)的路徑?jīng)_突。文獻(xiàn)［9］為了提高乘客叫車請(qǐng)求的響應(yīng)速度，將遺傳算法和貪婪算法結(jié)合，優(yōu)先處理較早的叫車請(qǐng)求，但車輛的運(yùn)行路徑較為單一，沒(méi)有針對(duì)各訂單分別進(jìn)行規(guī)劃路徑。文獻(xiàn)［10］針對(duì)兵場(chǎng)站物資配送車輛的調(diào)度問(wèn)題，在遺傳算法的基礎(chǔ)上增加了模擬退火算法，減少了陷入局部最優(yōu)解的情況發(fā)生，但算法的運(yùn)行時(shí)間較長(zhǎng)，實(shí)時(shí)性差。文獻(xiàn)［11］使用混合粒子群算法對(duì)軌道門吊的調(diào)度任務(wù)進(jìn)行求解，減少了空駛行程，但算法求解時(shí)間在13 s以上，時(shí)間較長(zhǎng)。文獻(xiàn)［12］在軌道交通的調(diào)度問(wèn)題上采用蟻群算法進(jìn)行負(fù)載均衡調(diào)度，系統(tǒng)具有較高的任務(wù)吞吐量，但當(dāng)任務(wù)量較小時(shí)，完成時(shí)間較長(zhǎng)。

由已有文獻(xiàn)可知，當(dāng)前對(duì)于平面交通系統(tǒng)的車輛調(diào)度問(wèn)題，已經(jīng)取得了一定的研究成果。其中，遺傳算法、模擬退火算法等啟發(fā)式算法由于收斂速度較慢，不能滿足立體軌道交通智能調(diào)度系統(tǒng)的實(shí)時(shí)性要求；Dijkstra算法用于解決正權(quán)值的單源最短路徑問(wèn)題是十分有效的［13， 14］，且求解速度快、實(shí)時(shí)性好。對(duì)于立體軌道交通，還需要考慮多車輛之間的路徑?jīng)_突問(wèn)題，通過(guò)判斷各路段的時(shí)間窗是否存在重疊并作出相應(yīng)動(dòng)作，可以提前規(guī)避該問(wèn)題發(fā)生。為此，本文將提前調(diào)度與訂單分配算法結(jié)合，以減少車輛調(diào)度的等待時(shí)間，同時(shí)在Dijkstra算法中增加時(shí)間窗，以避免路徑?jīng)_突，最終實(shí)現(xiàn)車輛的智能調(diào)度。

1 建立數(shù)學(xué)模型

1.1 問(wèn)題描述

車輛調(diào)度要求有較高的實(shí)時(shí)性，即在調(diào)度系統(tǒng)收到調(diào)度請(qǐng)求后，在盡可能短的時(shí)間內(nèi)響應(yīng)請(qǐng)求，并按照調(diào)度規(guī)則，合理地規(guī)劃車輛和路徑，將車輛調(diào)度到指定地點(diǎn)。

本文智能調(diào)度算法的運(yùn)行場(chǎng)景為一棟樓宇里的立體軌道交通，樓內(nèi)豎移電梯與平移軌道車輛無(wú)縫連接，并實(shí)現(xiàn)自動(dòng)駕駛，共同組成立體軌道交通系統(tǒng)。居民可以通過(guò)叫車軟件設(shè)定目的地，由智能調(diào)度系統(tǒng)規(guī)劃路線，點(diǎn)對(duì)點(diǎn)接送。其特征如下：

a）樓宇共五層，每50 m有一個(gè)車站，每個(gè)車站初始狀態(tài)下有兩輛車。

b）樓內(nèi)各層之間有垂直方向運(yùn)行的電梯，通過(guò)垂直軌道將車輛送入平移軌道。

c）車輛平移軌道位于第四層，有正向和反向兩組軌道，各自單向行駛，每組分為低速、中速和高速三條軌道。

d）第四層中，每?jī)蓚€(gè)車站中間設(shè)有一個(gè)低-中速變道裝置，每個(gè)車站處設(shè)有一個(gè)中-高速變道裝置，車輛可通過(guò)變道裝置雙向變道。具體場(chǎng)景如圖1所示。

1.2 模型假設(shè)條件

在智能調(diào)度系統(tǒng)中，公交車有三種狀態(tài)：第一種是空閑狀態(tài)，車輛停泊在車站里等待乘客下訂單或等待調(diào)度系統(tǒng)的調(diào)度命令；第二種是空載狀態(tài)，當(dāng)調(diào)度系統(tǒng)發(fā)出指令將空閑車輛調(diào)度到訂單起點(diǎn)時(shí)，便會(huì)空載運(yùn)行；第三種是載客狀態(tài)，就是執(zhí)行訂單任務(wù)將乘客從起點(diǎn)運(yùn)送到目的地的過(guò)程。由于乘客所在車站和空閑車輛所在車站均具有隨機(jī)性，使得乘客等車的時(shí)間長(zhǎng)短具有不確定性，智能調(diào)度系統(tǒng)可以使每位乘客具有最優(yōu)的等待時(shí)間。因此調(diào)度目標(biāo)是為每位乘客選擇最合適的車輛，盡可能減少車輛的空行程，縮短乘客的等車時(shí)間，使每位乘客盡可能早地開始行程，最終規(guī)劃出耗時(shí)最短的車輛行駛路線。

在調(diào)度系統(tǒng)中，存在很多干擾調(diào)度結(jié)果的變量與影響因素，為了能更好地將其抽象為數(shù)學(xué)模型，本文從車輛的實(shí)際運(yùn)營(yíng)情況出發(fā)，作出以下假設(shè)：

a）所有車輛統(tǒng)一由智能調(diào)度系統(tǒng)進(jìn)行指揮調(diào)度，車輛均為同一型號(hào)，不考慮發(fā)生故障的情況。

b）一輛車在同一時(shí)間只能處理一個(gè)訂單，一個(gè)訂單也只能由一輛車接收并處理，不考慮不同訂單共享車輛的情況。

c）乘客數(shù)量不影響車輛的運(yùn)行速度。

d）由于乘客上下車的時(shí)間為每次接駁的共有因素，對(duì)智能調(diào)度系統(tǒng)的決策不產(chǎn)生影響，故在本文模型中不考慮該因素。

e）不考慮乘客未能及時(shí)到達(dá)車站的情況，即不考慮車輛等待乘客的情況。

1.3 數(shù)學(xué)模型

理時(shí)間，rvi表示處理該訂單的車輛。因?yàn)槊课唤熊嚨某丝蛢H對(duì)應(yīng)一個(gè)叫車請(qǐng)求，所以完全可以用叫車請(qǐng)求代表乘客，下文將不再單獨(dú)考慮乘客個(gè)體。

在智能調(diào)度系統(tǒng)中，為了最大程度地改善乘車體驗(yàn)，提高車輛的運(yùn)行效率，需要將調(diào)度問(wèn)題分為兩部分考慮。首先是訂單分配，即收到訂單后將訂單分配給合適的車輛，可以是空閑車輛，也可以是即將到站的運(yùn)行車輛。分配給運(yùn)行中的車輛時(shí)，需要先等待車輛完成當(dāng)前訂單，再將其調(diào)度到叫車地點(diǎn)。對(duì)此提出第一個(gè)優(yōu)化目標(biāo)：某一時(shí)刻提交的所有訂單中，乘客的平均等待時(shí)間盡可能短；其次是車輛運(yùn)行路徑的規(guī)劃，通過(guò)變道系統(tǒng)適時(shí)地在低速、中速及高速車道之間切換，規(guī)劃出耗時(shí)最短的路線。對(duì)此提出第二個(gè)優(yōu)化目標(biāo)：某一時(shí)刻提交的所有訂單總處理時(shí)間盡可能短。根據(jù)以上內(nèi)容，列出目標(biāo)函數(shù)如下：

目標(biāo)函數(shù)1：

目標(biāo)函數(shù)2：

其中：Thandle為t時(shí)刻所有訂單總處理時(shí)間；tstarti為乘客上車時(shí)間，即車輛出發(fā)時(shí)間；tendi為車輛到達(dá)目的地的時(shí)間。

目標(biāo)函數(shù)1表示在某一時(shí)刻提交的所有訂單中乘客的平均等待時(shí)間；目標(biāo)函數(shù)2表示某一時(shí)刻提交的所有訂單的總處理時(shí)間。為達(dá)到上文中的兩個(gè)優(yōu)化目標(biāo)，需使式（1）和（3）的值盡可能小。下文將結(jié)合訂單分配算法和路徑規(guī)劃算法對(duì)目標(biāo)進(jìn)行優(yōu)化。

2 智能調(diào)度算法研究

2.1 訂單分配算法

訂單分配算法的主要目標(biāo)是優(yōu)化乘客的等車時(shí)間，提高交通系統(tǒng)的運(yùn)行效率。訂單分配算法的著重點(diǎn)在于為每一個(gè)訂單選擇合適的車輛，當(dāng)車輛接收到訂單任務(wù)后，只需按訂單指示的站點(diǎn)運(yùn)行即可。本節(jié)將以目標(biāo)函數(shù)1為優(yōu)化目標(biāo)設(shè)計(jì)訂單分配算法。

運(yùn)用上述訂單分配算法，可以選出合適的車輛，使乘客等車時(shí)間盡可能短，從而提高系統(tǒng)的運(yùn)行效率。然而，在實(shí)際運(yùn)營(yíng)場(chǎng)景中，各個(gè)車站的人流量以及訂單數(shù)量存在較大差異，由此出現(xiàn)了一些高頻車站和低頻車站。為此，本文提出一種提前調(diào)度的方法，對(duì)調(diào)度系統(tǒng)進(jìn)行進(jìn)一步優(yōu)化。

提前調(diào)度是指在系統(tǒng)收到訂單之前就開始進(jìn)行車輛的調(diào)度工作，向高頻車站派遣更多車輛。當(dāng)一個(gè)車站被判定為高頻車站時(shí)，調(diào)度系統(tǒng)會(huì)提前將低頻車站的部分空閑車輛調(diào)度到該車站，以保證供需平衡，盡可能避免接收到訂單后由于起始站空閑車輛不足而需要從其他車站調(diào)度車輛的情況，從而縮短乘客不必要的等車時(shí)間。據(jù)此提出的高、低頻車站的判定公式如式（5）（6）所示。

NR（T）表示0～T時(shí)間段內(nèi)的訂單數(shù)量。

設(shè)高頻車站的頻率閾值為Phigh，低頻車站的頻率閾值為Plow。如果Psi（T）>Phigh，則認(rèn)為車站si在該時(shí)間段內(nèi)為高頻車站；如果Psi（T）

2.2 結(jié)合時(shí)間窗的路徑規(guī)劃算法

上文解決了訂單分配的相關(guān)問(wèn)題，下一個(gè)問(wèn)題是已知車輛起始站和終點(diǎn)站的情況下的路徑規(guī)劃問(wèn)題。本節(jié)將以目標(biāo)函數(shù)2為優(yōu)化目標(biāo)，設(shè)計(jì)車輛的路徑規(guī)劃算法。

Dijkstra算法是一種具有代表性的單源最短路徑算法，結(jié)合了貪心思想和松弛操作，從起始點(diǎn)開始逐層向外擴(kuò)展，直到找出其他所有節(jié)點(diǎn)的最短路徑。由于車輛是在軌道上行駛的，并不能通過(guò)變換位置來(lái)給其他車輛讓行，所以在多車輛的環(huán)境中，如果分別對(duì)各個(gè)車輛進(jìn)行路徑規(guī)劃，必然會(huì)出現(xiàn)路徑?jīng)_突的情況。本文的路徑?jīng)_突主要表現(xiàn)為兩種變道沖突，一種是變道車輛與已在目標(biāo)車道上運(yùn)行的車輛產(chǎn)生的沖突，如圖3所示；另一種是交叉變道時(shí)產(chǎn)生的沖突，如圖4所示。對(duì)此需要引入時(shí)間窗的概念，將其與Dijkstra算法相結(jié)合，達(dá)到所有車輛均能正常運(yùn)行的目的。

時(shí)間窗主要是指某一路段被某一車輛所占用的時(shí)間段，設(shè)Windowspvi=［tstartvi，p，tendvi，p］表示車輛vi通過(guò)路段p所占用的時(shí)間窗，tstartvi，p表示時(shí)間窗的開始時(shí)間，tendvi，p表示時(shí)間窗的結(jié)束時(shí)間。使用Dijkstra算法規(guī)劃路徑時(shí)，系統(tǒng)會(huì)給車輛途徑的每個(gè)路段分配時(shí)間窗，通過(guò)避免時(shí)間沖突來(lái)保證各車輛的正常運(yùn)行。基于該思想，列出以下不等式：

式（7）表示在車輛vi離開路段p時(shí)，車輛vj還未到達(dá)該路段。式（8）表示在車輛vi到達(dá)路段p時(shí)，車輛vj已經(jīng)離開該路段。當(dāng)路徑中的所有路段均滿足以上兩個(gè)公式時(shí)，即可避免車輛發(fā)生碰撞，若某個(gè)路段不滿足條件，則增大該路段的權(quán)值并重新使用Dijkstra算法規(guī)劃路徑。

在高頻車站附近的路段和變道裝置時(shí)間窗非常密集，這將導(dǎo)致系統(tǒng)頻繁重新規(guī)劃路徑，造成資源浪費(fèi)。為提高系統(tǒng)效率，在使用式（5）（6）確認(rèn)出高頻車站以后，將進(jìn)出這些站點(diǎn)必經(jīng)的路段以及變道裝置的權(quán)值適當(dāng)提高，在首次規(guī)劃路徑時(shí)就盡可能地避開這些車流量大的路段，減少重新規(guī)劃路徑的次數(shù)。圖5為當(dāng)車站C三樓被列為高頻站點(diǎn)時(shí)，提高權(quán)值的路段示意圖。改進(jìn)后的路徑規(guī)劃算法具體流程如下：

a）訪問(wèn)訂單列表，查詢并統(tǒng)計(jì)所有訂單的起始站和終點(diǎn)站。

b）通過(guò)式（5）（6）計(jì)算各站點(diǎn)出現(xiàn)的頻率，然后判斷并記錄下高頻車站。

c）提高進(jìn)出高頻站點(diǎn)必經(jīng)路段和變道裝置的權(quán)值。

d）獲取當(dāng)前訂單中（或調(diào)度任務(wù)中）的起始站和終點(diǎn)站。

e）使用Dijkstra算法找出最短路徑。

f）為途徑的每個(gè)路段分配時(shí)間窗。

g）遍歷每個(gè)時(shí)間窗，分別使用式（7）（8）進(jìn)行判斷。

h）若每個(gè)時(shí)間窗都滿足式（7）或（8），則跳轉(zhuǎn)至步驟j），否則進(jìn)入步驟i）。

i）提高不符合條件的路段權(quán)值，然后跳轉(zhuǎn)至步驟e）。

j）完成路徑規(guī)劃。

路徑規(guī)劃算法的流程如圖6所示。

3 算法的仿真與結(jié)果分析

3.1 建立地圖模型

OpenTCS軟件是一款開源的有軌自動(dòng)小車可視化仿真軟件，本文使用該軟件建立地圖模型，并在此軟件框架的基礎(chǔ)上進(jìn)行二次開發(fā)，以測(cè)試本文所研究的訂單分配算法和路徑規(guī)劃算法。在OpenTCS軟件上建立的地圖模型如圖7所示，模型由三條軌道和55個(gè)站點(diǎn)組成，軌道上總共有11個(gè)車站，每個(gè)車站都有5個(gè)站點(diǎn)可以選擇，分別對(duì)應(yīng)五個(gè)樓層。三條軌道從上到下分別對(duì)應(yīng)低速、中速、高速軌道。

3.2 仿真結(jié)果與分析

首先是訂單分配，本文先在某一路段內(nèi)隨機(jī)生成一組車輛位置，有的正在軌道上運(yùn)行，有的在車站里處于空閑狀態(tài)。然后又隨機(jī)生成十個(gè)叫車地點(diǎn)，分別用本文研究的訂單分配算法給車輛分配訂單，記錄車輛收到訂單后調(diào)度到叫車地點(diǎn)的用時(shí)。實(shí)驗(yàn)數(shù)據(jù)如表1和2所示，其中V（vehicle）代表車輛，P（point）代表點(diǎn)，L（location）代表車站位置，實(shí)驗(yàn)結(jié)果如圖8所示。當(dāng)某車站有乘客提交訂單時(shí)，無(wú)論是將訂單分配給運(yùn)行中的車輛，還是分配給空閑車輛，都會(huì)存在比另一方等待時(shí)間更長(zhǎng)的情況，而通過(guò)訂單分配算法，可以使乘客的等待時(shí)間達(dá)到最短。

在表2中，十個(gè)叫車地點(diǎn)中L-038和L-050兩個(gè)車站均出現(xiàn)了兩次，將其設(shè)為高頻車站，提前給這兩個(gè)車站增派其他路段的空閑車輛后，乘客的等待時(shí)間如圖9所示。經(jīng)計(jì)算，結(jié)合提前調(diào)度后，乘客平均等待時(shí)間由8.043 s降到了5.724 s，相當(dāng)于每位乘客減少了2.319 s的等待時(shí)間。

在路徑規(guī)劃算法的仿真中，本文隨機(jī)生成了十個(gè)訂單，分別用結(jié)合時(shí)間窗的Dijkstra算法和普通Dijkstra算法進(jìn)行了路徑規(guī)劃。由于普通Dijkstra算法規(guī)劃的路徑不考慮各車輛的路徑?jīng)_突，規(guī)劃出來(lái)的路線參考價(jià)值不大，所以本文只對(duì)其規(guī)劃耗時(shí)進(jìn)行對(duì)比分析。本次仿真所用到的訂單如表3所示。結(jié)合時(shí)間窗的Dijkstra算法所規(guī)劃出的部分路徑如圖10所示。

圖11為分別用結(jié)合時(shí)間窗的Dijkstra算法和普通Dijkstra算法對(duì)這十個(gè)訂單進(jìn)行路徑規(guī)劃的耗時(shí)，兩者的規(guī)劃耗時(shí)都在1 ms以內(nèi)。通過(guò)表4對(duì)比可見，本文算法的平均執(zhí)行時(shí)間遠(yuǎn)小于已有的啟發(fā)式算法。結(jié)合時(shí)間窗的Dijkstra算法由于增加了時(shí)間窗判定流程，比普通Dijkstra算法用時(shí)略長(zhǎng)，增加了約0.1 ms，但對(duì)于路徑?jīng)_突來(lái)說(shuō)，是非常有意義的。

圖11中的4號(hào)訂單規(guī)劃用時(shí)為0.558 ms，顯著長(zhǎng)于其他訂單規(guī)劃用時(shí)，原因是首次路徑規(guī)劃時(shí)檢測(cè)到了路徑?jīng)_突，并且在提高沖突路段權(quán)值后重新進(jìn)行了路徑規(guī)劃。如圖12所示，紅色路徑為n號(hào)訂單規(guī)劃好的路徑，在m號(hào)訂單規(guī)劃路徑時(shí)，初次規(guī)劃的路徑與n號(hào)訂單相同，但由于檢測(cè)到了兩者之間存在時(shí)間窗沖突，系統(tǒng)便提高了沖突路段的權(quán)值，重新規(guī)劃的路徑如圖12中藍(lán)色路徑所示。與原路徑相比，相當(dāng)于車輛通過(guò)提前變道避免了這次路徑?jīng)_突。

4 結(jié)束語(yǔ)

本文針對(duì)立體軌道交通系統(tǒng)的調(diào)度問(wèn)題，將算法分為訂單分配算法和路徑規(guī)劃算法兩部分進(jìn)行考慮。研究了一種立體軌道交通車輛的訂單分配算法，根據(jù)乘客的叫車地點(diǎn)，選擇調(diào)度時(shí)間最短的車輛進(jìn)行訂單分配，減少了乘客的等待時(shí)間。在該算法的基礎(chǔ)上增加了高、低頻車站的判定，提前給高頻車站調(diào)度空閑車輛，進(jìn)一步減少了乘客的等待時(shí)間。針對(duì)多車輛情況下普通Dijkstra算法規(guī)劃路徑時(shí)不考慮路徑?jīng)_突的問(wèn)題，研究了一種結(jié)合時(shí)間窗的Dijkstra算法，通過(guò)時(shí)間窗判斷是否存在路徑?jīng)_突，若存在沖突則提高相應(yīng)路段的權(quán)值，并重新使用Dijkstra算法規(guī)劃路徑，保證所有車輛都能正常運(yùn)行。

結(jié)合本文算法對(duì)OpenTCS軟件進(jìn)行了二次開發(fā)，并進(jìn)行仿真測(cè)試。測(cè)試結(jié)果表明，當(dāng)乘客發(fā)起叫車請(qǐng)求時(shí)，在訂單分配算法的基礎(chǔ)上增加提前調(diào)度后，有效地將乘客的平均等待時(shí)間由8.043 s降到了5.724 s，減少了2.319 s。其次，路徑規(guī)劃時(shí)，結(jié)合時(shí)間窗的Dijkstra算法和普通Dijkstra算法的規(guī)劃耗時(shí)都在1 ms以內(nèi)，而結(jié)合時(shí)間窗的Dijkstra算法在只增加約0.1 ms耗時(shí)的情況下，實(shí)現(xiàn)了無(wú)沖突的路徑規(guī)劃，使所有車輛均可正常運(yùn)行。本文研究的調(diào)度算法和已有算法相比，有實(shí)時(shí)性高、規(guī)劃耗時(shí)短等優(yōu)點(diǎn)，可以滿足立體軌道交通系統(tǒng)的調(diào)度要求。算法的下一步研究將引入車站間距、變道裝置的數(shù)量等因素，對(duì)算法作進(jìn)一步優(yōu)化。

參考文獻(xiàn)：

［1］張思維， 魏昕怡， 邱桃榮. 優(yōu)化公交車調(diào)度的多目標(biāo)遺傳算法模型［J］. 南昌大學(xué)學(xué)報(bào)： 理科版， 2022，46（1）： 60-65. （Zhang Siwei， Wei Xinyi， Qiu Taorong. Multi-objective genetic algorithm model for optimizing bus dispatch［J］. Journal of Nanchang University： Natural Science， 2022，46（1）： 60-65.）

［2］趙娜， 袁家斌， 徐晗. 智能交通系統(tǒng)綜述［J］. 計(jì)算機(jī)科學(xué)， 2014，41（11）： 7-11，45. （Zhao Na， Yuan Jiabin， Xu Han. Survey on intelligent transportation system［J］. Computer Science， 2014，41（11）： 7-11，45.）

［3］Li Jingquan. Transit bus scheduling with limited energy［J］. Transportation Science， 2014，48（4）： 521-539.

［4］Tang Jiafu， Guan Jing， Yu Yang， et al. Beam search combined with MAX-MIN ant systems and benchmarking data tests for weighted vehicle routing problem［J］. IEEE Trans on Automation Science and Engineering， 2014，11（4）： 1097-1109.

［5］Shui Xinguo， Zuo Xingquan， Chen Cheng， et al. A clonal selection algorithm for urban bus vehicle scheduling［J］. Applied Soft Computing， 2015，36： 36-44.

［6］Lim J K， Kim K H， Yoshimoto K， et al. A dispatching method for automated guided vehicles by using a bidding concept［J］. OR Spectrum， 2003，25（1）： 25-44.

［7］Zhang Feizhou， Cao Xuejun， Yang Donggai. Intelligent scheduling of public traffic vehicles based on a hybrid genetic algorithm［J］. Tsinghua Science and Technology， 2008，13（5）： 625-631.

［8］司維超， 齊玉東， 韓維. 基于融合Dijkstra的凸殼算法的艦載機(jī)機(jī)庫(kù)調(diào)運(yùn)規(guī)劃［J］. 系統(tǒng)工程與電子技術(shù)， 2015， 37（3）： 583-588. （Si Weichao， Qi Yudong， Han Wei. Carrier plane transportation in hangar based on convex hull algorithm combined with Dijkstra［J］. Systems Engineering and Electronics， 2015，37（3）： 583-588.）

［9］李爽， 楊明， 王春香， 等. 面向全自動(dòng)控制交通系統(tǒng)的車輛調(diào)度算法［J］. 上海交通大學(xué)學(xué)報(bào)， 2017， 51（2）： 174-179. （Li Shuang， Yang Ming， Wang Chunxiang， et al. Scheduling algorithm for vehicles in cybernetic transportation system［J］. Journal of Shanghai Jiaotong University， 2017，51（2）： 174-179.）

［10］閻哲， 汪民樂(lè)， 汪江鵬， 等. 基于混合遺傳算法的海軍航空兵場(chǎng)站物資配送車輛調(diào)度智能優(yōu)化［J］. 系統(tǒng)工程與電子技術(shù)， 2023，45（12）：3908-3914. （Yan Zhe， Wang Minle， Wang Jiangpeng， et al. Intelligent optimization of vehicle scheduling for material distribution in naval aviation station based on hybrid genetic algorithm［J］. Systems Engineering and Electronics， 2023，45（12）：3908-3914.

［11］王力， 朱曉寧， 閆偉， 等. 鐵路集裝箱中心站軌道門吊調(diào)度優(yōu)化模型與算法［J］. 鐵道學(xué)報(bào)， 2014，36（5）： 8-13. （Wang Li， Zhu Xiaoning， Yan Wei， et al. Optimization model and algorithm of rail mounted gantry crane scheduling at railway container terminals［J］. Journal of the China Railway Society， 2014，36（5）： 8-13.）

［12］堯海昌， 柴博周， 劉尚東， 等. 基于蟻群算法的軌道交通集群調(diào)度算法研究［J］. 南京郵電大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2018， 38（4）： 81-88. （Yao Haichang， Chai Bozhou， Liu Shangdong， et al. Load balancing scheduling algorithm for rail transit cluster based on ant colony algorithm［J］. Journal of Nanjing University of Posts and Telecommunications： Natural Science Edition， 2018，38（4）： 81-88.）

［13］宋翠穎， 王鶴玲， 田澤尚， 等. 需求響應(yīng)式公交車輛調(diào)度模型和算法研究綜述［J］. 北京交通大學(xué)學(xué)報(bào)，2023，47（4）：31-44. （Song Cuiying， Wang Heling， Tian Zeshang， et al. Review of demand-responsive transit vehicle scheduling models and algorithms［J］. Journal of Beijing Jiaotong University， 2023，47（4）：31-44.）

［14］Akram M， Habib A， Alcantud J C R. An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers［J］. Neural Computing and Applications， 2021，33（4）： 1329-1342.