多路徑選擇變速雙目標物流配送路徑規劃

孔 珊，仲昭林，張紀會

(青島大學 a.復雜性科學研究所；b.山東省工業控制技術重點實驗室，山東 青島 266071)

0 引言

車輛路徑問題(VRP)是物流領域的熱門課題。自Dantzig和Ramser[1]首次提出以來，一直備受關注。根據實際環境的不同，產生了多種變型問題，如綠色車輛路徑問題、帶有時間窗的車輛路徑問題、多車型車輛路徑問題、動態車輛路徑問題、半開放式車輛路徑問題、變速車輛路徑問題等。多數模型都假設兩點之間只有一條路徑，且車輛勻速行駛，然而在實際路網中，任意兩點之間可能存在多條道路，且同一路段上車輛在不同時間段內的行駛速度會有較大差異(比如城市交通高峰期和非高峰期情況)。另一方面，隨著社會的發展，物流服務企業面臨的競爭不斷加劇，以時間窗刻畫服務水平的傳統方式具有一定局限性，需要根據客戶的特點將客戶分為不同類別(即考慮客戶優先級)來提供不同服務。因此，研究路網中任意兩點之間存在多條路徑的帶時間窗和能力約束的變速車輛路徑問題具有重要意義。

對于變速車輛路徑問題，Malandraki和Daskin[2]于1992年提出了用分段函數刻畫旅行時間的混合整數線性規劃模型。周鮮成等[3]研究時間依賴型綠色車輛路徑問題時考慮了車輛出發時刻對行駛速度和行駛時間的影響，并采用改進蟻群算法求解。Poonthalir和Nadarajan[4]研究了高效綠色車輛路徑問題，討論了行駛速度對路線成本和燃料消耗的影響。Fan等[5]研究了時變多車場帶時間窗綠色車輛路徑問題，利用多個三角函數關系表示不斷變化的車速，使其更加適合于動態環境。Gmira等[6]考慮路網中每個路段旅行時間的變化，采用禁忌搜索算法求解帶有時間窗的車輛路徑問題。

對于帶有路徑選擇的車輛路徑問題，Behnke和Kirschstein[7]的研究發現當兩點之間存在多條路徑時，通過合理的路徑選擇可以實現節能減排。Wang等[8]以節能和出行距離最小為目標建立多路徑電動汽車物流線路規劃模型。李順勇等[9]考慮了城市交通擁堵造成的環境污染問題，研究表明優化路徑選擇能夠明顯降低配送車輛的油耗。程興群等[10]對運輸時間和單位運費率的概率分布未知情形下的多路徑選擇問題進行研究，建立魯棒優化模型并設計了相應的算法。Sun等[11]綜合多種因素，比較車輛路徑選擇對車輛的運行時間和乘客的出行時間的影響。Croce等[12]研究了道路交通中影響車輛路徑選擇的行為，結果表明行駛距離、行駛時間以及行駛成本(如能耗)等因素都會影響車輛路徑選擇。

在顧客滿意度度量方面，余建軍等[13]考慮生鮮外賣配送的送達時間對顧客滿意度的影響，以配送成本最小和顧客滿意度最大為目標，用改進的遺傳算法求解。Barkaoui等[14]使用改進的混合遺傳算法對動態環境下多次訪問同一客戶的DVRPTW問題的客戶滿意度進行詳細研究，給出了新穎的滿意度評價函數，通過多次服務客戶的方式提高滿意度。Rajak等[15]針對單一倉庫不足以滿足顧客需求導致顧客滿意度下降的問題，提出了基于客戶滿意度的多倉庫車輛路徑問題，并采用兩階段蟻群優化算法求解。

綜上可以發現：目前多數研究都是利用車輛到達顧客時刻與時間窗的關系來刻畫顧客滿意度[16-18]，這種方式不能很好區分顧客的差異性；假設車輛行駛速度恒定不符合實際情況；假設任意兩個客戶點之間存在唯一路徑也與實際情況不吻合。針對這3個問題，做了3點改進：1)評價顧客滿意度時，除了以時間窗作為評價依據外，還考慮了顧客優先級因素；2)任意兩點之間存在多條可選擇路徑；3)在同一道路上，車輛行駛速度與通行時間有關。考慮以上速度變化和多路徑選擇問題，以同時滿足顧客滿意度最大和總配送成本最小為目標建立模型，對蟻群算法進行了有針對性的改進，最后通過算例分析驗證了該模型的合理性和算法的有效性。

1 建立模型

1.1 問題描述

