養(yǎng)老服務(wù)中配送車輛路徑問題研究

王鴻雁， 謝 勇 （華中科技大學(xué)，湖北 武漢 430074）

現(xiàn)今，中國社會(huì)老齡化現(xiàn)象變得日益嚴(yán)重，黨中央以及各級(jí)政府都越來越重視民生服務(wù)中的養(yǎng)老工作，并已將其納入了政策規(guī)劃之中。居家養(yǎng)老作為養(yǎng)老服務(wù)模式中最符合中國國情的一種模式，正受到社會(huì)和群眾的大力支持與推廣。養(yǎng)老服務(wù)中上門服務(wù)的配送問題也得到了更廣泛的關(guān)注。

養(yǎng)老配送服務(wù)主要是物資的調(diào)度和人員的指派，涉及到頂點(diǎn)、路網(wǎng)對(duì)稱性、車場(chǎng)點(diǎn)、車型與車程等元素，這構(gòu)成了車輛路徑問題的元素。但是養(yǎng)老服務(wù)的主要對(duì)象老人的特點(diǎn)是有時(shí)候比較多疑挑剔，喜歡討價(jià)還價(jià)，所以對(duì)蔬菜和牛奶等的新鮮程度以及某些暫時(shí)性短缺的藥品的即時(shí)性比較高，而此類物品自身對(duì)時(shí)間的要求也比較嚴(yán)格。同時(shí)，老人的出行時(shí)間、實(shí)際的道路交通狀況、車輛行駛速度和配送途中各種意外情況等都是不確定因素，因此，配送過程有時(shí)間窗約束。另外，車輛本身對(duì)載容量和載重量都有一定的限制。可見，養(yǎng)老服務(wù)配送問題實(shí)際上就是帶時(shí)間窗的車輛路徑問題。

從車輛路徑問題提出至今，國內(nèi)外學(xué)者針對(duì)車輛路徑問題中配載與配送問題已經(jīng)有過不少研究。楊錦冬[1]基于客戶時(shí)間窗約束、道路交通條件約束和車輛承載能力約束等限制條件，建立了車輛總行走時(shí)間最短和配載貨物最多的兩目標(biāo)優(yōu)化模型組，反映實(shí)際的調(diào)度問題。王永亮[2]系統(tǒng)分析了面向城鎮(zhèn)連鎖經(jīng)營物流配載與配送組合優(yōu)化問題的構(gòu)成要素，研究了多配送中心、多車型、無時(shí)間窗限制和軟時(shí)間窗限制混合、車輛閉環(huán)運(yùn)行的VRP問題。李相勇[3]對(duì)車輛路徑問題的構(gòu)成要素和擴(kuò)展標(biāo)準(zhǔn)作了仔細(xì)的討論和分類，并對(duì)各類VRP問題進(jìn)行了建模和求解。王征[4]對(duì)多車場(chǎng)問題作了概述，同時(shí)對(duì)時(shí)間窗問題做了分類，給出了數(shù)學(xué)模型，并用改進(jìn)的變鄰域搜索算法進(jìn)行了求解。文章[5]根據(jù)城市蔬菜配送公司的實(shí)際情況，創(chuàng)新性地同時(shí)考慮了車輛路徑問題中人力參與較多、多車型、不同車型的固定費(fèi)用和行駛費(fèi)用不同且?guī)в矔r(shí)間窗等問題，并同時(shí)考慮車型與任務(wù)的相容性。SOLOMO等[6]并未對(duì)問題模型進(jìn)行描述，而是在理論上分析了解決時(shí)間窗的車輛路徑問題的多種啟發(fā)式算法。文章[7]則研究了帶時(shí)間窗的同時(shí)收發(fā)貨的實(shí)時(shí)車輛路徑問題。文獻(xiàn)[8-10]則采用了PSO或改進(jìn)的PSO算法求解。

本文假設(shè)要配送的貨物是生鮮蔬菜、水果和非處方藥品等類型的貨物，可以混裝，且不考慮多周期配送的問題，將送貨地點(diǎn)抽象為社區(qū)進(jìn)行研究。由于客戶對(duì)生鮮蔬菜和水果的配送優(yōu)先級(jí)的要求有其特殊的時(shí)間特征，文中考慮客戶的時(shí)間窗約束條件和車輛的空間利用率，優(yōu)化整個(gè)配送過程。

1 問題描述與模型

本文將問題描述為簡(jiǎn)化考慮單配送中心和單車型以及單車程配送的軟時(shí)間窗問題，且各社區(qū)距配送中心的距離以及各社區(qū)之間的距離已知。各個(gè)社區(qū)的貨物需求容量已知，每輛車的車型相同，其額定載容量已知，同時(shí)已知要求將貨物送到的時(shí)間窗，要求合理安排車輛的配送路線，使總配送距離最短、車輛利用率最大、超出時(shí)間窗的時(shí)間總量最少。

