高速公路服務區液化天然氣站點混合補氣路徑優化問題

中圖分類號 U417 文獻標識碼 A 文章編號 2096-8949（2025）08-0044-04

0 引言

2020年9月我國提出“碳達峰”“碳中和”目標。在“雙碳”戰略下，各行業開展綠色發展的進程進一步被激發。液化天然氣近年來被大量開發并應用于汽車動力原料。高速公路服務區以加油站為主，LNG加氣站相對較少，隨著在服務區內加氣站建設站點的增多，如何低成本補氣成為供氣公司面臨的問題。

LNG車輛訪問加氣站屬于經典的車輛路徑問題[1]，國內外相關學者對該類問題展開了大量研究[2]。

由于高速公路服務區內加氣站的氣體儲備量較大，通常需要多個運輸車輛為其補充氣源，然而多個運輸車輛為單個高速公路服務區內的加氣站補充LNG時，極易出現LNG補充過度導致運輸車內剩余LNG，或補充不足導致加氣站內儲氣罐儲氣不足的問題。而現有文獻中關于這一問題的研究，多考慮單一車型為其服務[34]，較少考慮采用專車運輸與拼車運輸的混合運輸模式為加氣站補充LNG。

鑒于此，該文首先綜合考慮LNG專車與拼車兩種模式，提出服務區LNG站點混合補氣路徑優化問題。綜合考慮各個加氣站的差異化需求及運輸車輛的裝載要求，構建以運輸成本最小化為目標的數學模型。其次，在遺傳算法中引入“破壞”與“修復”策略，對所構建的模型進行求解。然后，在對所設計模型及求解車輛的基礎上，采用數值分析的方式對其性能進行驗證。最后，以實例對混合補氣模式及優化結果進行分析。

1模型建立

1.1問題描述

供氣公司通過車隊為服務區內加氣站提供供氣服務，不同站點受車流量影響，所剩庫存存在差異性，因此，不同加氣站點需補充的氣源存在差異性。當加氣站點所需補充氣源量大于運輸車額定裝載量時，采用專車運輸模式，當站點所需補充的氣源小于運輸車輛額定裝載量時，采用共享運輸模式為多個加氣站補氣，要求以最安全、最低運輸成本為各個加氣站完成補氣，所解決具體問題如圖1所示。

問題可描述為在有向圖 G = （ V ， A ） 中，尋找多條由氣源到加氣站的最短路問題。 為所有加氣站組成的集合，0和 n + 1 為氣源， 1 ， 2 ， 3 ， ？ s ， n 為加氣站， A 為由氣源與加氣站所組成的弧。車輛完成任務須返回氣源中心。使用符號以及含義如表1所示。

決策變量 為車輛 k 對加氣站 i 的開始服務時間， 為車輛 k 是否從加氣站 i 出發前往加氣站i，是為1否則為

1.2模型構建

為實現運輸車輛以最小運輸成本將LNG由氣源地運往加氣站，在滿足時間窗以及補氣約束條件下，以最小運輸成本作為優化目標函數，構建數學模型如下。

公式（1）為以運輸成本最小化的目標函數，公式（2）為每一個加氣站只能夠被分配到一條路徑中，公式（3） ～ （ 5 ） 為車輛在運輸路徑上的流量限制，公式（6）為運輸過程中的時間，公式（7）為時間連續性約束，式（8） ～ （9）為時間窗約束，公式（10）為限載約束。

2 求解策略

