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

DOI：10.3976/j.issn.1002-4026.20230047

收稿日期：2023-03-17

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

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

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

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

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

開(kāi)放科學(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

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

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

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

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

1? 問(wèn)題描述

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

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

2? 優(yōu)化模型

2.1? 符號(hào)定義

本文涉及的其他符號(hào)定義如表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)的屬性包括其對(duì)應(yīng)的拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)、其對(duì)應(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對(duì)應(yīng)的拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)，ρ2i為點(diǎn)i對(duì)應(yīng)的離散時(shí)間點(diǎn)。

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

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

行駛弧表示車(chē)輛在拓?fù)渚W(wǎng)絡(luò)中一條邊上的行駛活動(dòng)，即從邊的起始節(jié)點(diǎn)行駛至其終點(diǎn)節(jié)點(diǎn)。因此，行駛弧是基于拓?fù)渚W(wǎng)絡(luò)中的每條邊構(gòu)建的，行駛弧起終點(diǎn)對(duì)應(yīng)拓?fù)渚W(wǎng)絡(luò)中一條邊的起始、終點(diǎn)節(jié)點(diǎn)，且起終點(diǎn)對(duì)應(yīng)的離散時(shí)間點(diǎn)差值為邊的車(chē)輛行駛時(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ò)中邊對(duì)應(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)的場(chǎng)內(nèi)車(chē)輛路徑規(guī)劃模型，設(shè)置二元變量xkij（k∈K，（i，j）∈A），其值取1時(shí)表示車(chē)輛k經(jīng)過(guò)時(shí)空網(wǎng)絡(luò)中的?。╥，j），反之值為0。模型的目標(biāo)為所有車(chē)輛在場(chǎng)內(nèi)的總加權(quán)時(shí)間最小，包括等待時(shí)間和行駛時(shí)間。權(quán)重用車(chē)輛的優(yōu)先級(jí)來(lái)衡量，以此確保優(yōu)先級(jí)低的車(chē)在會(huì)車(chē)時(shí)進(jìn)行避讓等待，則目標(biāo)函數(shù)為

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

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

車(chē)輛會(huì)車(chē)避讓約束如式（11）所示。對(duì)于拓?fù)渚W(wǎng)絡(luò)中的一個(gè)沖突邊對(duì)l，l′來(lái)說(shuō)，式（11）表示當(dāng)車(chē)輛k′經(jīng)過(guò)邊l對(duì)應(yīng)的一條行駛?。╥′，j′）時(shí)，離散時(shí)間點(diǎn)ρ2i′前后Δtpass時(shí)間內(nèi)（即區(qū)間［ρ2i′－Δtpass，ρ2i′+Δtpass］）沒(méi)有任何其他車(chē)輛駛?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)的所有車(chē)輛分配一條時(shí)空路徑，每條時(shí)空路徑上不存在任何時(shí)空沖突，目標(biāo)為最小化場(chǎng)內(nèi)所有車(chē)輛的時(shí)間。為了快速求解上述模型，本文考慮根據(jù)各車(chē)輛給定的起終點(diǎn)，利用Yen算法（偏離路徑法）計(jì)算得到各車(chē)輛的K短路徑［13］，之后計(jì)算得到各車(chē)輛到達(dá)最短路徑上各節(jié)點(diǎn)和占用各路段的時(shí)間信息。若車(chē)輛間存在時(shí)空沖突，根據(jù)沖突車(chē)輛優(yōu)先級(jí)屬性，首先遍歷尋找優(yōu)先級(jí)低的車(chē)輛K段路徑集合中未被優(yōu)先級(jí)高的車(chē)輛占用的K短路，若存在該條路徑，則安排優(yōu)先級(jí)低的車(chē)輛更改當(dāng)前路徑，按照所搜索到的K短路行駛；若不存在該條路徑，則安排優(yōu)先級(jí)低的車(chē)輛在會(huì)車(chē)點(diǎn)等待直到優(yōu)先級(jí)高的車(chē)輛離開(kāi)沖突路段。特別地，當(dāng)兩個(gè)車(chē)優(yōu)先級(jí)相同時(shí)，根據(jù)先到先服務(wù)原則，優(yōu)先讓入場(chǎng)時(shí)間早的車(chē)輛進(jìn)入沖突路段。根據(jù)沖突的預(yù)計(jì)發(fā)生時(shí)間，解決當(dāng)前最早發(fā)生的沖突，直到場(chǎng)內(nèi)所有運(yùn)輸車(chē)輛都有無(wú)沖突的路徑。

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

算法的主要流程如下：

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

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

步驟3? 若k>K，進(jìn)入步驟2，否則從pik中最靠近t的點(diǎn)開(kāi)始到點(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? 對(duì)場(chǎng)內(nèi)所有車(chē)輛所經(jīng)過(guò)的路段隊(duì)列和所經(jīng)過(guò)路段的占用時(shí)間隊(duì)列進(jìn)行兩兩比較，若存在兩輛車(chē)行駛方向相反、所經(jīng)過(guò)占用時(shí)間有沖突的路段，則提取出其中最先發(fā)生的路段Si，Sj，同時(shí)記錄兩輛車(chē)經(jīng)過(guò)上述路段時(shí)各自的占用時(shí)間aSim，dSjm，判定兩個(gè)車(chē)輛會(huì)在場(chǎng)內(nèi)行駛途中發(fā)生會(huì)車(chē)沖突，此時(shí)進(jìn)入步驟6比較兩個(gè)車(chē)輛的優(yōu)先級(jí)Pm，Pn；若不存在占用時(shí)間重合的路段Si，Sj，則車(chē)輛按照初始最短路徑時(shí)空信息行駛。

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

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

4? 算例分析

為了驗(yàn)證提出的模型和求解算法的有效性，本文以一個(gè)實(shí)際的大型風(fēng)電場(chǎng)的場(chǎ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)電場(chǎng)場(chǎng)內(nèi)路網(wǎng)如圖3所示，我們將路網(wǎng)中的路口節(jié)點(diǎn)分為一般節(jié)點(diǎn)、在場(chǎng)區(qū)邊界的出入口以及卸貨點(diǎn)。在圖3中，F(xiàn)為會(huì)車(chē)點(diǎn)，M為場(chǎng)區(qū)邊界的出入口，D為卸貨點(diǎn)，S為一般路口節(jié)點(diǎn)。在這部分的小規(guī)模算例中，我們僅考慮3輛車(chē)，車(chē)輛的起終點(diǎn)、入場(chǎng)時(shí)間、優(yōu)先級(jí)等信息如表2所示。由表可見(jiàn)，車(chē)輛1和車(chē)輛3的優(yōu)先級(jí)低于車(chē)輛2。

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

4.2? 大規(guī)模算例

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

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

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

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

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

5? 結(jié)論

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

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

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

（3）提出的模型和算法，在不同車(chē)輛規(guī)模下均可在消除車(chē)輛間行駛沖突的同時(shí)，保證車(chē)輛在會(huì)車(chē)時(shí)不等待過(guò)長(zhǎng)時(shí)間，最終的方案具有較高的車(chē)輛運(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)輸若干問(wèn)題的研究［D］. 哈爾濱： 東北林業(yè)大學(xué)， 2007.

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

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

［7］周思， 肖宜， 申明亮， 等. 大型水利工程土石方調(diào)配道路系統(tǒng)建模研究［J］. 中國(guó)農(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)引車(chē)路徑規(guī)劃［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（7）： 2155-2163. DOI： 10.11772/j.issn.1001-9081.2019122117.

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