多路徑選擇變速雙目標(biāo)物流配送路徑規(guī)劃

孔 珊，仲昭林，張紀(jì)會

(青島大學(xué) a.復(fù)雜性科學(xué)研究所；b.山東省工業(yè)控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島 266071)

0 引言

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

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

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

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

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

1 建立模型

1.1 問題描述

某配送中心為客戶提供配送服務(wù)，配送車輛服務(wù)能力有限，路網(wǎng)上任意兩點(diǎn)之間存在多條路況不同的路徑，且同一路徑上車輛的行駛速度隨通行時刻的不同而變化。配送車輛從配送中心出發(fā)，在規(guī)定時間窗內(nèi)對客戶進(jìn)行服務(wù)，完成對最后一個客戶的服務(wù)后返回配送中心。每個客戶都有設(shè)定的服務(wù)時間窗和需求量，且客戶具備不同優(yōu)先級，目標(biāo)是設(shè)計配送路線，用最少的車輛在規(guī)定時間內(nèi)完成所有配送任務(wù)，實(shí)現(xiàn)最小化配送成本和最大化客戶滿意度的目標(biāo)。

1.2 顧客滿意度

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

(1)

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

(2)

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

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

(3)

以優(yōu)先級衡量的所有顧客的加權(quán)平均滿意度描述為

(4)

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

f=ω1afTW+ω2fp

(5)

1.3 時變速度與路徑選擇

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

表1 道路類型、通行時段與速度的關(guān)系

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

1.4 模型建立

此模型有兩個目標(biāo)函數(shù)：

Maxf=ω1afTW+ω2fp

(6)

MinQ=C1+C2+C3+C4

(7)

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

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

Min (1-f)

(8)

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

C1=pq

(9)

C2=q1s

(10)

(11)

(12)

其中，p為使用車輛數(shù)，q為每輛車的固定費(fèi)用，q1，q2，q3分別為單位路程(時間)內(nèi)產(chǎn)生的車輛可變成本，xih為判斷車輛是否為顧客提供配送服務(wù)的0-1變量。總路程s可表示為

(13)

為消除滿意度和成本的數(shù)量級差距帶來的影響，公式(14)對兩者取對數(shù)，再用加權(quán)方式將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。對應(yīng)的加權(quán)系數(shù)分別為δ和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)表示綜合最小成本和最大總體滿意度的目標(biāo)函數(shù)；式(15)表示所有車輛的容量需要滿足配送總量；式(16)表示車輛h的實(shí)際載重；式(17)表示車輛的實(shí)際載重不能超過車輛的最大容量；式(18)表示同一個需求點(diǎn)只能被服務(wù)一次；式(19)表示配送過程中每輛車只能使用一次；式(20)表示每個需求點(diǎn)只能被一輛車服務(wù)；式(21)表示每輛車至少要為一個需求點(diǎn)服務(wù)，這里H′表示配送過程中使用車輛的集合；式(22)和(23)為相應(yīng)的0、1決策變量。

2 算法設(shè)計

蟻群算法最早由意大利學(xué)者M(jìn)arco Dorigo[19]于1992年提出，通過模擬自然界蟻群覓食行為實(shí)現(xiàn)尋優(yōu)目的。蟻群算法存在搜索時間長，容易陷入局部最優(yōu)、出現(xiàn)停滯現(xiàn)象等問題，為克服這些缺點(diǎn)，設(shè)計了改進(jìn)蟻群算法。

(24)

(25)

(26)

(27)

(28)

改進(jìn)蟻群算法流程圖如圖1所示。

圖1 改進(jìn)蟻群算法流程圖

3 算例分析

3.1 實(shí)驗(yàn)設(shè)置

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

3.2 目標(biāo)函數(shù)對實(shí)驗(yàn)結(jié)果的影響

本次對比實(shí)驗(yàn)分為3種情況：以“成本+滿意度”作為目標(biāo)函數(shù)、僅以成本作為目標(biāo)函數(shù)和僅以滿意度作為目標(biāo)函數(shù)。由于所求得的是近似解，所以每次運(yùn)行的結(jié)果有所差異，針對每種情況分別進(jìn)行30次獨(dú)立仿真，取其中最接近平均值的單次仿真結(jié)果進(jìn)行比較。

圖2 3種情況下的平均最優(yōu)路徑規(guī)劃

圖3 3種情況下的目標(biāo)函數(shù)適應(yīng)度曲線

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

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

3.3 可選路徑對結(jié)果的影響

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

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

3.4 改進(jìn)算法對結(jié)果的影響

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

圖4 算法改進(jìn)前后對比

4 結(jié)論

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