某配送中心為客戶提供配送服務，配送車輛服務能力有限，路網上任意兩點之間存在多條路況不同的路徑，且同一路徑上車輛的行駛速度隨通行時刻的不同而變化。配送車輛從配送中心出發，在規定時間窗內對客戶進行服務，完成對最后一個客戶的服務后返回配送中心。每個客戶都有設定的服務時間窗和需求量，且客戶具備不同優先級，目標是設計配送路線，用最少的車輛在規定時間內完成所有配送任務，實現最小化配送成本和最大化客戶滿意度的目標。

1.2 顧客滿意度

假設車輛h到達顧客i的時間為Tih，顧客i希望的服務時間窗為[ETi,LTi]。從時間窗角度，顧客i的滿意度函數可表示為

(1)

以時間窗衡量的全部顧客的平均滿意度為

(2)

其中，xih為0—1變量，表示車輛h是否服務顧客i；|I|為需要服務的顧客數量；I為所有顧客集合。

從優先級角度出發，顧客i的滿意度可以用分段函數式(3)表示。

(3)

以優先級衡量的所有顧客的加權平均滿意度描述為

(4)

其中，priori為顧客i的優先級，Prior∈{1,2,3,…,r}。利用權值因子判斷法，得到以時間窗刻畫的顧客滿意度和以優先級刻畫的顧客滿意度所占權重，滿意度可以表示為加權和形式：

f=ω1afTW+ω2fp

(5)

1.3 時變速度與路徑選擇

一般來說，車輛的行駛速度是時變的。為了簡化計算，將通行時間段進行合理分割，在每個時間段內假定車輛勻速行駛。假設根據實際情況，將通行時段分成m段，將道路分成n種類型，如表1所示。

表1 道路類型、通行時段與速度的關系

對于選定客戶點j，從客戶點i出發有r條路徑可到達，對每條路徑上的行駛時間分別進行計算。假設車輛h在時間區間為[Ta-1,Ta]的時間段a中的時刻Tih從客戶點i出發，經過道路類型為b的路徑到達客戶j，則通過分段計算車輛從客戶點i出發到達下一個客戶點j的時刻。車輛h從客戶點i到達客戶點j的時刻可以表示為：車輛h到達點i的時刻加上需要在點i停留的服務時間以及經過路段所需時間，即Tjh=Tih+Ti+tijh。比較通過不同路徑到達客戶點j的時刻，為車輛從客戶點i到客戶點j選擇合適的路徑。

1.4 模型建立

此模型有兩個目標函數：

Maxf=ω1afTW+ω2fp

(6)

MinQ=C1+C2+C3+C4

(7)

式(6)表示最大化顧客滿意度，式(7)表示最小化成本。由于f的值在0～1之間，為了整合目標函數，公式(6)可以轉化為

(2) 當任一汽機遮斷時,為保證主蒸汽母管不超壓、不超溫,同時熱網供汽不中斷,可將主蒸汽母管至熱管網減溫減壓電動調門超馳至一定開度,再投入自動控制來兼顧主汽和供汽穩定,調門超馳開度由汽機遮斷前的負荷來確定。汽機遮斷快速減負荷控制流程如圖1所示。

Min (1-f)

(8)

式(7)由兩部分組成，分別為：車輛的固定成本和可變成本。車輛的固定成本用式(9)來表示，可變成本隨著汽車行駛里程數、實際行駛時間以及為客戶點服務的等待時間的變化而變化，可分別表示為式(10)～(12)。

C1=pq

(9)

C2=q1s

(10)

(11)

(12)

其中，p為使用車輛數，q為每輛車的固定費用，q1，q2，q3分別為單位路程(時間)內產生的車輛可變成本，xih為判斷車輛是否為顧客提供配送服務的0-1變量?？偮烦蘳可表示為

(13)

為消除滿意度和成本的數量級差距帶來的影響，公式(14)對兩者取對數，再用加權方式將多目標優化問題轉化為單目標優化問題。對應的加權系數分別為δ和1-δ，其中δ∈(0,1)。

MinδlgQ+(1-δ)|lg(1-f)|

(14)

s.t.

(15)

(16)

Qh≤Ch,?h∈H

(17)

(18)

(19)

(20)

(21)

(22)

(23)

其中，式(14)表示綜合最小成本和最大總體滿意度的目標函數；式(15)表示所有車輛的容量需要滿足配送總量；式(16)表示車輛h的實際載重；式(17)表示車輛的實際載重不能超過車輛的最大容量；式(18)表示同一個需求點只能被服務一次；式(19)表示配送過程中每輛車只能使用一次；式(20)表示每個需求點只能被一輛車服務；式(21)表示每輛車至少要為一個需求點服務，這里H′表示配送過程中使用車輛的集合；式(22)和(23)為相應的0、1決策變量。

2 算法設計

蟻群算法最早由意大利學者Marco Dorigo[19]于1992年提出，通過模擬自然界蟻群覓食行為實現尋優目的。蟻群算法存在搜索時間長，容易陷入局部最優、出現停滯現象等問題，為克服這些缺點，設計了改進蟻群算法。

