井工煤礦無軌膠輪車全局調(diào)度模型

陳湘源， 潘濤， 周彬

（1. 國能榆林能源有限責(zé)任公司，陜西 榆林 719000；2. 國能信息技術(shù)有限公司，北京 100011；3. 北京航空航天大學(xué) 車路一體智能交通全國重點(diǎn)實驗室，北京 100191）

0 引言

在井工煤礦生產(chǎn)中，輔助運(yùn)輸一般是指采用有軌列車、無軌膠輪車、單軌吊等運(yùn)輸人員、物資、設(shè)備等的運(yùn)輸方式。其中無軌膠輪車具有行駛路線靈活、運(yùn)輸能力大、爬坡能力強(qiáng)等優(yōu)勢，在新建大型礦井中得到了越來越多的應(yīng)用[1]，相應(yīng)地產(chǎn)生了無軌膠輪車調(diào)度管理系統(tǒng)[2]。無軌膠輪車運(yùn)輸具有需求多樣、臨時運(yùn)輸需求較多、末端路線結(jié)構(gòu)多變等特點(diǎn)，易受搬家倒面、突發(fā)事件等影響，且隨著礦井生產(chǎn)規(guī)模增大，無軌膠輪車數(shù)量急劇增加，傳統(tǒng)的人工調(diào)度管理方式效率低，無法滿足日漸增長的調(diào)度需求，造成車輛閑置、空載、里程浪費(fèi)等問題[3-5]。隨著5G、人工智能、高精度定位等新興技術(shù)在煤礦廣泛應(yīng)用[6-7]，通過基于全局優(yōu)化的人工智能算法來優(yōu)化車輛調(diào)度，提高無軌膠輪車運(yùn)輸效率和安全性，成為提高礦井生產(chǎn)率的關(guān)鍵[8-9]。

在地面車輛調(diào)度管理領(lǐng)域，劉愷[10]基于深度強(qiáng)化學(xué)習(xí)技術(shù)，提出了帶有自適應(yīng)獎勵機(jī)制和多目標(biāo)優(yōu)化的巡航車輛調(diào)度和車輛資源管理方法，從時間和空間維度平衡供需關(guān)系，優(yōu)化了車輛資源在時空維度的配置。楊華龍等[11]提出了基于匯集預(yù)測的車輛調(diào)度方法，綜合考慮物流配送成本和客戶滿意度，能有效預(yù)測隨機(jī)客戶需求，降低了調(diào)度成本。唐非[12]圍繞地勤服務(wù)公司的車輛配置和使用決策問題，研究了最少用車的特種車輛調(diào)度問題，建立了以最小化特種車輛數(shù)、無效服務(wù)時間比率和服務(wù)時間標(biāo)準(zhǔn)差為目標(biāo)的多目標(biāo)非線性數(shù)學(xué)模型，設(shè)計了多階段啟發(fā)式算法，通過實例仿真驗證了模型和算法的有效性。上述研究以城市道路上的乘用車調(diào)度為主，研究角度為人員與車輛或物料與車輛之間的匹配。這與煤礦無軌膠輪車既需運(yùn)輸人員又要運(yùn)輸物料的需求有較大差異[13]。此外，井下環(huán)境較地面更加復(fù)雜，無軌膠輪車行駛規(guī)則與地面車輛有較大區(qū)別。因此，地面成熟的車輛調(diào)度算法和框架無法直接應(yīng)用于井下環(huán)境[14]。

