張得志，喬馨，肖博文，王日東，毛成輝

(1. 中南大學(xué) 交通運輸工程學(xué)院，湖南 長沙410075；2. 清華大學(xué) 機械工程學(xué)院，北京100084)

近年來，電子商務(wù)的發(fā)展對我國消費增長、產(chǎn)業(yè)升級和經(jīng)濟發(fā)展起到了極大的推動作用[1]。然而，在城市物流配送過程中，大量二氧化碳的排放對環(huán)境造成了嚴重影響，國際能源署(IEA)數(shù)據(jù)表明，交通運輸業(yè)的碳排放量占能源消耗的23%[2]，其中道路運輸是碳排放的主要來源，根據(jù)相關(guān)部門統(tǒng)計數(shù)據(jù)，我國道路運輸碳排放量在交通運輸業(yè)中占比高達86.32%[3]，作為電子商務(wù)的重要支撐，其排放控制問題和對策成為國內(nèi)外研究的焦點；同時，B2B 模式下的客戶需求往往不確定，客戶滿意度成為提升企業(yè)價值的關(guān)鍵因素。因此，在低碳與需求隨機的條件下，考慮客戶滿意度、車隊規(guī)模與配送成本并進行集成優(yōu)化十分必要。目前，國內(nèi)外學(xué)者圍繞低碳車輛路徑問題(Vehicle Routing Problem，VRP)進行了大量研究工作，多為單目標優(yōu)化。KARA 等[4]以能耗最小的方式將綠色理念與車輛路徑問題結(jié)合，推動了這一領(lǐng)域的發(fā)展；FIGLIOZZI[5]以減少CO2為目標建立了帶時間窗約束的VRP 模型并以迭代算法進行優(yōu)化求解，將CO2排放的測算脫離了能耗；邱雅君等[6]通過線性加權(quán)將碳排放引入VRP，并使用遺傳算法進行求解；崔娥英等[7]測算了有碳稅和碳交易的配送中心和配送環(huán)節(jié)的碳排放；李進等[8]將車輛速度與碳排相結(jié)合，研究了相應(yīng)的碳稅激勵機制；張得志等[9]建立了基于CO2排放的多車型VRP 模型，考慮了市內(nèi)行駛速度的時變性；程興群等[10]同時考慮低碳政策與道路擁堵，設(shè)計了基于保優(yōu)策略和移民策略的遺傳算法。在多目標VRP 問題方面。陳希瓊等[11]建立同時考慮車輛容量和距離約束的VRPSPD 雙目標模型；ZHANG 等[12]同時考慮運輸成本和每條路徑間的平衡；李嫚嫚等[13]等以最大化客戶滿意度與最小化配送成本作為優(yōu)化目標,對帶時間窗的車輛路徑問題進行研究。郭森等[14]綜合考慮了配送中距離最短、時間最少和費用最省三個目標，但未考慮低碳因素。同時，上述研究都是基于確定性需求特征進行探索優(yōu)化，一定程度上忽略了B2B 環(huán)境下需求不確定性對物流配送優(yōu)化的影響，因而得到的解決方案魯棒性較差，現(xiàn)實中會增加物流企業(yè)的配送成本?；诖耍疚目紤]電子商務(wù)環(huán)境下，大型連鎖超市以B2B 為主的配送業(yè)務(wù)，考慮配送總成本、車隊規(guī)模以及客戶時間滿意度，構(gòu)建基于低碳與隨機需求的多目標車輛路徑模型，設(shè)計基于Pareto最優(yōu)解的多目標遺傳算法進行求解，并以步步高集團云通物流配送為例，進行實證分析。

1 問題分析與建模

本文提出基于低碳視角與隨機需求的多目標車輛路徑優(yōu)化模型，使用多輛同種車輛從配送中心配送至客戶點，客戶點需求存在不確定性。要求規(guī)劃合理的配送路線使得成本最小，同時考慮低碳經(jīng)濟的要求并盡可能地減少車輛使用數(shù)量。

1.1 模型假設(shè)

1)配送中心只有一個且已知；