(24)

(25)

(26)

(27)

(28)

改進蟻群算法流程圖如圖1所示。

圖1 改進蟻群算法流程圖

3 算例分析

3.1 實驗設置

采用Solomon標準數據集中的RC208算例進行仿真實驗。每個需求點的優先級隨機生成，配送中心的車輛數和儲貨容量足夠進行所有需求點的配送，所有車輛最大載重量為500。程序采用Matlab R2016a編寫，在環境為3.40GHz處理器、16G內存的計算機上運行。算法的參數設置為：最大循環次數iter_max=400；螞蟻數量m=50；信息素重要程度因子α=1；啟發函數重要程度因子β=3。算例中所用其他數據為：ω1=0.6，ω2=0.4，δ=0.5，q=2 000，q1=2.5，q2=0.016，q3=0.048。根據日常車流量的分布將通行時段設置為m=6，道路種類n=3，分別代表3種道路類型(好、普通、差)。對照實驗有兩組：第1組是不同目標函數的對照實驗，說明設計“成本+滿意度”目標函數的必要性；第2組是可選路徑的對照實驗，說明可供選擇路徑的存在的必要性。同時，用改進算法與原算法比較，證明了改進算法的有效性。

3.2 目標函數對實驗結果的影響

本次對比實驗分為3種情況：以“成本+滿意度”作為目標函數、僅以成本作為目標函數和僅以滿意度作為目標函數。由于所求得的是近似解，所以每次運行的結果有所差異，針對每種情況分別進行30次獨立仿真，取其中最接近平均值的單次仿真結果進行比較。

圖2 3種情況下的平均最優路徑規劃

圖3 3種情況下的目標函數適應度曲線

當目標函數為“成本+滿意度”時，得到最優解所用成本為13 349，滿意度達到94%。當目標函數僅考慮配送成本時，相比目標函數是雙目標的結果，完成配送所用的車輛數有所下降，成本降低13.7%，顧客滿意度下降8.5%，這種情況是以顧客滿意度的下降為代價來降低企業的配送成本。當目標函數以顧客滿意度為唯一標準時，完成配送所用的車輛數明顯增加，用來盡可能滿足各個需求點時間窗的要求；配送成本比“成本+滿意度”為雙目標函數的情況下上漲25%，同時滿意度上升2.1%。這表明僅考慮滿意度的方案為盡可能提高滿意度不計成本代價，故此方案不可行。以上比較結果列舉如表2所示。綜上，從權衡企業和顧客雙方利益考慮，模型中采用“成本+滿意度”的模式是值得借鑒的。

表2 3種情況下平均成本與滿意度的比較

3.3 可選路徑對結果的影響

為了說明可選擇路徑的存在對實驗結果的影響，假設任意兩點之間存在唯一的情況與存在可供選擇路徑的原模型作對比。表3結果顯示其他條件相同的情況下，可供選擇路徑的存在能夠大幅度增加顧客的滿意度。與具有可選擇路徑的原模型相比，單一路徑只能通過不斷調整配送順序來實現最小化配送成本和最大化滿意度的目標，因此具有可選擇路徑的原模型滿意度是最大的。對于其他參數與具有可選擇路徑的原模型相比，當模型中僅有最短路徑或中間路徑時，行駛距離減少，成本隨之降低；當模型中僅有最長路徑時，行駛距離增加，對應成本上升。

表3 單一路徑模型與多路徑原模型比較

3.4 改進算法對結果的影響

以上對照實驗說明在企業的物流車輛路徑問題中，建立考慮成本與顧客滿意度的雙目標規劃模型，提供可選擇的道路交通網絡，對于降低成本、提高顧客滿意度有十分明顯的效果。為了驗證改進后算法的有效性，用改進前算法對模型再次進行求解，結果對比如圖4a所示。改進后的算法收斂速度明顯增加，目標函數值也得到較好改善。同時，通過改進蟻群算法檢測顧客優先級的差異，首先滿足優先級較高的顧客所要求的時間窗。通過圖4b的對比，可以發現滿足時間窗的顧客點所占比例為94%，且顧客優先級越高，滿足時間窗的顧客數目所占比例越大。

圖4 算法改進前后對比

4 結論

本文研究了路網中任意兩點之間存在多條路徑選擇的帶時間窗和能力約束的變速車輛路徑問題，建立以總成本最小和客戶總體滿意度最大的雙目標混合整數規劃模型，利用改進蟻群算法對模型進行求解，仿真實驗結果表明所提的模型和算法是有效的。本研究仍存在一些需要改進的內容，如車輛行駛速度的描述不夠細致、理論分析有待加強，這些都是下一步要繼續研究的內容。