在煤礦輔助運(yùn)輸車輛調(diào)度研究方面，曹春玲等[15]將井下車輛調(diào)度策略抽象為一系列離散事件（包括預(yù)占用申請、區(qū)段聯(lián)鎖運(yùn)算、信號燈控制、意外事故處理等），針對3 種調(diào)度策略建立了巷道Petri 網(wǎng)模型并進(jìn)行分析；李夢雨[16]應(yīng)用AnyLogic 軟件建立了井下輔助運(yùn)輸車輛調(diào)度系統(tǒng)仿真模型，實現(xiàn)了調(diào)度系統(tǒng)基本功能，對應(yīng)用調(diào)度策略前后車輛運(yùn)行效率、成本等指標(biāo)進(jìn)行了對比分析?，F(xiàn)有研究大多采用面向固定任務(wù)使用離散事件優(yōu)化的方案進(jìn)行車輛調(diào)度優(yōu)化，通過將全局模型拆解為局部模型來簡化優(yōu)化問題，從而達(dá)到快速求解調(diào)度結(jié)果的目的[17]，缺乏對井工煤礦整體情況的分析，在實際應(yīng)用部署中無法達(dá)到理想效果[18-20]。因此，本文提出一種基于百度工業(yè)求解器的井工煤礦無軌膠輪車全局調(diào)度模型，并通過實驗驗證了該模型可解決傳統(tǒng)調(diào)度模型求解時間長、易陷入局部最優(yōu)解等問題，提升了無軌膠輪車調(diào)度管理效率，更適用于井下輔助運(yùn)輸場景下大規(guī)模復(fù)雜調(diào)度任務(wù)。

1 無軌膠輪車全局調(diào)度模型原理

無軌膠輪車全局調(diào)度模型由信息收集模塊、數(shù)據(jù)建模模塊和工業(yè)求解器模塊組成。信息收集模塊可采集井下地圖信息、車輛信息和工單信息（包括工單需求、工單時間、工單運(yùn)輸?shù)攸c(diǎn)、待運(yùn)輸?shù)娜藛T/物料信息等），可分析各信息間的相互關(guān)系并導(dǎo)入數(shù)據(jù)建模模塊。數(shù)據(jù)建模模塊對采集信息的相互關(guān)系進(jìn)行建模，通過數(shù)學(xué)方式將優(yōu)化條件、約束及目標(biāo)在模型對應(yīng)。工業(yè)求解器模塊根據(jù)優(yōu)化目標(biāo)對數(shù)學(xué)模型進(jìn)行優(yōu)化，得到最終的決策結(jié)果。

無軌膠輪車全局調(diào)度模型運(yùn)行流程如圖1 所示。對井下地圖信息和工單信息進(jìn)行數(shù)據(jù)校驗，確保沒有錯誤或相互沖突的信息。通過數(shù)據(jù)校驗后，相關(guān)信息輸入數(shù)據(jù)建模模塊建模，經(jīng)分析判斷模型是否存在可行解，若不存在可行解則輸出沖突信息供管理人員進(jìn)行判斷調(diào)整，存在可行解的模型輸入百度工業(yè)求解器進(jìn)行優(yōu)化分析，將得到的最優(yōu)解作為決策信息返回。

圖1 無軌膠輪車全局調(diào)度模型運(yùn)行流程Fig. 1 Operation process of global scheduling model for trackless rubber-tyred vehicle

2 無軌膠輪車全局調(diào)度模型設(shè)計

2.1 信息收集模塊

信息收集模塊通過信息采集器自動采集信息，包括地圖信息采集器、車輛信息采集器、工單信息采集器。

地圖信息采集器采集并格式化存儲煤礦井下四維基礎(chǔ)數(shù)據(jù)，即三維空間和時間相關(guān)數(shù)據(jù)，具體包括巷道、點(diǎn)狀與線狀對象的位置關(guān)系、屬性信息及其四維時空變化過程信息。地圖信息采集器功能見表1。

表1 地圖信息采集器功能Table 1 Function of map information collector

車輛信息采集器用來收集無軌膠輪車相關(guān)信息，包括車型、車輛尺寸、車輛載人量、車輛載貨量、車輛狀態(tài)、剩余油（電）量等。

工單信息采集器用來采集無軌膠輪車派車工單的相關(guān)要求及信息，主要包括任務(wù)開始/結(jié)束時間、任務(wù)開始/結(jié)束地點(diǎn)、運(yùn)輸物料信息、運(yùn)輸人員信息、特殊要求等。

