考慮道路限制的建設(shè)場地內(nèi)車輛調(diào)度問題研究

李國儉 徐君 吳海軍 沈磊 王一夫 李憲利 鄭漢坤

DOI：10.3976/j.issn.1002-4026.20230047

收稿日期：2023-03-17

作者簡介：李國儉（1977—），男，高級工程師，研究方向?yàn)槟茉措娏夹g(shù)。E-mail：lgjian77@126.com

*通信作者，沈磊，男，工程師，研究方向?yàn)樾履茉窗l(fā)電。E-mail ：2733797096@qq.com

摘要：針對大型設(shè)備運(yùn)輸車輛進(jìn)入建設(shè)場地后，在場內(nèi)道路上的車輛調(diào)度和路徑規(guī)劃問題進(jìn)行了研究。受場內(nèi)道路寬度限制，車輛難以在同一道路上相向行駛；同時(shí)，由于不同車輛所運(yùn)輸?shù)呢浳锛斑\(yùn)輸任務(wù)的緊急程度不同，車輛的通行具有不同優(yōu)先級。針對上述特性，利用時(shí)空網(wǎng)絡(luò)技術(shù)構(gòu)建整數(shù)規(guī)劃模型，在考慮道路限制和不同車輛優(yōu)先級情況下，對建設(shè)場地內(nèi)的車輛進(jìn)行調(diào)度和會車規(guī)避。模型的目標(biāo)為最小化所有車輛在場內(nèi)的總時(shí)間，包括行駛時(shí)間和會車等待時(shí)間；模型包含兩類約束，即車輛流平衡約束和車輛會車避讓約束。為快速有效地求解模型，設(shè)計(jì)基于時(shí)空網(wǎng)絡(luò)的啟發(fā)式算法得到各車輛的時(shí)空路徑，為車輛的路徑規(guī)劃和會車避讓提供指導(dǎo)。結(jié)合一個(gè)實(shí)際的大型風(fēng)電場路網(wǎng)，構(gòu)建多個(gè)算例，對模型和算法的有效性進(jìn)行驗(yàn)證。結(jié)果表明，提出的算法能迅速對不同規(guī)模的問題進(jìn)行求解；另外，算法可以在消除車輛時(shí)空沖突的同時(shí)，保證車輛在會車時(shí)不等待過長時(shí)間，最終的方案具有較高的車輛運(yùn)輸效率。

關(guān)鍵詞：建設(shè)場地；道路限制；車輛調(diào)度問題；時(shí)空網(wǎng)絡(luò)；沖突規(guī)避

中圖分類號：U492.33??? 文獻(xiàn)標(biāo)志碼：A??? 文章編號：1002-4026（2024）03-0076-09

開放科學(xué)（資源服務(wù)）標(biāo)志碼（OSID）：

The vehicle scheduling problem at a construction

site considering road restrictions

LI Guojian1，XU Jun2，WU Haijun2，SHEN Lei2*，WANG Yifu2，LI Xianli2，ZHENG Hankun3

（1. SPIC Nei Mongol Energy Co.， Ltd.， Tongliao 028011，China；2. Inner Mongolia Chahar New Energy Co.， Ltd.，

Wulanchabu 011800，China; 3. School of Systems Science，Beijing Jiaotong University， Beijing 100044， China）

Abstract∶This study investigates vehicle scheduling and path planning problems on field roads after large equipment transportation vehicles enter construction sites. Due to road width limitations and varying task priorities， vehicles have difficulty traveling in opposite directions on the same road. Furthermore， the large equipment transportation vehicles have different priorities depending on their loads and urgency of the transportation. To address these challenges， this study constructs an integer programming model based on spatiotemporal network technology that minimizes the total travel time of all vehicles on the site by considering road restrictions and vehicle priorities. Furthermore， vehicle flow balance and meeting avoidance constraints are incorporated into the model. Moreover， a heuristic algorithm is designed to efficiently solve the model and obtain the spatiotemporal path of each vehicle， thereby providing guidance for vehicle path planning and passing each other. The effectiveness of the proposed model and algorithm is demonstrated through multiple cases based on an actual wind farm road network. The computational results show that the algorithm can quickly solve the vehicle path planning problem at various scales. Additionally， it can guarantee short waiting time to avoid vehicle meeting while eliminate spatiotemporal conflicts. Moreover， the proposed approach showed high transportation efficiency.

Key words∶construction site; road restriction; vehicle scheduling problem; spatiotemporal network; conflict avoidance