為考慮問題的一般性，做如下的模型假設(shè)：

1）假定每個(gè)社區(qū)是一個(gè)顧客點(diǎn)，且每個(gè)社區(qū)點(diǎn)所需的貨物不可拆分；2）配送路線對(duì)稱，且兩社區(qū)之間的距離即為兩地實(shí)際地理坐標(biāo)的幾何距離；3）每輛車必須從配送中心發(fā)出，最后回到配送中心；4）配送中心的貨物總量能滿足社區(qū)的貨物需求量，且各社區(qū)的需求量不超過配送車輛的容量；5）忽略卸貨時(shí)間，且行駛速度始終不變。

建立數(shù)學(xué)模型如下：

m：配送中心擁有的車輛數(shù)

n：頂點(diǎn)數(shù)目，n=0表示配送中心，n=1,2,…,n表示各個(gè)社區(qū)點(diǎn)

dij：各個(gè)頂點(diǎn)之間的歐式距離

vi：各個(gè)社區(qū)的貨物需求體積

V：每輛配送車輛的最大載容量 （車型相同）

ETi：配送車輛到達(dá)第i個(gè)社區(qū)的最早時(shí)間

LTi：配送車輛到達(dá)第i個(gè)社區(qū)的最晚時(shí)間

tij：配送車輛從第i個(gè)社區(qū)到第j個(gè)社區(qū)的行駛時(shí)間，與距離成比例

Si：配送車輛到達(dá)第i個(gè)社區(qū)的實(shí)際時(shí)間

上述模型中式 （1）表示目標(biāo)函數(shù)，是車輛總行駛路程最短、車輛空間利用率最大、早到或晚到時(shí)間總量最小四個(gè)優(yōu)化目標(biāo)的綜合，由于四個(gè)目標(biāo)的重要性和量綱不同，賦予不同的權(quán)重將多目標(biāo)變?yōu)閱文繕?biāo)，其中λ1、λ2、λ3、λ4表示各項(xiàng)權(quán)重，根據(jù)實(shí)際要求進(jìn)行設(shè)置，以此來保證優(yōu)化目標(biāo)的層次優(yōu)先級(jí)別[2]。 （2）表示每個(gè)社區(qū)點(diǎn)只能被一輛車服務(wù)。 （3）表示每個(gè)社區(qū)點(diǎn)j只能由來之其他點(diǎn)的所有車中的一輛車來服務(wù)。 （4）表示車輛k的配送路線上的社區(qū)點(diǎn)所需求貨物的體積之和不超過車輛的額定載容量Q。 （5）和 （6）分別表示每輛車必須從車場(chǎng)中心發(fā)出來服務(wù)社區(qū)且服務(wù)完其路線上最后一個(gè)社區(qū)后必須回到車場(chǎng)中心。 （7）表示車輛實(shí)際到達(dá)每個(gè)社區(qū)點(diǎn)的時(shí)刻。 （8）和 （9）分別表示兩個(gè)決策變量。

實(shí)際中老年人更注重時(shí)間上的有效性，因而權(quán)重系數(shù)λ3、λ4應(yīng)較大，晚到會(huì)降低對(duì)老人的服務(wù)質(zhì)量，故λ3比λ4要設(shè)置的相對(duì)小一些。另外，配送中心自身的成本付出中載容利用率和運(yùn)輸距離，更傾向于優(yōu)化運(yùn)輸距離，故λ1比λ2要設(shè)置的大一些，但兩者都要小于λ3、λ4。模型中的權(quán)重系數(shù)可以根據(jù)實(shí)際問題中對(duì)約束條件的要求程度用層次分析法 （AHP法）求出[2]。

2 方法描述

2.1 PSO算法的引入

對(duì)于車輛路徑問題，很多時(shí)候并不能找到最優(yōu)解，而只是找到較優(yōu)解，因?yàn)閱栴}的解即各車輛的排列組合的搜索范圍過大。由于問題中約束條件較多，當(dāng)問題規(guī)模較大時(shí)，要事先得到一個(gè)可行解也十分不容易。而啟發(fā)式算法中PSO算法則可以很好的解決了這個(gè)問題，因?yàn)镻SO算法實(shí)際上是基于迭代的優(yōu)化啟發(fā)式算法，系統(tǒng)將為其初始化一個(gè)隨機(jī)解，再經(jīng)過迭代搜索找到最優(yōu)解。