2.2 數(shù)據(jù)建模模塊

數(shù)據(jù)建模模塊的輸入數(shù)據(jù)主要是錄入的工單信息和需要調(diào)度的車輛信息，包括調(diào)度任務(wù)的總行駛里程、工單任務(wù)的最早開始或最晚結(jié)束時間、工單任務(wù)的載人或載貨信息、可調(diào)度的車輛數(shù)、車輛可用或檢修狀態(tài)、車輛可載人或載貨量、車輛速度、車輛油耗及電耗、可駕駛資質(zhì)信息等。

在井下無軌膠輪車調(diào)度過程中，通常存在可用車輛資源規(guī)模大、待運(yùn)輸人員或物料數(shù)量多等情況，此時工業(yè)求解器的求解空間呈指數(shù)級增大，任務(wù)目標(biāo)結(jié)果求解時間增加，影響煤礦井下資源管理的穩(wěn)定性。對此，提出了基于分批求解、迭代優(yōu)化的無軌膠輪車全局調(diào)度算法，偽代碼如下（以運(yùn)輸物料為例）。

第1-4 行為算法初始化流程，用于讀取數(shù)據(jù)建模模塊的輸入數(shù)據(jù)、定義關(guān)鍵的中間參數(shù)變量、設(shè)置分批求解超參數(shù)；第6 行開始為針對大量輸入的待運(yùn)輸物料分批求解，即從全部待運(yùn)輸物料W中取出1 個批次wbs；第8 行開始為針對大規(guī)模輸入的可用車輛資源分批求解，即從全部可用車輛資源U中取出1 個批次ubs；第10 行為調(diào)用百度工業(yè)求解器對當(dāng)前批次的待運(yùn)輸物料和可用車輛資源進(jìn)行優(yōu)化求解；第11-13 行為在百度工業(yè)求解器求解出車輛調(diào)度結(jié)果后，將本輪求解結(jié)果保存在中間參數(shù)變量R中，并從全部待運(yùn)輸物料W和全部可用車輛資源U中刪除當(dāng)前已分配的任務(wù)工單和車輛資源，并進(jìn)入下一輪的分批求解、迭代優(yōu)化流程；第16 行為完成全部的分批求解循環(huán)后，返回最終車輛調(diào)度結(jié)果。

提出的無軌膠輪車全局調(diào)度算法可減小工業(yè)求解器的求解空間，提高求解效率，優(yōu)化求解結(jié)果。該算法中B(wbs,ubs)為基于百度工業(yè)求解器的調(diào)度優(yōu)化模型，建模方案設(shè)計如下。

1） 輸入數(shù)據(jù)設(shè)定。設(shè)可調(diào)用的車輛資源集合為Ncar；待運(yùn)輸人員或物料的任務(wù)工單集合為Ntask；可分配車輛為i，i∈Ncar；待分配任務(wù)工單為j，j∈Ntask；車輛i行駛速度為V(i)，可用時間段為(T1(i)，T2(i))，當(dāng)日初始油（電）量為I(i)，單位里程耗油（電）量為F(i)；車輛i與任務(wù)工單j的資質(zhì)匹配關(guān)系（包括載客量、可載物料體積、可載物料質(zhì)量等）為C(i,j)，若車輛i與任務(wù)工單j資質(zhì)匹配，則C(i,j)=1，反之C(i,j)=0；任務(wù)工單j的總行駛里程為D(j)，最早開始時間或最晚結(jié)束時間為T(j)；2 個任務(wù)工單j和j′之間的行駛距離為D(j,j′)，j′∈Ntask。

2） 決策變量設(shè)計。設(shè)車輛i是否接受任務(wù)工單j為X(i.j)，X(i.j)為1 表示接受工單，為0 表示不接受工單；車輛i接受任務(wù)工單j的時間為Y(i,j)，其為整數(shù)變量；車輛i在接受任務(wù)工單j后是否接受任務(wù)工單j′以合單運(yùn)輸為Z(i,j,j′)，Z(i,j,j′)為1 表示接受工單，為0 表示不接受工單。