隨著社會各類工程建設(shè)進(jìn)程的不斷加快，大型設(shè)備、構(gòu)件及物料運(yùn)輸車輛的路徑規(guī)劃逐漸成為熱點(diǎn)問題，尤其是在建設(shè)場地內(nèi)的路徑規(guī)劃問題。在建設(shè)場地內(nèi)，由于場內(nèi)道路寬度有限，往往存在因道路狹窄導(dǎo)致大型貨物運(yùn)輸車輛無法正常會車的情況，即場內(nèi)道路不能滿足運(yùn)輸車輛在同一路段上對向行駛會車通過。同時(shí)，場內(nèi)運(yùn)輸車輛作業(yè)通常較為繁忙，從優(yōu)化運(yùn)輸效率、節(jié)約運(yùn)輸時(shí)間的角度，在場內(nèi)長距離道路上設(shè)置會車點(diǎn)可以保證對向行駛車輛順利會車通行。但是在車輛會車避讓過程中，如果車輛會車調(diào)度不合理，則會增加運(yùn)輸車輛的會車等待時(shí)間，甚至?xí)斐蓤鰞?nèi)道路擁堵，降低車輛利用率，影響設(shè)備及物料配送效率，造成運(yùn)輸人力與物力的浪費(fèi)，導(dǎo)致運(yùn)輸成本增加。因此，如何對建設(shè)場地內(nèi)大型運(yùn)輸車輛進(jìn)行更為科學(xué)合理的路徑規(guī)劃，并對場內(nèi)車輛進(jìn)行調(diào)度管理來進(jìn)行會車避讓，是一個(gè)具有實(shí)際意義的課題。

現(xiàn)有考慮道路限制的大型貨物運(yùn)輸車輛路徑研究主要集中于為裝載大型設(shè)備的運(yùn)輸車輛進(jìn)行遠(yuǎn)途路徑規(guī)劃，通過綜合考慮大型貨物公路運(yùn)輸?shù)陌踩浴⒔?jīng)濟(jì)性、時(shí)效性等影響因素，建立其運(yùn)輸路線選擇模型［1-4］，但未進(jìn)一步針對運(yùn)輸車輛在受限的場內(nèi)道路中如何選擇運(yùn)輸路徑的問題進(jìn)行探討。而在針對場內(nèi)運(yùn)輸車輛路徑問題的研究中，大多基于交通仿真技術(shù)對場內(nèi)交通運(yùn)行情況進(jìn)行模擬，以達(dá)到減少場內(nèi)交通擁堵和交通事故的目的。鄭家祥等［5］應(yīng)用系統(tǒng)仿真的方法對施工場內(nèi)交通運(yùn)輸過程進(jìn)行了仿真研究；劉寧［6］建立了基于土石方調(diào)配模型的施工場內(nèi)交通仿真與優(yōu)化模型，給出了仿真與優(yōu)化流程，并將其應(yīng)用于優(yōu)化過程中；周思等［7］提出以運(yùn)距最短為前提，綜合考慮各道路行車密度、運(yùn)輸強(qiáng)度、岔口壓力以及運(yùn)輸機(jī)械的載重量、運(yùn)行限制等因素，尋求最優(yōu)的物料運(yùn)輸線路。但大多數(shù)研究對象僅涉及大壩工程的施工場內(nèi)模擬，對場內(nèi)交通運(yùn)輸?shù)挠绊懸蛩乜紤]不充分。同時(shí)，大部分現(xiàn)有研究均使用仿真模擬方法來對場內(nèi)運(yùn)輸車輛路徑問題進(jìn)行研究，缺乏從數(shù)學(xué)建模的角度來對車輛路徑進(jìn)行系統(tǒng)優(yōu)化。

時(shí)空網(wǎng)絡(luò)建模方法在車輛路徑規(guī)劃領(lǐng)域有著廣泛應(yīng)用［8］，該類模型根據(jù)實(shí)際路網(wǎng)中的路口節(jié)點(diǎn)和路段來構(gòu)造時(shí)空網(wǎng)絡(luò)的節(jié)點(diǎn)和弧，可以更精確地獲得離散時(shí)間下車輛從出發(fā)到駛至客戶點(diǎn)途徑各節(jié)點(diǎn)的時(shí)刻，有利于運(yùn)輸車輛的調(diào)配。一些學(xué)者利用時(shí)空網(wǎng)絡(luò)建模方法，考慮不同現(xiàn)實(shí)場景約束的運(yùn)輸車輛路徑規(guī)劃展開了深入研究。Yan等［9］為搬家公司開發(fā)了一個(gè)優(yōu)化客戶選擇和車輛調(diào)度的模型，通過構(gòu)建時(shí)空網(wǎng)絡(luò)模型來描述運(yùn)輸車輛的裝卸活動(dòng)和最大化靈活客戶方的選擇，并基于分解算法來進(jìn)行有效求解。Wang等［10］利用時(shí)空網(wǎng)絡(luò)構(gòu)建了一個(gè)兩階段的拾取和交付問題模型。高一鷺等［11］提出了一種基于時(shí)空網(wǎng)絡(luò)的路徑優(yōu)化方法，以解決自動(dòng)化集裝箱碼頭運(yùn)輸中的路徑?jīng)_突問題。吳正陽等［12］采用時(shí)空網(wǎng)絡(luò)模型來避免子回路的產(chǎn)生，對車輛配送路線規(guī)劃問題進(jìn)行更加直觀準(zhǔn)確的描述，該模型以擴(kuò)大模型規(guī)模為代價(jià)豐富了車輛配送路徑選擇方案，并求解車輛到達(dá)、離開客戶點(diǎn)的時(shí)刻。以上文獻(xiàn)結(jié)合貨物及物料配送領(lǐng)域中存在的實(shí)際應(yīng)用問題進(jìn)行研究討論，利用時(shí)空網(wǎng)絡(luò)方法對具體場景進(jìn)行準(zhǔn)確描述，提高了運(yùn)輸車輛作業(yè)調(diào)度及路徑規(guī)劃的效率，但未有文獻(xiàn)采用時(shí)空網(wǎng)絡(luò)方法來對考慮道路寬度限制的場內(nèi)運(yùn)輸車輛路徑規(guī)劃問題進(jìn)行研究。

