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

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

0 引言

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

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

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

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

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

1 建立模型

1.1 問(wèn)題描述

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

1.2 顧客滿(mǎn)意度

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

(1)

以時(shí)間窗衡量的全部顧客的平均滿(mǎn)意度為

(2)

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

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

(3)

以?xún)?yōu)先級(jí)衡量的所有顧客的加權(quán)平均滿(mǎn)意度描述為

(4)

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

f=ω1afTW+ω2fp

(5)

1.3 時(shí)變速度與路徑選擇

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

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

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

1.4 模型建立

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

Maxf=ω1afTW+ω2fp

(6)

MinQ=C1+C2+C3+C4

(7)

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

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

Min (1-f)

(8)

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

C1=pq

(9)

C2=q1s

(10)

(11)

(12)

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

(13)

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

2 算法設(shè)計(jì)

蟻群算法最早由意大利學(xué)者M(jìn)arco Dorigo[19]于1992年提出，通過(guò)模擬自然界蟻群覓食行為實(shí)現(xiàn)尋優(yōu)目的。蟻群算法存在搜索時(shí)間長(zhǎng)，容易陷入局部最優(yōu)、出現(xiàn)停滯現(xiàn)象等問(wèn)題，為克服這些缺點(diǎn)，設(shè)計(jì)了改進(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)。每個(gè)需求點(diǎn)的優(yōu)先級(jí)隨機(jī)生成，配送中心的車(chē)輛數(shù)和儲(chǔ)貨容量足夠進(jìn)行所有需求點(diǎn)的配送，所有車(chē)輛最大載重量為500。程序采用Matlab R2016a編寫(xiě)，在環(huán)境為3.40GHz處理器、16G內(nèi)存的計(jì)算機(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ù)日常車(chē)流量的分布將通行時(shí)段設(shè)置為m=6，道路種類(lèi)n=3，分別代表3種道路類(lèi)型(好、普通、差)。對(duì)照實(shí)驗(yàn)有兩組：第1組是不同目標(biāo)函數(shù)的對(duì)照實(shí)驗(yàn)，說(shuō)明設(shè)計(jì)“成本+滿(mǎn)意度”目標(biāo)函數(shù)的必要性；第2組是可選路徑的對(duì)照實(shí)驗(yàn)，說(shuō)明可供選擇路徑的存在的必要性。同時(shí)，用改進(jìn)算法與原算法比較，證明了改進(jìn)算法的有效性。

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

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

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

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

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

表2 3種情況下平均成本與滿(mǎn)意度的比較

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

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

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

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

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

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

4 結(jié)論

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