PSO的優(yōu)勢(shì)十分明顯，能對(duì)解進(jìn)行并行處理且魯棒性好、實(shí)現(xiàn)簡(jiǎn)單、精度高、收斂快，也沒有許多參數(shù)需要調(diào)整，能以較大的概率找到優(yōu)化問題的全局最優(yōu)解。但同時(shí)它也有一定的缺陷，如在大規(guī)模問題中易陷入局部最優(yōu)[8-9]。文獻(xiàn)[10]提出的隨機(jī)慣性權(quán)重PSO算法，能有效克服種群中所有粒子共享同一慣性權(quán)重的問題，使所有粒子都能向優(yōu)化方向移動(dòng)，從而提高PSO的搜索性能，使搜索過程有效地跳出局部最優(yōu)，搜索全局最優(yōu)。

2.2 算法具體過程

1）編碼方法

一般文獻(xiàn)中對(duì)于算法的編碼都會(huì)采用實(shí)數(shù)編碼方法，即對(duì)n個(gè)社區(qū)點(diǎn)，K輛車服務(wù)的車輛路徑問題，解的維度D=n+K-1。即在顧客點(diǎn)序列中插入K-1個(gè)0，則由0分開的序列組成一個(gè)車輛行駛路線。實(shí)數(shù)編碼中維度同時(shí)依賴于車輛數(shù)和顧客點(diǎn)數(shù)目。

文中采用另一種編碼方式，讓維度只依賴顧客點(diǎn)數(shù)目，且更大。對(duì)n個(gè)社區(qū)點(diǎn)，K輛車服務(wù)的車輛路徑問題，將適應(yīng)度函數(shù)對(duì)應(yīng)的自變量即每個(gè)粒子設(shè)計(jì)為一個(gè)2n維的向量，分成2個(gè)n維向量：前n維Xk表示順次客戶點(diǎn)所使用的車輛編號(hào)，后n維Xo表示各社區(qū)在對(duì)應(yīng)的路線中的優(yōu)先級(jí)次序。

這樣編碼直觀的顯示出服務(wù)每個(gè)社區(qū)車輛編號(hào)，也能明確得出每條路線上車輛服務(wù)的先后順序。同時(shí)保證每個(gè)社區(qū)點(diǎn)都能得到車輛的服務(wù)，并限制每個(gè)社區(qū)點(diǎn)僅能由一輛車來服務(wù)，從而減少解的可行性計(jì)算過程。另外，PSO算法在多維尋優(yōu)問題中有較好的特性，維數(shù)的增大也不會(huì)增加計(jì)算的復(fù)雜性。

2）更新粒子狀態(tài)

事先約定種群大小為N，則粒子i i=1,2,…,（ ），位置則表示為 xi=xi1,xi2,…,xid

（N 在 d d=1,2,…,2）（n 維解空間中的速度可表示為vi=vi1,vi2,…,vid）

上式中，w表示慣性權(quán)重，值越大粒子的全局探索能力越強(qiáng)，值越小粒子的局部挖掘能力越強(qiáng)；c1和c2表示自身和社會(huì)的慣性系數(shù)，表明粒子自我和群體的學(xué)習(xí)能力；rand1和rand2是獨(dú)立的均勻分布于0,［］1 之間的隨機(jī)數(shù)。pid是當(dāng)前粒子搜索到的歷史最佳位置，pgd是整個(gè)粒子種群搜索到的歷史最佳位置。

文獻(xiàn)[10]中提出隨機(jī)慣性權(quán)重粒子群算法，其粒子的狀態(tài)更新公式為：（ ）。粒子在整個(gè)搜索空間內(nèi)的狀態(tài)更新將通過下面的兩個(gè)式子進(jìn)行更新：

3）適應(yīng)度計(jì)算

文中數(shù)學(xué)模型，既有載容量的約束，又有時(shí)間窗約束，故采用罰函數(shù)來處理，將這些約束條件一起寫進(jìn)目標(biāo)函數(shù)中，而粒子的適應(yīng)度則直接用目標(biāo)函數(shù)表示。利用PSO算法解決VRP問題的具體流程如圖1所示。

3 實(shí)驗(yàn)結(jié)果和分析

本文設(shè)計(jì)了一個(gè)簡(jiǎn)單的算例，3輛車服務(wù)8個(gè)社區(qū)，并假定每輛車的額定載容量為 V=8。 λ1、 λ2、 λ3、 λ4分別取值為 0.249,0.037,0.32,0.394。 測(cè)試如下數(shù)據(jù)，配送中心和每個(gè)社區(qū)點(diǎn)的坐標(biāo)、需求容量數(shù)據(jù)如表1。

圖1 PSO算法流程

表1 社區(qū)的坐標(biāo)及需求