本文采用時(shí)空網(wǎng)絡(luò)建模方法研究了建設(shè)場地內(nèi)的大型車輛調(diào)度問題，在該場景下考慮道路限制造成的車輛會車避讓，對場內(nèi)車輛進(jìn)行調(diào)度及會車引導(dǎo)，從而避免時(shí)空沖突。針對研究問題，提出了基于時(shí)空網(wǎng)絡(luò)的場內(nèi)車輛路徑規(guī)劃模型與算法，優(yōu)化場內(nèi)不同種類的運(yùn)輸車輛通過會車點(diǎn)的次序，并對比場內(nèi)所有運(yùn)輸車輛在時(shí)空網(wǎng)絡(luò)中所占用的弧與對應(yīng)的離散時(shí)間點(diǎn)是否重疊，以此為基礎(chǔ)設(shè)計(jì)算法排開風(fēng)電場內(nèi)所有運(yùn)輸車輛在時(shí)空網(wǎng)絡(luò)中的重疊部分，使得所有車輛在場內(nèi)的總時(shí)間最小。

1? 問題描述

將建設(shè)場地路網(wǎng)抽象為拓?fù)渚W(wǎng)絡(luò)G=S，L，其中，L（l∈L）是拓?fù)渚W(wǎng)絡(luò)中邊的集合，S（s∈S）是拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)集合。節(jié)點(diǎn)包括路口節(jié)點(diǎn)和會車點(diǎn)，S*為會車點(diǎn)集合。以圖1（a）中的實(shí)際路網(wǎng)為例，共包括11條原始路段，12個(gè)節(jié)點(diǎn)。其中原始路段（5， 10）由于距離過長，中途設(shè)置了會車點(diǎn)7以方便場內(nèi)車輛的會車避讓，在拓?fù)渚W(wǎng)絡(luò)中將其視為兩個(gè)路段（5， 7）和（7， 10）。此外，路網(wǎng)中的所有路段均為雙向行駛的單車道，在拓?fù)渚W(wǎng)絡(luò)中一條路段可以看作兩個(gè)有方向的邊l和l′，l和l′方向相反組成一個(gè)沖突邊對l，l′，l和l′不能同時(shí)被占用。最后，圖1（a）對應(yīng)的拓?fù)渚W(wǎng)絡(luò)共包括22條邊，12個(gè)節(jié)點(diǎn)。

基于構(gòu)建的拓?fù)渚W(wǎng)絡(luò)，本文旨在對研究時(shí)段內(nèi)給定的車輛集合進(jìn)行車輛調(diào)度，其中時(shí)間維度用離散的時(shí)間點(diǎn)來表示，而不同車輛具有不同的優(yōu)先級，優(yōu)先級越高的車輛在會車時(shí)優(yōu)先通行，而優(yōu)先級低的車輛則在會車點(diǎn)進(jìn)行避讓等待。本文使用時(shí)空網(wǎng)絡(luò)技術(shù)來直觀、具體地反映車輛會車避讓的等待時(shí)間和時(shí)空軌跡。以圖1（a）中的車輛1和2為例，圖1（b）的時(shí)空網(wǎng)絡(luò)展示了兩個(gè)車輛的時(shí)空軌跡。如圖所示，車輛1和2的路徑?jīng)_突，需對其進(jìn)行會讓指導(dǎo)。考慮車輛1優(yōu)先級高于車輛2，因此車輛2在時(shí)間點(diǎn)5到達(dá)會車點(diǎn)7后，需停車等待，直至車輛1駛出路段（5， 7）后才能駛?cè)肼范危?， 5）。

2? 優(yōu)化模型

2.1? 符號定義

本文涉及的其他符號定義如表1所示。