車輛在為加氣站補充LNG這一過程屬于典型的NP-hard問題，難以使用精確式算法為其求出最優解[5，特別是隨求解問題規模的增加，求解復雜度呈現指數上升。鑒于遺傳算法具有快速搜索全局的能力，該文采用遺傳算法對LNG站點混合補氣問題進行求解。

2.1 編碼與解碼

在運輸中有兩種車型，專車為單個加氣站提供服務，拼車為多個站點提供服務。在編碼過程中采用實數進行編碼，用0表示供氣公司，1，2，3，表示加氣站，采用由供氣公司與加氣站點組成的實數段進行染色體的編碼如圖2所示。

在圖2中，0為供氣公司，染色體1為車輛由供氣公司出發，先后經過加氣站1，2，3，4，5，6，并為六個加氣站提供服務，最后返回；染色體2為運輸車輛由供氣公司出發，先后經過加氣站6，5，4，3，2，1，并為加氣站提供服務，最后返回，解碼過程則為編碼的逆序。

2.2 適應度函數

適應度函數（FitnessFunction）是遺傳算法（GeneticAlgorithm，GA）中一個核心概念。用于評估個體的優劣程度。適應度函數的設計直接影響算法的性能和最終解的質量，該文采用適應度函數對解的質量進行評價，以篩選優質的運輸方案，設計的適應度函數如公式（11）所示。

f （ s ） = c （ s ） + α × q （ s ） + β × w （ s ）

式中， s —配送方案； f （ s ） ——車輛在執行任務過程中的總運輸成本； c （ s ） —車輛執行任務中的運輸成本；a ——違反車輛裝載量約束的懲罰因子； q （ s ） ——運輸過程中違反車輛裝載量， β —運輸過程中違反時間窗懲罰因子； w （ s ） —一運輸過程中違反時間窗約束量。該文將適應度函數設定為成本函數的倒數形式，即fitnes： ，以尋找最滿意解。

2.3種群初始化

初始種群的質量和多樣性直接影響算法的性能和收斂速度。該文采用隨機數發生器，組成初始種群，即先從所有加氣站中隨機選擇一個加氣站 i ， 其次，初始化車輛數目 k ，隨機生成遍歷加氣站的運輸序列 ，最后根據車輛裝載量對運輸路徑序列的可行性進行檢驗，以完成優化迭代過程中的種群的初始化。

2.4 交叉與變異

交叉又稱重組，是產生新個體的重要手段。交叉操作能夠保持種群的多樣性，并有可能結合不同個體的優秀基因，產生適應度更高的新個體。該文假設有兩個父代個體12345678與87654321。在交叉過程中隨機選擇兩個交叉位置 x 1 和 x 2 ，假設 x 1 = 3 ， x 2 = 6 ，則交叉片段為：12|3456|78與87|6543|21。然后根據交叉位置，對基因片段進行交叉生成新的染色體654312|345678，345687|6543|21，最后依據順序刪除重復基因，形成兩個新的子代個體：65431278與34568721。變異具體過程為交換兩個位置上邊的基因，假設隨機選擇兩個交叉位置 x 1 = 3 ， x 2 = 6 ，則交叉片段為12345678，87654321，變異之后的個體為12645378，87354621。

2.5 局部搜索操作

為提升算法效能，該文設計基于“破壞”與“修復”策略的局部搜索操作，使用破壞算子移除若干加氣站，使用修復算子將被移除的加氣站重新插回被破壞解中，破壞算子如公式（12）。

式中， 標準化值，取值范圍為[0，1]；

加氣站 i 與 j 是否在同一條路徑上的0，1變量。

3實例分析

某LNG加氣站點分布以及氣源分布如圖3所示。

在圖3中，矩形為高速公路服務區內加氣站，不同的加氣站每日消耗量不同，因此不同的加氣站對LNG的需求量存在差異性。五角星為某供氣公司所在位置，每日負責為加氣站補充LNG。運輸車輛額定裝載量為30t，由于LNG的特殊性，補充氣體時為夜間，因此加氣站時間窗為20：00—07：00。運輸車在為加氣站補氣時需要一定的服務時間，單位為min。供氣公司以及所服務的加氣站位置、需求數據如表2所示。

在為服務區內加氣站補充氣體過程中，考慮到不同加氣站LNG的需求量差異性，適配不同的策略為其提供配送服務。結果表明：需求量最大的加氣站共需要4輛運輸車為其提供補氣服務，其中3輛車為專車，1輛車為拼車。而需求量最小的加氣站共需要1輛車為其提供配送服務。若采用混合運輸補氣模式，相比專線運輸模式能夠顯著降低運輸成本。