高速公路服務(wù)區(qū)液化天然氣站點混合補氣路徑優(yōu)化問題

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

0 引言

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

LNG車輛訪問加氣站屬于經(jīng)典的車輛路徑問題[1]，國內(nèi)外相關(guān)學(xué)者對該類問題展開了大量研究[2]。

由于高速公路服務(wù)區(qū)內(nèi)加氣站的氣體儲備量較大，通常需要多個運輸車輛為其補充氣源，然而多個運輸車輛為單個高速公路服務(wù)區(qū)內(nèi)的加氣站補充LNG時，極易出現(xiàn)LNG補充過度導(dǎo)致運輸車內(nèi)剩余LNG，或補充不足導(dǎo)致加氣站內(nèi)儲氣罐儲氣不足的問題。而現(xiàn)有文獻中關(guān)于這一問題的研究，多考慮單一車型為其服務(wù)[34]，較少考慮采用專車運輸與拼車運輸?shù)幕旌线\輸模式為加氣站補充LNG。

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

1模型建立

1.1問題描述

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

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

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

1.2模型構(gòu)建

為實現(xiàn)運輸車輛以最小運輸成本將LNG由氣源地運往加氣站，在滿足時間窗以及補氣約束條件下，以最小運輸成本作為優(yōu)化目標(biāo)函數(shù)，構(gòu)建數(shù)學(xué)模型如下。

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

2 求解策略

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

2.1 編碼與解碼

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

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

2.2 適應(yīng)度函數(shù)

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

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

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

2.3種群初始化

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

2.4 交叉與變異

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

2.5 局部搜索操作

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

式中， 標(biāo)準(zhǔn)化值，取值范圍為[0，1]；

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

3實例分析

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

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

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