3） 相關(guān)約束條件設(shè)計。

約束1：任務(wù)工單j僅被1 輛車接受，即

約束2：車輛接受的不同工單時間不沖突，即

約束3：車輛工作時間必須為可用時段，即

約束4：車輛耗油（電）量不大于每日初始油（電）量，即

約束5：車輛與工單資質(zhì)匹配，即

約束6：變量間關(guān)系為

式中M為工單執(zhí)行順序。

4） 優(yōu)化目標(biāo)設(shè)計。

最大化訂單完成數(shù)量，即

最小化任務(wù)等待時間，即

最小化總耗油（電）量，即

2.3 工業(yè)求解器模塊

綜合井下無軌膠輪車運(yùn)輸系統(tǒng)調(diào)度問題的求解精度、效率等因素，采用百度工業(yè)求解器對無軌膠輪車全局調(diào)度模型進(jìn)行優(yōu)化。百度工業(yè)求解器具有多種基礎(chǔ)優(yōu)化算法模塊來開發(fā)調(diào)度優(yōu)化算法。本文設(shè)計了基于強(qiáng)化學(xué)習(xí)策略調(diào)整的啟發(fā)式算法。該算法采用強(qiáng)化學(xué)習(xí)生成動作策略加速求解器收斂速度，且基于云原生的并行框架，充分利用GPU+CPU 的異構(gòu)算力，可解決超大規(guī)模復(fù)雜問題。百度工業(yè)求解器優(yōu)化算法流程如圖2 所示。

圖2 百度工業(yè)求解器優(yōu)化算法流程Fig. 2 Optimization algorithm process of Baidu industrial solver

2.4 無軌膠輪車全局調(diào)度過程

1） 業(yè)務(wù)系統(tǒng)或移動端應(yīng)用發(fā)來用車請求（含用車時間、物料申請、用車地點(diǎn)等）。

2） 對來自業(yè)務(wù)系統(tǒng)的車輛、人員、物料等基礎(chǔ)信息和訂單信息進(jìn)行校驗，重點(diǎn)判別有無字段缺失及字符無效等情況。

3） 若校驗通過，百度工業(yè)求解器對無軌膠輪車全局調(diào)度模型進(jìn)行預(yù)處理和計算，無可行解時轉(zhuǎn)步驟4），有可行解時轉(zhuǎn)步驟5）。

4） 報警并輸出模型約束沖突信息，用戶根據(jù)自定義的約束優(yōu)先級進(jìn)行選擇和調(diào)整，通過數(shù)據(jù)建模模塊生成新的模型后返回步驟3）。

5） 采用百度工業(yè)求解器進(jìn)行問題求解，可引入強(qiáng)化學(xué)習(xí)策略網(wǎng)絡(luò)來加速求解過程：在每個分支節(jié)點(diǎn)由強(qiáng)化學(xué)習(xí)策略網(wǎng)絡(luò)輸出動作后，由百度工業(yè)求解器基于動作調(diào)整啟發(fā)式算法進(jìn)行優(yōu)化求解，計算后更新問題的上界，通過判斷更新的上界是否等于下界來判斷是否求解完成。若未完成求解，由百度工業(yè)求解器的分支模塊生成新的問題，進(jìn)入下一輪迭代，直至求解出最優(yōu)解或達(dá)到預(yù)設(shè)的求解時間。

6） 將得到的最優(yōu)調(diào)度結(jié)果反饋至業(yè)務(wù)系統(tǒng)，形成有效的運(yùn)輸工單。

3 實驗與結(jié)果分析