2.2? 時(shí)空網(wǎng)絡(luò)構(gòu)建

時(shí)空網(wǎng)絡(luò)中的一個(gè)點(diǎn)表示拓?fù)渚W(wǎng)絡(luò)上的節(jié)點(diǎn)在時(shí)間軸上的虛擬拓展點(diǎn)，點(diǎn)的屬性包括其對應(yīng)的拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)、其對應(yīng)的離散時(shí)間點(diǎn)。則時(shí)空網(wǎng)絡(luò)中點(diǎn)的集合為

N={i|ρ1i=s，ρ2i=t，s∈S，t∈T}，（1）

其中，ρ1i為點(diǎn)i對應(yīng)的拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)，ρ2i為點(diǎn)i對應(yīng)的離散時(shí)間點(diǎn)。

時(shí)空網(wǎng)絡(luò)中的弧描述了車輛的活動(dòng)，分為等待弧和行駛弧兩種。其中等待弧表示車輛在會車點(diǎn)進(jìn)行避讓的等待活動(dòng)，只發(fā)生在會車點(diǎn)處。等待弧的起終點(diǎn)所對應(yīng)的拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)相同，且對應(yīng)的離散時(shí)間點(diǎn)相差1，即

Aw={（i，j）|ρ1i=s，ρ1j=s，ρ2i=t－1，ρ2j=t，s∈S*，t∈T＼{1}}。（2）

行駛弧表示車輛在拓?fù)渚W(wǎng)絡(luò)中一條邊上的行駛活動(dòng)，即從邊的起始節(jié)點(diǎn)行駛至其終點(diǎn)節(jié)點(diǎn)。因此，行駛弧是基于拓?fù)渚W(wǎng)絡(luò)中的每條邊構(gòu)建的，行駛弧起終點(diǎn)對應(yīng)拓?fù)渚W(wǎng)絡(luò)中一條邊的起始、終點(diǎn)節(jié)點(diǎn)，且起終點(diǎn)對應(yīng)的離散時(shí)間點(diǎn)差值為邊的車輛行駛時(shí)間，即

Ar={（i，j）|ρ1i=s（l），ρ1j=e（l），ρ2i=t－trunl，ρ2j=t，t∈T＼{1，…，trunl}，l∈L}，（3）

其中拓?fù)渚W(wǎng)絡(luò)中邊對應(yīng)的行駛弧集合為

Arl={（i，j）∈Ar|ρ1i=s（l），ρ1j=e（l），ρ2j－ρ2i=trunl}。（4）

2.3? 模型構(gòu)建

基于上述構(gòu)建的時(shí)空網(wǎng)絡(luò)，本文構(gòu)建了相應(yīng)的場內(nèi)車輛路徑規(guī)劃模型，設(shè)置二元變量xkij（k∈K，（i，j）∈A），其值取1時(shí)表示車輛k經(jīng)過時(shí)空網(wǎng)絡(luò)中的弧（i，j），反之值為0。模型的目標(biāo)為所有車輛在場內(nèi)的總加權(quán)時(shí)間最小，包括等待時(shí)間和行駛時(shí)間。權(quán)重用車輛的優(yōu)先級來衡量，以此確保優(yōu)先級低的車在會車時(shí)進(jìn)行避讓等待，則目標(biāo)函數(shù)為

min Z=∑k∈K∑（i，j）∈Awqkxkij+∑k∈K∑（i，j）∈Arqkxkij（ρ2j－ρ2i） 。（5）

模型的約束包括兩類，即車輛的流平衡約束和車輛會車避讓約束。流平衡約束見式（6）～（10）。其中式（6）表示車輛在給定的起點(diǎn)和時(shí)間入場；式（8）表示車輛最終到達(dá)給定的終點(diǎn)；式（7）和（9）禁止車輛駛回起點(diǎn)和駛出終點(diǎn)，以此來消除車輛路徑上的子回路；式（10）表示車輛在其他點(diǎn)上的流平衡約束。

∑（i，j）∈Ar|ρ1i=ok，ρ2i=tdepkxkij=1，k∈K ，（6）

∑（j，i）∈A|ρ1i=ok，ρ2i=tdepkxkji=0，k∈K ，（7）

∑（i，j）∈Ar|ρ1j=dkxkij=1，k∈K ，（8）

∑（j，i）∈A|ρ1j=dkxkji=0，k∈K ，（9）

∑（i，j）∈Axkij=∑（j，i′）∈Axkji′，j∈N，k∈K|ρ1j∈S＼{ok，dk} 。（10）

