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

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

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

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

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

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

1 問題描述與模型

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

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

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

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

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

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

dij：各個頂點之間的歐式距離

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

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

ETi：配送車輛到達第i個社區(qū)的最早時間

LTi：配送車輛到達第i個社區(qū)的最晚時間

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

Si：配送車輛到達第i個社區(qū)的實際時間

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

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

2 方法描述

2.1 PSO算法的引入

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

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

2.2 算法具體過程

1）編碼方法

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

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

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

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

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

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

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

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

3）適應度計算

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

3 實驗結果和分析

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

圖1 PSO算法流程

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

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

將三種方式的計算結果進行比較，如表2所示。

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

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

從表2和圖2可以得出以下結論：

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

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

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

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

4 結 論

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

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

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

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

[4] 王征.多車場帶時間窗車輛路徑問題的模型和算法[D].大連：大連理工大學 （碩士學位論文），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] 陳嚴，劉利民.改進型PSO算法在VRP中的應用[J].計算機工程，2011,37(1):170-172.

[9] 黃小燕，文展,等.基于改進PSO的汽車路徑優(yōu)化[J].湘潭大學 （自然科學學報），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.