取粒子數(shù)N=50，最大迭代數(shù)M=100。w=0.7，c1=1.3和c2=2.8，對(duì)隨機(jī)慣性權(quán)重PSO算法取參數(shù)k=1，隨機(jī)進(jìn)行50次計(jì)算。得出的最優(yōu)結(jié)果為：車輛1：0-4-0；車輛2：0-3-8-1-0；車輛3：0-2-6-7-5-0。

將三種方式的計(jì)算結(jié)果進(jìn)行比較，如表2所示。

表2 執(zhí)行50次結(jié)果比較表

將三種方式的PSO算法分別執(zhí)行50次得到的結(jié)果分布情況如圖2。

從表2和圖2可以得出以下結(jié)論：

①兩種編碼的最優(yōu)值都是143.2，兩種編碼并沒有太多的優(yōu)劣性，不管采用何種方式，都可以求出最優(yōu)值，但搜索成功率都不高。

②標(biāo)準(zhǔn)PSO算法搜索過程達(dá)到最優(yōu)值的次數(shù)小于50%，而采用隨機(jī)慣性權(quán)重PSO進(jìn)行改進(jìn)后，只有5次沒達(dá)到最優(yōu)值，搜索成功率大大提高。

③在相同的執(zhí)行次數(shù)情況下，盡管耗費(fèi)的時(shí)間成本高一些，但隨機(jī)慣性權(quán)重PSO算法達(dá)到最優(yōu)值的次數(shù)比標(biāo)準(zhǔn)PSO算法達(dá)到的多，所耗費(fèi)的平均成本也小一些。

綜合評(píng)估平均搜索時(shí)間、平均成本和搜索成功率，隨機(jī)慣性權(quán)重PSO算法對(duì)解決VRP問題有較優(yōu)的效果。

4 結(jié) 論

本文針對(duì)現(xiàn)今社會(huì)呈現(xiàn)的老齡化現(xiàn)象，提出了具有代表性的養(yǎng)老服務(wù)中的物流配送問題，并建立了合理的數(shù)學(xué)模型。同時(shí)，對(duì)PSO算法的編碼方式以及標(biāo)準(zhǔn)PSO和改進(jìn)PSO進(jìn)行簡(jiǎn)單的比較，并求解了一個(gè)較為簡(jiǎn)單的算例。結(jié)果表明，隨機(jī)慣性權(quán)重PSO算法對(duì)于車輛路徑問題的求解有較高的搜索成功率。但本文只對(duì)養(yǎng)老配送問題中基本的帶時(shí)間窗VRP模型進(jìn)行了研究，未考慮速度對(duì)車輛行駛時(shí)間的影響，也忽略了混裝相容性等約束條件對(duì)模型的影響，以后可以對(duì)這些方面進(jìn)行更深入的研究。

[1] 楊錦冬，徐立群.城市物流中心車輛配送配載調(diào)度指派模型研究[J].同濟(jì)大學(xué)學(xué)報(bào)，2004,32(11):1452-1456.

[2] 王永亮.面向連鎖經(jīng)營的物流配載與配送組合優(yōu)化模型與算法研究[D].北京：北京交通大學(xué) （碩士學(xué)位論文），2007.

[3] 李相勇.車輛路徑問題模型及算法研究[D].上海：上海交通大學(xué) （博士學(xué)位論文），2007.

[4] 王征.多車場(chǎng)帶時(shí)間窗車輛路徑問題的模型和算法[D].大連：大連理工大學(xué) （碩士學(xué)位論文），2010.

[5] 肖和山.城市蔬菜配送車輛調(diào)度模型與啟發(fā)式算法研究[J].湘潮，2009(9):56-58.

[6] Marius M.Solomo.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research,1987,35(2):254-266.

[7]Mei-shiang Chang,Shyang-ruey Chen,Che-fu Hsueh.Real-time Vehicle Routing Problem with Time Windows and Simultaneous Delivery/pickup Demands[J].Journal of the Eastern Asia Society for Transportation Studies,2003(5):2273-2286.

[8] 陳嚴(yán)，劉利民.改進(jìn)型PSO算法在VRP中的應(yīng)用[J].計(jì)算機(jī)工程，2011,37(1):170-172.

[9] 黃小燕，文展,等.基于改進(jìn)PSO的汽車路徑優(yōu)化[J].湘潭大學(xué) （自然科學(xué)學(xué)報(bào)），2009,31(2):166-170.

[10] Zhang Q,Mahfouf M.A New Structure for Particle Swarm Optimization （nPSO） Applicable to Single Objective and Multiobjective Problems[C]∥Proc of the IEEE Int'l IEEE Conf Intelligent Systems,2006.