車輛會車避讓約束如式（11）所示。對于拓?fù)渚W(wǎng)絡(luò)中的一個(gè)沖突邊對l，l′來說，式（11）表示當(dāng)車輛k′經(jīng)過邊l對應(yīng)的一條行駛弧（i′，j′）時(shí)，離散時(shí)間點(diǎn)ρ2i′前后Δtpass時(shí)間內(nèi)（即區(qū)間［ρ2i′－Δtpass，ρ2i′+Δtpass］）沒有任何其他車輛駛?cè)肼范蝜。

∑k∈K＼{k′}∑（i，j）∈Arl′|ρ2i∈［ρ2i′－Δtpass－trunl′，ρ2j′+Δtpass］xkij≤M（1－xk′i′j′），k′∈K，（l，l′）∈Ω，（i，j）∈Arl 。 （11）

3? 求解算法

上述模型旨在為研究時(shí)段內(nèi)的所有車輛分配一條時(shí)空路徑，每條時(shí)空路徑上不存在任何時(shí)空沖突，目標(biāo)為最小化場內(nèi)所有車輛的時(shí)間。為了快速求解上述模型，本文考慮根據(jù)各車輛給定的起終點(diǎn)，利用Yen算法（偏離路徑法）計(jì)算得到各車輛的K短路徑［13］，之后計(jì)算得到各車輛到達(dá)最短路徑上各節(jié)點(diǎn)和占用各路段的時(shí)間信息。若車輛間存在時(shí)空沖突，根據(jù)沖突車輛優(yōu)先級屬性，首先遍歷尋找優(yōu)先級低的車輛K段路徑集合中未被優(yōu)先級高的車輛占用的K短路，若存在該條路徑，則安排優(yōu)先級低的車輛更改當(dāng)前路徑，按照所搜索到的K短路行駛；若不存在該條路徑，則安排優(yōu)先級低的車輛在會車點(diǎn)等待直到優(yōu)先級高的車輛離開沖突路段。特別地，當(dāng)兩個(gè)車優(yōu)先級相同時(shí)，根據(jù)先到先服務(wù)原則，優(yōu)先讓入場時(shí)間早的車輛進(jìn)入沖突路段。根據(jù)沖突的預(yù)計(jì)發(fā)生時(shí)間，解決當(dāng)前最早發(fā)生的沖突，直到場內(nèi)所有運(yùn)輸車輛都有無沖突的路徑。

對于軌跡時(shí)空沖突較少的情況，算法迭代較少的次數(shù)就可以得到所有車輛間無沖突的時(shí)空路徑。但當(dāng)多個(gè)車輛聚集在路網(wǎng)中的某一區(qū)域時(shí)，可能會產(chǎn)生擁堵現(xiàn)象。此時(shí)，若在調(diào)整車輛行駛路徑時(shí)沒有考慮后續(xù)影響，沖突路段的前1個(gè)節(jié)點(diǎn)的等待或路徑重新調(diào)整可能會導(dǎo)致車輛軌跡的二次沖突。為了解決上述車輛二次沖突和多個(gè)車輛在同一路段存在會車沖突的問題，本文提出了一種基于時(shí)空網(wǎng)絡(luò)的沖突解決方法，如圖2所示。假定需要規(guī)劃運(yùn)輸車輛C在t時(shí)刻經(jīng)過n個(gè)時(shí)間刻度到達(dá)D的路徑，若在時(shí)空網(wǎng)絡(luò)中不存在Ct到Dt+n的通路（路徑中的弧和點(diǎn)被其他運(yùn)輸車輛占用），此時(shí)C需在到達(dá)Dt+n前在會車點(diǎn)處等待wt直至擁堵消除，此時(shí)運(yùn)輸車輛C到達(dá)的時(shí)間網(wǎng)絡(luò)節(jié)點(diǎn)更新為Dt+n+wt。

算法的主要流程如下：

步驟1? 第1輛車進(jìn)入路網(wǎng)，編號i=1，使用Dijkstra算法計(jì)算車輛1行駛的最短路徑，記錄車輛1最短路段集合{［Sp，Sq］}，經(jīng)過路段時(shí)間段集合{［aSp1，dSq1］}，其中aSp1=Gs0spc，dSq1=Gs0sqv，Gs0sp是從起點(diǎn)SO到Sp的距離，c是車速。

步驟2? 每有后續(xù)新車進(jìn)入路網(wǎng)，i=i+1，若i>I進(jìn)入步驟5，否則初始化K短路集Pi，候選集Xi，確定起點(diǎn)si，終點(diǎn)ti，松弛系數(shù)δ（K短路徑的長度與最短路徑的長度的比值），使用Dijkstra算法計(jì)算車輛i行駛的最短路徑pi1，pi1放入集合Pi中，計(jì)算pi1的長度fpi1，令F=δ×fpi1，令k=1，記錄pi1路段集合{［Sp，Sq］}和路段時(shí)間段集合{［aSpi，dSqi］}，其中aSpm=Gs0spc，dSqm=Gs0sqc。

