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

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

DOI：10.3976/j.issn.1002-4026.20230047

收稿日期：2023-03-17

作者簡介：李國儉（1977—），男，高級工程師，研究方向為能源電力技術(shù)。E-mail：lgjian77@126.com

*通信作者，沈磊，男，工程師，研究方向為新能源發(fā)電。E-mail ：2733797096@qq.com

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

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

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

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

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

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

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

2? 優(yōu)化模型

2.1? 符號定義

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

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

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

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

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

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

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

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

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

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

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

∑（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ò)中的一個沖突邊對l，l′來說，式（11）表示當(dāng)車輛k′經(jīng)過邊l對應(yīng)的一條行駛?。╥′，j′）時，離散時間點ρ2i′前后Δtpass時間內(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? 求解算法

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

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

算法的主要流程如下：

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

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

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

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

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

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

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

4? 算例分析

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

4.1? 小規(guī)模算例

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

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

4.2? 大規(guī)模算例

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

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

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

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

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

5? 結(jié)論

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

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

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

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

參考文獻(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)品公路運輸安全管理系統(tǒng)研究及應(yīng)用［D］. 重慶： 重慶大學(xué)， 2008.

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

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

［6］劉寧. 高心墻堆石壩施工場內(nèi)交通仿真與實時控制研究［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］高一鷺， 胡志華. 基于時空網(wǎng)絡(luò)的自動化集裝箱碼頭自動化導(dǎo)引車路徑規(guī)劃［J］. 計算機應(yīng)用， 2020， 40（7）： 2155-2163. DOI： 10.11772/j.issn.1001-9081.2019122117.

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