設(shè)置不同規(guī)模的仿真優(yōu)化問題來驗證基于百度工業(yè)求解器的井工煤礦無軌膠輪車全局調(diào)度模型性能。收集某井工煤礦無軌膠輪車2 個月的調(diào)度運(yùn)行計劃，平均每個調(diào)度工單需完成1～6 種物料的運(yùn)輸，整個調(diào)度車隊包括106 輛不同型號的無軌膠輪車。

根據(jù)煤礦井下實際地圖信息，采用Python 3.8.8 搭建仿真平臺，對物料運(yùn)輸工單進(jìn)行運(yùn)輸任務(wù)優(yōu)化模擬。仿真平臺CPU 為Intel（R） Xeon（R） CPU E5-2680 v4 @ 2.40 GHz。采用基于百度工業(yè)求解器的全局調(diào)度模型與人工調(diào)度、基于主流商業(yè)求解器Gurobi 的局部調(diào)度模型[21]進(jìn)行調(diào)度優(yōu)化。2 種算法的批尺度均設(shè)為25。

3.1 不同規(guī)模調(diào)度問題優(yōu)化結(jié)果對比

將采集的工單數(shù)據(jù)進(jìn)行分類編組，根據(jù)每個工單所包含運(yùn)輸物料的種類、數(shù)量，將運(yùn)輸工單任務(wù)分為5 組。第1 組：14 個工單，16 個待運(yùn)輸物料，56 輛可調(diào)度車輛，平均每個工單運(yùn)輸1.1 個物料。第2 組：14 個工單，25 個待運(yùn)輸物料，56 輛可調(diào)度車輛，平均每個工單運(yùn)輸1.8 個物料。第3 組：14 個工單，25 個待運(yùn)輸物料，106 輛可調(diào)度車輛，平均每個工單運(yùn)輸1.8 個物料。第4 組：46 個工單，198 個待運(yùn)輸物料，106 輛可調(diào)度車輛，平均每個工單運(yùn)輸4.3 個物料。第5 組：60 個工單，284 個待運(yùn)輸物料，106 輛可調(diào)度車輛，平均每個工單運(yùn)輸4.7 個物料。

第1 組和第2 組調(diào)度問題較簡單，求解結(jié)果見表2（部分工單由于缺少相應(yīng)車輛而無法完成）。可看出對于簡單調(diào)度問題，人工調(diào)度與基于求解器的調(diào)度模型差距不大，但基于求解器的調(diào)度模型可顯著減少完成工單的車輛，提高車輛使用率，降低車輛空駛率；基于百度工業(yè)求解器的全局調(diào)度模型與基于Gurobi 求解器的局部調(diào)度模型性能相當(dāng)。

表2 第1 組和第2 組無軌膠輪車調(diào)度問題的求解結(jié)果Table 2 Calculated results for group 1 and group 2 scheduling problems of trackless rubber-tyred vehicle

第3—5 組調(diào)度問題較復(fù)雜，每個工單需要運(yùn)輸?shù)奈锪细?，且可使用的車輛數(shù)量大幅增加，求解結(jié)果見表3?？煽闯霾捎萌斯ふ{(diào)度方法時，一般1 輛車運(yùn)輸1 種物料，車輛空駛率較高，資源浪費(fèi)嚴(yán)重，且無法滿足大量物料運(yùn)輸需求，特別是對于第4 組和第5 組調(diào)度問題，人工調(diào)度方法僅滿足約80%的物料運(yùn)輸需求，而采用基于求解器的調(diào)度模型可滿足95%以上的物料運(yùn)輸需求，且極大降低了使用車次，提高了車輛運(yùn)轉(zhuǎn)效率。另外，基于百度工業(yè)求解器的全局調(diào)度模型表現(xiàn)最穩(wěn)定，針對最復(fù)雜的第5 組調(diào)度問題，該模型在完成工單個數(shù)和運(yùn)輸物料個數(shù)2 項指標(biāo)上均優(yōu)于基于Gurobi 求解器的局部調(diào)度模型，更適用于復(fù)雜的車輛調(diào)度優(yōu)化問題。

表3 第3—5 組無軌膠輪車調(diào)度問題的求解結(jié)果Table 3 Calculated results for group 3, group 4 and group 5 scheduling problems of trackless rubber-tyred vehicle

3.2 優(yōu)化速度對比

人工調(diào)度方法一般通過1 個調(diào)度指令派出1 個車次，從接到運(yùn)輸需求到查詢排班再到通知駕駛員耗時3～5 min，當(dāng)運(yùn)輸需求較大時，該方式無法及時響應(yīng)?；诎俣裙I(yè)求解器的全局調(diào)度模型與基于Gurobi 求解器的局部調(diào)度模型求解時間見表4?？煽闯霎?dāng)調(diào)度問題規(guī)模較小時，2 種模型的求解速度接近；當(dāng)調(diào)度問題規(guī)模增大時，基于Gurobi 求解器的局部調(diào)度模型求解時間大幅增加，表明求解結(jié)果易陷入局部最優(yōu)，導(dǎo)致時間浪費(fèi)。因此，在實際無軌膠輪車調(diào)度管理應(yīng)用中，采用基于百度工業(yè)求解器的全局調(diào)度模型求解大規(guī)模車輛調(diào)度問題更合適。