步驟3? 若k>K，進(jìn)入步驟2，否則從pik中最靠近t的點(diǎn)開始到點(diǎn)si，點(diǎn)v擺動(dòng)到所有可能連接的點(diǎn)m上，vm滿足不在候選集Xi的條件。使用Dijkstra法搜索點(diǎn)m到ti的最短路，記為pm，把pksv、vm和pm組成的偏離徑路放入候選集Xi中，其中pksv表示pik上從si到v的子路徑。

步驟4? 若候選集Xi為空，進(jìn)入步驟2；若不為空，計(jì)算所有候選集中路徑fp升序排列，最小值路徑記為pik+1，只保留前K條路徑，若fpik+1>F進(jìn)入步驟5，否則把pik+1移入Pi中，k=k+1，進(jìn)入步驟3。

步驟5? 對場內(nèi)所有車輛所經(jīng)過的路段隊(duì)列和所經(jīng)過路段的占用時(shí)間隊(duì)列進(jìn)行兩兩比較，若存在兩輛車行駛方向相反、所經(jīng)過占用時(shí)間有沖突的路段，則提取出其中最先發(fā)生的路段Si，Sj，同時(shí)記錄兩輛車經(jīng)過上述路段時(shí)各自的占用時(shí)間aSim，dSjm，判定兩個(gè)車輛會在場內(nèi)行駛途中發(fā)生會車沖突，此時(shí)進(jìn)入步驟6比較兩個(gè)車輛的優(yōu)先級Pm，Pn；若不存在占用時(shí)間重合的路段Si，Sj，則車輛按照初始最短路徑時(shí)空信息行駛。

步驟6? 對比場上車輛優(yōu)先級屬性值，設(shè)優(yōu)先級高的車輛為m1，優(yōu)先級低的車輛為m2。按照所述車輛會車避讓準(zhǔn)則對兩個(gè)車輛進(jìn)行會車指導(dǎo)，首先遍歷車輛m2的K短路集合，判斷是否存在未被優(yōu)先級更高的車輛占用的次短路，計(jì)算該路徑上的總行程時(shí)間tk。若存在，則令車輛m2按此次短路徑行駛，更新車輛m2經(jīng)過路段{［Sp，Sq］}及時(shí)間段集合{［aspm2，dsqm2］}。若不存在，接著遍歷優(yōu)先級低的車從入口到?jīng)_突路段之間的路口，若存在會車點(diǎn)，則令車輛在會車點(diǎn)處等待，更新車輛m2經(jīng)過路段{［Sp，Sq］}及時(shí)間段集合{［aspm2，dsqm2］}；若不存在會車點(diǎn)，則令車輛m2在車輛入口等待，等待時(shí)間w=dsjm1－asjm2，并重新計(jì)算此時(shí)車輛行駛最短路總行程時(shí)間t，其中aspm2=aspm2+w，dsqm2=dsqm2+w，p，q≥i，j。更新避讓車輛路徑信息，并返回步驟5。

步驟7? 對比場內(nèi)所有車輛所經(jīng)過路段隊(duì)列和經(jīng)過路段的占用時(shí)間隊(duì)列無重合部分終止。

4? 算例分析

為了驗(yàn)證提出的模型和求解算法的有效性，本文以一個(gè)實(shí)際的大型風(fēng)電場的場內(nèi)路網(wǎng)為例，構(gòu)造案例進(jìn)行求解分析。算法使用Python編程實(shí)現(xiàn)，在2.20 GHz PC，16 GB RAM，Windows11，64位操作系統(tǒng)上運(yùn)行。

4.1? 小規(guī)模算例

所研究的風(fēng)電場場內(nèi)路網(wǎng)如圖3所示，我們將路網(wǎng)中的路口節(jié)點(diǎn)分為一般節(jié)點(diǎn)、在場區(qū)邊界的出入口以及卸貨點(diǎn)。在圖3中，F(xiàn)為會車點(diǎn)，M為場區(qū)邊界的出入口，D為卸貨點(diǎn)，S為一般路口節(jié)點(diǎn)。在這部分的小規(guī)模算例中，我們僅考慮3輛車，車輛的起終點(diǎn)、入場時(shí)間、優(yōu)先級等信息如表2所示。由表可見，車輛1和車輛3的優(yōu)先級低于車輛2。