2)客戶位置和配送中心位置已知；

3)不得超過配送車輛最大容量限制；

4) 客戶需求服從正態(tài)分布，其均值、方差已知；

5)車輛為同種車型，且容量已知；

6) 客戶接受服務(wù)的時間窗已知，可以違反但會產(chǎn)生相應(yīng)懲罰。

1.2 數(shù)學(xué)模型

符號表示：

V={0,1,2,…,n}：其中0 表示配送中心，1,2,…,n表示需要服務(wù)的客戶點

M={1,2,3,…,k}：服務(wù)車輛集合

m= |M|：使用車輛總數(shù)

Eij：路徑(i,j)上車輛的能量消耗量

δ：碳排放因子，KgCO2/L

cv：配送車輛的固定成本，元/次

cf：每單位燃料的價格，元/L

ce：單位CO2排放的納稅額，元/kg

cd：司機單位時間薪酬，元/h

Satisf ki：車輛k服務(wù)的客戶i的滿意度

q+：車輛的容量上限，kg

qi：客戶i的需求量，kg

Tk：車輛k的總耗時，h

a：允許的路由失敗次數(shù)

目標函數(shù)：

約束條件：

式(1)～(3)為目標函數(shù)。目標(1)表示配送的總成本最小，包括兩部分：車輛固定使用成本與變動成本，其中變動成本包括了燃料成本、碳排放納稅額和司機報酬；目標(2)表示使用的車隊規(guī)模最??；目標(3)表示客戶時間滿意度最大。(4)～(9)為約束條件，式(4)表示一個客戶有且僅由一輛車提供服務(wù)；式(5)表示兩點之間的運輸必須由一輛車完成；式(6)和(7)表示每個客戶點只能被服務(wù)一次；式(8)表示路徑允許的需求總量；式(9)為變量的非負約束。

1.3 車輛能源消耗量

基于BARTH 等[15]提出的重型車輛綜合排放測算模型，構(gòu)造運用距離dij和速度vij來測算路徑(i,j)上車輛的能量消耗函數(shù)。

其中，vij表示車輛在路徑(i,j)上的平均速度，m/s；ρ表 示空 氣密 度，kg/m2；mij為 車 輛 在路 徑(i,j)上的載重量；M為車輛自重；S為車頭與空氣的接觸面積；?為能源的空氣質(zhì)量比；K為引擎摩擦系數(shù)；E為引擎排量；N為引擎轉(zhuǎn)速；η柴油引擎的效率；ηcd為功率傳遞效率；Pzs為引擎運轉(zhuǎn)損失；Ckq為空氣摩擦阻力系數(shù)；dij為路徑(i,j)的行駛距離；τ表示能源從g/s到l/s的轉(zhuǎn)化因子；κ表示燃料的發(fā)熱量；將與路徑相關(guān)的多個阻力變量整合為ψij=a+gsinφ+gCgdcosφ，其中a為加速度；g為引力常數(shù)；φ為道路傾斜角；Cgd為滾動摩擦阻力系數(shù)。

1.4 客戶時間滿意度

考慮軟時間窗約束，即在客戶規(guī)定的時間窗內(nèi)到達為滿意，若到達時間早于客戶要求時間將等待，直到客戶要求的開始時間，設(shè)滿意度最大為1，最小為0。采用改進的降半哥西分布，設(shè)置客戶敏感度系數(shù)為0.000 05：

其中：Satif(ti)表示滿意度，ti為車輛到達客戶i的時間，Ui，Li為時間窗上下限。

2 求解算法

參考TAN等[16]的研究，設(shè)計基于Pareto最優(yōu)解的多目標遺傳算法進行求解。

算法求解過程如下：

Step 1：初始化算法，對各變量進行賦值，隨機產(chǎn)生初始種群；

Step 2：進行適應(yīng)度評估與Pareto 排序，選出較優(yōu)的個體組成新的種群；

Step 3：進行二元聯(lián)賽選擇，更新種群；

Step 4：染色體配對，進行路徑交叉；