表4 2 種無軌膠輪車調(diào)度模型的求解時間Table 4 Calculated time of two scheduling models for trackless rubber-tyred vehicle

3.3 批尺度選擇

超參數(shù)批尺度對基于百度工業(yè)求解器的井工煤礦無軌膠輪車全局調(diào)度模型求解結(jié)果與求解時間影響較大。批尺度主要影響單次調(diào)度優(yōu)化計算涉及的優(yōu)化參數(shù)規(guī)模，批尺度過小會使優(yōu)化參數(shù)無法表示全局調(diào)度問題，過大會增大調(diào)度問題的計算規(guī)模，增加求解時間。因此，批尺度需根據(jù)待求解問題的規(guī)模進(jìn)行相應(yīng)調(diào)整。

為了選擇合適的全局調(diào)度模型超參數(shù)，設(shè)置不同的批尺度，針對第4 組和第5 組工單配置進(jìn)行調(diào)度優(yōu)化，結(jié)果見表5。可看出當(dāng)批尺度設(shè)置為15 時，雖然調(diào)度問題的求解時間更短，但由于單次優(yōu)化的任務(wù)過少，無法全局表達(dá)待優(yōu)化問題，所以優(yōu)化性能有所降低。當(dāng)批尺度增大到40 時，雖然優(yōu)化性能稍有提升，但求解時間大幅增加。針對目前井工煤礦無軌膠輪車調(diào)度問題的現(xiàn)有規(guī)模，選擇批尺度為25 可較好地平衡調(diào)度優(yōu)化性能與求解時間，能在較短的時間內(nèi)得到較好的優(yōu)化結(jié)果。

表5 不同批尺度下的無軌膠輪車調(diào)度優(yōu)化結(jié)果Table 5 Scheduling optimization results of trackless rubber-tyred vehicle under different batch-size

4 結(jié)論

1） 采用百度工業(yè)求解器對井工煤礦無軌膠輪車調(diào)度任務(wù)進(jìn)行優(yōu)化可顯著提升車輛使用效率，減少車輛使用數(shù)量，降低煤礦輔助運(yùn)輸系統(tǒng)運(yùn)行成本。

2） 采用百度工業(yè)求解器從無軌膠輪車運(yùn)輸整體情況進(jìn)行優(yōu)化能更好地應(yīng)對井工煤礦大規(guī)模復(fù)雜輔助運(yùn)輸系統(tǒng)調(diào)度任務(wù)，較傳統(tǒng)車輛調(diào)度方法表現(xiàn)更加優(yōu)異。

3） 下一步將從煤礦井下實際應(yīng)用場景出發(fā)，進(jìn)一步探索智能優(yōu)化算法在煤礦輔助運(yùn)輸系統(tǒng)調(diào)度管理中的應(yīng)用。