采用所提出的算法對該算例進(jìn)行求解。首先得到各車輛從任務(wù)起點(diǎn)至終點(diǎn)的初始K（K=5）短路徑集合，然后計(jì)算得到車輛經(jīng)過路網(wǎng)各節(jié)點(diǎn)的時(shí)刻，對比計(jì)算第k短路上的車輛行駛時(shí)間和當(dāng)前最短路徑上的行駛時(shí)間，進(jìn)行多次迭代循環(huán)。當(dāng)k=1時(shí)，得到無沖突的車輛時(shí)空路徑，即取當(dāng)前所規(guī)劃的最短路徑。最終結(jié)果中，3輛車間的時(shí)空沖突都得到消除，沖突數(shù)量達(dá)到0。表3展示了最后各車輛的時(shí)空路徑結(jié)果，而圖4展示了各車輛會車避讓調(diào)整前后的時(shí)空路徑。從結(jié)果圖表中可以看出，車輛1為避讓會車優(yōu)先級更高的車輛2，在會車點(diǎn)F8處等待了1.7 min，待車輛2通過沖突路段后，車輛1繼續(xù)行駛；而對于車輛1和車輛3產(chǎn)生的會車沖突，由于車輛1和車輛3會車優(yōu)先級相同但車輛1作業(yè)時(shí)間更早，所以此時(shí)由車輛3在會車點(diǎn)F7處停車等待。最后，車輛2在場內(nèi)無須等待，車輛1和車輛3在場內(nèi)的等待時(shí)間與場內(nèi)總時(shí)間的比值分別為3.64%和8.01%。

4.2? 大規(guī)模算例

在相同的路網(wǎng)上，這部分構(gòu)建了不同車輛規(guī)模的大規(guī)模算例，并對結(jié)果進(jìn)行對比分析。共做了4組實(shí)驗(yàn)，車輛數(shù)分別為20、40、60、80，隨機(jī)生成車輛的起點(diǎn)、終點(diǎn)、優(yōu)先級和出發(fā)時(shí)間等信息。

使用本文提出的求解算法對模型進(jìn)行求解，算法運(yùn)行時(shí)間會隨車隊(duì)規(guī)模增加而增大，并且計(jì)算時(shí)間均在

1 s以內(nèi)。圖5展示了4組實(shí)驗(yàn)下的對比統(tǒng)計(jì)結(jié)果，包括無需等待車輛數(shù)、車輛平均等待時(shí)間和平均運(yùn)行時(shí)間。顯然，無需等待車輛數(shù)隨著車隊(duì)規(guī)模增大而增加，但是其占總車輛數(shù)的比例隨著車隊(duì)規(guī)模增大而減小。這是因?yàn)檐囮?duì)規(guī)模越大，車輛間的時(shí)空沖突越多，需要會車等待的車輛比例越高。圖5中紅色折線代表車輛平均等待時(shí)間，藍(lán)色折線代表車輛平均運(yùn)行時(shí)間。由圖6可以看出，當(dāng)車隊(duì)規(guī)模為20時(shí)，車輛平均等待時(shí)間和平均運(yùn)行時(shí)間最小；當(dāng)車隊(duì)規(guī)模≥40時(shí)，車輛平均等待時(shí)間和平均運(yùn)行時(shí)間基本保持不變。由此可見，車隊(duì)規(guī)模對車輛平均等待時(shí)間和平均運(yùn)行時(shí)間影響很小。

圖6展示了不同車隊(duì)規(guī)模下路網(wǎng)上所有車輛為進(jìn)入各路段的總等待時(shí)間分布情況，用于挖掘路網(wǎng)上的瓶頸路段，即路網(wǎng)上最容易發(fā)生車輛沖突和等待的路段。從圖6中可以看出，隨著車隊(duì)規(guī)模的增大，出現(xiàn)車輛沖突的路段數(shù)量隨之增加，而所有沖突路段上的總等待時(shí)間也不斷增長。該現(xiàn)象說明場內(nèi)車輛數(shù)量越多，路網(wǎng)上的擁堵程度越嚴(yán)重。而當(dāng)車隊(duì)規(guī)模達(dá)到40輛及以上時(shí)，F(xiàn)8-D6路段上的車輛總等待時(shí)間顯著高于其他路段，且在不同車隊(duì)規(guī)模增場景下均高于其他路段。因此在實(shí)際應(yīng)用中，當(dāng)場內(nèi)車輛較多時(shí)，可考慮拓寬F8-D6路段或采取其他相關(guān)措施，對該路段進(jìn)行擁堵疏解來減少場內(nèi)車輛間的沖突和等待時(shí)間。

此外，場內(nèi)車輛總等待時(shí)間占總行駛時(shí)間的百分比可有效反映車輛的運(yùn)輸效率，該值百分比越高，則說明車輛在行駛?cè)毯馁M(fèi)的等待時(shí)間越多，運(yùn)輸效率越低。如圖7所示，隨著車隊(duì)規(guī)模的增加，上述百分比指標(biāo)不斷上升，可知場內(nèi)車輛數(shù)量增加時(shí)會造成車輛運(yùn)輸效率降低。而當(dāng)車隊(duì)規(guī)模超過40輛時(shí)，該指標(biāo)上升趨勢明顯放緩，由此可見本文中提出的算法可在車輛較多時(shí)有效安排車輛合理避讓，盡可能減少等待時(shí)間在總行駛時(shí)間中的占比，具有較強(qiáng)的實(shí)際應(yīng)用性。