Step 5：依概率進行染色體變異(包括分裂、整合、部分交換)；

Step 6：判斷染色體是否為可行解，若不是則將不滿足條件的染色體去除，重新從父代中選擇較優(yōu)的個體插入種群中；

Step 7：判斷是否滿足算法的終止條件，若滿足則輸出當前最優(yōu)解，否則返回Step 2。

算法描述如下：

1) 編碼：采用實數(shù)編碼法進行基因型編碼。每個基因位在實際中對應(yīng)于其客戶編號。例如一條路徑的基因位數(shù)為6(即有6個客戶，其客戶編號分別為1，3，4，6，7 和9)，其路由順序為：0→1→4→3→7→9→6→0，則其基因型為(01437960)。

2) 適應(yīng)度測算：使用目標函數(shù)作為適應(yīng)度測量指標。

3)Pareto 最優(yōu)排序：根據(jù)適應(yīng)度進行Pareto 最優(yōu)排序，最優(yōu)個體的排序等級為0，次優(yōu)排序等級為1，以此類推。

4) 選擇算子：使用二元錦標賽的方式進行選擇。

5)交叉算子：如圖1，設(shè)定交叉概率，生成0到1之間的隨機數(shù)，若小于交叉概率則隨機選擇群體中的2 條染色體中的2 條路徑進行雙點交叉，交叉之后對各條染色體刪除重復(fù)客戶點。為增大搜索空間，交叉后對染色體的路徑依概率進行隨機洗牌。

圖1 交叉算子示意圖Fig.1 Crossover operator diagram

圖2 交叉算子示意圖Fig.2 Mutation operator diagram

6) 變異算子：采取3 種變異方式進行突變[15]。①部分交換：在同一條染色體內(nèi)隨機選擇2條路徑交換部分基因位，產(chǎn)生新路徑；②合并短路徑：將染色體內(nèi)2條較短路徑進行合并，形成一條長路徑；③分裂長路徑：將染色體內(nèi)過長染色體進行隨機位拆分。每種突變方式依概率發(fā)生，變異后對每條路線依概率隨機洗牌。

3 算例分析

本文選取步步高連鎖超市的日配送數(shù)據(jù)進行實例分析。該連鎖超市由云通物流中心負責該區(qū)域內(nèi)超市零售配送任務(wù)。假設(shè)客戶點的需求為服從正態(tài)分布的隨機需求，均值和方差已知。各需求點都有軟時間窗要求，違反時間窗會使客戶的時間滿意度降低。客戶中心和配送中心位置分布如圖3所示。

圖3 客戶和配送中心地理位置分布圖Fig.3 Geographic distribution of customers and DCs

3.1 參數(shù)設(shè)置

車輛燃料為柴油，柴油價格為6.36元/L；車輛的自重3 t，最大容積為2 t；CO2排放的征稅額為50 元/t。本文引用DEMIR 等[17]使用的道路數(shù)據(jù)進行模擬研究，參數(shù)設(shè)置如表1所示。

表1 測算參數(shù)數(shù)據(jù)Table 1 Calculation parameter data

3.2 求解結(jié)果

每次迭代隨機正態(tài)生成10 組需求數(shù)據(jù)進行適應(yīng)度評估，以10 組評估的均值作為評價依據(jù)，分別進行10次模擬，每次種群數(shù)量為500，迭代次數(shù)上限為400。

結(jié)果表示，非支配解集和最終種群中車輛數(shù)都是9輛，這表明現(xiàn)有運營狀態(tài)下，配送中心車輛最優(yōu)數(shù)量為9 輛，對應(yīng)的最優(yōu)配送方案如表2 所示，圖4給出了最優(yōu)的配送路線圖，對應(yīng)的配送總成本為4 779.23 元，其中車輛固定成本1 800 元，能耗成本1 322.99 元，碳排成本28.39 元(CO2排放約為620 kg)，司機報酬為1 627.85 元，客戶時間滿意度為27.03。

圖4 配送線路圖Fig.4 Distribution route

表2 最優(yōu)配送方案Table 2 Optimal distribution scheme