5? 結(jié)論

針對建設(shè)場內(nèi)運(yùn)輸車輛在道路限制的場景下面臨的對向會車沖突問題，基于時(shí)空網(wǎng)絡(luò)模型提出了一種求解算法，來規(guī)避車輛間的時(shí)空沖突。時(shí)空網(wǎng)絡(luò)模型以最小化車輛在場內(nèi)總時(shí)間為目標(biāo)，算法利用時(shí)空網(wǎng)絡(luò)的特性進(jìn)行模型刻畫，通過時(shí)空對比計(jì)算出沖突產(chǎn)生的位置和時(shí)間，并通過調(diào)節(jié)車輛在會車點(diǎn)的等待時(shí)間排除沖突。另外，以一個(gè)大型風(fēng)電場的實(shí)際路網(wǎng)為基礎(chǔ)構(gòu)造多個(gè)算例驗(yàn)證提出的模型和算法的有效性。通過對比分析可得：

（1）所提出的模型可兼顧場內(nèi)所有車輛的時(shí)空分布信息，為每輛車輛提供導(dǎo)航指令，在車輛行駛沖突產(chǎn)生之前進(jìn)行規(guī)避，有效消除車輛間的行駛沖突，具有較強(qiáng)實(shí)際應(yīng)用性；

（2）提出的算法效率很高，在算例中的不同車輛規(guī)模下都能在1 s內(nèi)得到結(jié)果，能滿足實(shí)時(shí)要求，可以很好地應(yīng)用至實(shí)際車輛導(dǎo)航中。

（3）提出的模型和算法，在不同車輛規(guī)模下均可在消除車輛間行駛沖突的同時(shí)，保證車輛在會車時(shí)不等待過長時(shí)間，最終的方案具有較高的車輛運(yùn)輸效率。

參考文獻(xiàn)：

［1］RAY J J. A web-based spatial decision support system optimizes routes for oversize/overweight vehicles in Delaware［J］. Decision Support Systems， 2007， 43（4）： 1171-1185. DOI： 10.1016/j.dss.2005.07.007.

［2］OSEGUEDA R， GARCIA-DIAZ A， ASHUR S， et al. GIS-based network routing procedures for overweight and oversized vehicles［J］. Journal of Transportation Engineering， 1999， 125（4）： 324-331. DOI： 10.1061/（asce）0733-947x（1999）125： 4（324）.

［3］申世杰. 大件產(chǎn)品公路運(yùn)輸安全管理系統(tǒng)研究及應(yīng)用［D］. 重慶： 重慶大學(xué)， 2008.

［4］吳麗麗. 重大件公路運(yùn)輸若干問題的研究［D］. 哈爾濱： 東北林業(yè)大學(xué)， 2007.

［5］鄭家祥， 殷奎生. 高土石壩施工過程計(jì)算機(jī)模擬［J］. 水電站設(shè)計(jì)， 1993， 9（2）： 70-75.

［6］劉寧. 高心墻堆石壩施工場內(nèi)交通仿真與實(shí)時(shí)控制研究［D］. 天津： 天津大學(xué)， 2013.

［7］周思， 肖宜， 申明亮， 等. 大型水利工程土石方調(diào)配道路系統(tǒng)建模研究［J］. 中國農(nóng)村水利水電， 2011（5）： 109-112.

［8］WANG Y， ZHANG S L， GUAN X Y， et al. Cooperation and profit allocation for two-echelon logistics pickup and delivery problems with state-space-time networks［J］. Applied Soft Computing， 2021， 109： 107528. DOI： 10.1016/j.asoc.2021.107528.

［9］YAN S Y， CHU J C， HUNG W C. A customer selection and vehicle scheduling model for moving companies［J］. Transportation Letters， 2020， 12（9）： 613-622. DOI： 10.1080/19427867.2019.1671061.

［10］WANG L F， SONG J， SHI L Y. Dynamic emergency logistics planning： models and heuristic algorithm［J］. Optimization Letters， 2015， 9（8）： 1533-1552. DOI： 10.1007/s11590-015-0853-z.

［11］高一鷺， 胡志華. 基于時(shí)空網(wǎng)絡(luò)的自動(dòng)化集裝箱碼頭自動(dòng)化導(dǎo)引車路徑規(guī)劃［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（7）： 2155-2163. DOI： 10.11772/j.issn.1001-9081.2019122117.

［12］吳正陽， 魯工圓， 馬駟. 多資源約束下車輛配送路徑優(yōu)化模型［J］. 交通運(yùn)輸工程與信息學(xué)報(bào)， 2018， 16（1）： 122-130. DOI： 10.3969/j.issn.1672-4747.2018.01.019.