3.3 算法性能分析

1) 算法收斂性分析

由圖5可知，種群平均配送總成本和非支配集平均配送總成本在迭代300 代之后均處于收斂狀態(tài)，收斂于4 800 元左右，但是收斂速度較慢；相比之下，車輛數(shù)收斂速度較快，在300代時，基本處于收斂狀態(tài)，均收斂于9輛；而客戶時間滿意度收斂性較差，尤其是非支配解集的平均客戶時間滿意度，雖然明顯表現(xiàn)出先下降后上升的趨勢，但波動較大。由于未對車輛數(shù)加以限制，在初始化過程中將優(yōu)先使用較多的車輛進行配送，因此客戶時間滿意度較高，但隨著使用車輛數(shù)的優(yōu)化，客戶時間滿意度逐步下降，在進一步優(yōu)化過程中逐漸上升，趨于收斂值28。

圖5 收斂性評價Fig.5 Convergence evaluation

根據(jù)種群和非支配解集內(nèi)各個目標函數(shù)的均值收斂情況，可知在迭代400次之后得到的解目標基本處于收斂狀態(tài)，可以認為已經(jīng)接近最優(yōu)解集，具有一定可靠性。

2) 方案適應(yīng)性分析

研究時使用的客戶需求具有不確定性，處于不斷波動之中。因此，所得到的方案能否在需求發(fā)生波動之后，依然保持良好的適應(yīng)性十分重要。為評價方案的適應(yīng)性，本研究在得到最優(yōu)方案集之后根據(jù)需求均值和方差隨機生成了4 組需求數(shù)據(jù)，對得到的方案進行模擬，得到現(xiàn)實運營過程中目標函數(shù)值，并與得到的目標函數(shù)期望值進行對比。

圖6顯示需求波動對平均配送成本存在一定影響，其中測試2 和4 相對較穩(wěn)定，其中值在300 附近，而測試1 和3 穩(wěn)定性較差，其差距中值超過300，約占總成本的10%?？梢钥闯觯骄蟮玫骄档闹兄堤幱?00附近，而且其數(shù)據(jù)波動范圍也較小，因此可認為其適應(yīng)性優(yōu)良，魯棒性較好。

圖6 適應(yīng)性評價Fig.6 Adaptability evaluation

3.4 交叉目標分析

客戶時間滿意度與其余目標存在沖突，表現(xiàn)在初期階段其他目標優(yōu)化會引起客戶時間滿意度降低。

為更加詳細地說明這種相關(guān)或沖突的程度，進行目標函數(shù)對比，使用增長的百分比作為依據(jù)，對比不同目標函數(shù)之間增長的趨勢關(guān)系。從表3可知：當配送成本減少37.7%時，客戶時間滿意度則降低了1.7%，前者變化率是后者的22 倍。這表明，現(xiàn)實中要想最大化客戶滿意度十分困難，需要投入大量成本；但在電商環(huán)境下，客戶滿意度幾乎是企業(yè)存亡的決定因素，因此企業(yè)往往將客戶滿意度作為優(yōu)先考慮的目標，而低碳則屬于次級目標。

表3 目標函數(shù)值前后對比分析表Table 3 Comparative analysis of objective function values

3.5 靈敏度分析

1) 碳稅額對結(jié)果的影響

為進一步探究碳稅額度變化對算法優(yōu)化結(jié)果的影響，本文對碳稅額參數(shù)的靈敏度進行分析。由表4可知，如果以征稅的方式控制碳排放量，碳稅額度并非越高效果越好。僅從政府管理的角度，當碳稅額定為70元/t，碳排放量最低。

表4 碳稅額對結(jié)果(收斂值)的影響Table 4 Influence of carbon tax on the result(convergence value)

選取成本與滿意度的比值以及成本與碳排放量的比值評價碳稅額度的效果。比值表示每提高一單位滿意度或者降低1 kg的CO2排放量所要付出的成本。如圖7 所示，從物流配送行業(yè)的角度分析，碳稅額定在40 元/t最優(yōu)。

圖7 碳稅額評價Fig.7 Carbon tax evaluation

2) 目標選擇對結(jié)果的影響

如圖8所示，若以碳排放最小為目標函數(shù)進行單目標優(yōu)化，在收斂時，其收斂值可以低至570 kg。相對于將其并入總配送成本中，可以減少8%以上的CO2排放，從低碳的角度更有利。但客戶時間滿意度下降到28.2 左右，相比之前減少約1.3?？芍寂艤p少與服務(wù)質(zhì)量提高之間是沖突的，這也是企業(yè)在節(jié)能減排工作壓力的來源之一。

圖8 碳排放作為單獨目標結(jié)果Fig.8 Result of carbon emission as an separate target

進一步分析極端情況，對每個目標分別優(yōu)化，探究多目標優(yōu)化對于每個目標的影響。

如表5 所示，通過①和②的結(jié)果對比可以看出，配送車輛總成本與車輛數(shù)之間沒有沖突，能夠達到同時優(yōu)化的目的，根據(jù)上文中的分析也可知，車輛的固定使用成本占總成本的比例很高，因此車輛數(shù)的優(yōu)化也是配送總成本優(yōu)化的關(guān)鍵；而通過①和③、②和③的對比發(fā)現(xiàn)，客戶時間滿意度與另外2個目標相沖突，將客戶時間滿意度提高至100%時，另外2 個目標的值都大大提高。對配送總成本進行單獨優(yōu)化時，其低碳優(yōu)化效果最好，甚至優(yōu)于同時優(yōu)化3個目標。在①情境下，配送總成本減少了2%左右，車輛數(shù)減少3%，但是客戶時間滿意度減少6.7%；在②情景下，車輛數(shù)減少2%，但成本上升30.7%，客戶時間滿意度下降27.2%；在③情景下，客戶時間滿意度提高至30增長2%，但引起另外2 個目標大幅度惡化，成本增長63.6%，車輛數(shù)增長63.3%。相比之下，②和③作為單目標優(yōu)化的目標函數(shù)是不明智的選擇。

表5 單目標優(yōu)化結(jié)果Table 5 Results of single objective optimization

從圖9 中可以看出，若降低配送成本的重要性，碳排量將顯著增加，同時在4個選擇中，其客戶時間滿意度是最大的，最終收斂于30，最終得到的總成本也是最高的，但對車輛數(shù)并沒有很大影響，這充分說明了成本與客戶滿意度之間的沖突；若降低客戶時間滿意度的重要性，其他3個量將同時達到最低，在優(yōu)化過程中要重視對于客戶時間滿意度目標的抉擇，其靈敏度較高，對優(yōu)化結(jié)果影響較大；而降低車輛數(shù)的重要性對于優(yōu)化過程并沒有產(chǎn)生明顯影響，說明這一目標函數(shù)在優(yōu)化過程中的靈敏度較低，在現(xiàn)實中可以忽略或置于配送總成本中考慮。

圖9 存在目標偏好對結(jié)果的影響Fig.9 Influence of objective preference on the result

4 結(jié)論

1) 設(shè)計的多目標車輛路徑遺傳算法能有效解決多目標隨機配送優(yōu)化問題，魯棒性較好。

2) 碳排減少與服務(wù)質(zhì)量提升之間存在一定矛盾。

3)從政府管理的角度分析，碳稅額定為70元/t最優(yōu)，從物流配送行業(yè)的角度分析，碳稅額定在40元/t最優(yōu)，政府管理部門在碳稅額度制定時可根據(jù)不同行業(yè)的特點劃分征收等級，從政府與企業(yè)兩個角度綜合考慮，制定合理的碳稅政策。

4) 配送企業(yè)的不同優(yōu)化目標偏好對配送優(yōu)化決策方案有重要影響，在優(yōu)化過程中要重視對于客戶時間滿意度目標的選擇，其靈敏度較高，對優(yōu)化結(jié)果影響顯著。

本研究可為政府制定合理的碳稅政策以及企業(yè)制定合理的配送決策提供理論依據(jù)。