基于改進粒子群算法的需求可拆分路徑問題研究

(1.北京物資學院 研究生部 北京 101149；2.北京物資學院 信息學院 北京 101149)

一、引言

需求可拆分的路徑優化問題是基本車輛路徑問題(Vehicle Routing Problem，VRP)的延伸和擴展。需求可拆分路徑問題在現實生活中有更重要的應用價值。比如車輛的裝載量小于需求點的需求量時，需要將需求量拆分開來。目前國內對需求可拆分路徑問題的研究較少[1-3]，更多的集中在對求解模型的算法研究上[4-6]。這些算法編碼和解碼時比較復雜，容易陷入最優解。

文中用到的粒子群優化算法(PSO)是由美國社會心理學家Kennedy 和電氣工程學家 Eberhart[7]在 1995年提出的一種模仿鳥群覓食飛行的一種群智能優化算法，具有參數設置少，精度高，收斂快，容易實現等優點，在車輛調度問題優化中已取得初步的研究成果[8-9]。Zhan Z[10]，D.M.Munoz[11]和Jin,Xin[12對粒子群進行了種群分類方面的改進，即當粒子群處于不同階段時，粒子群的參數作出相應的改變。本文用到的粒子群算法是動態更新全局最優解，仿真實驗表明，該算法能找到更優的解。

二、需求可拆分路徑問題及模型

(一)需求可拆分路徑問題描述

本文重點研究需求可拆分路徑問題。問題描述如下：將需求量超過車輛裝載量的需求點虛擬化為2個點使每個點的需求量都不超過車輛的裝載量。車輛從車場出發先到需求點的供應地取貨，再送達該需求點。要求車輛在客戶的時間窗內送達，早到或晚到需求點都有成本產生，并且車輛在不同的時間段有不同的行駛速度。問題的目標函數是車輛的行駛時間和等待時間最少。在這個過程中車輛必須在規定的時間內返回車場防止司機疲勞過度。在本模型中還考慮了司機對裝卸貨流程和標準的熟悉度這個因素，該因素會影響到車輛在需求點的服務時間。

(二)假設條件

為了研究并建立該問題的模型，這里做出以下假設：

(1)每個車場擁有相同數目的車輛，每輛車的裝載量相同。

(2)每個供應地的貨物數量充足，不會有缺貨的情況存在；每個供應地供應的貨物相似，車輛每次的取貨量至少能滿足一個對應的需求點的量。

(3)比顧客允許的最早送達貨物的時間點早的時刻為15min，如超過15分鐘則其超出時間窗的時間長度為+∞。

(4)比顧客允許的最晚送達貨物的時間點晚的時刻為15min，如果超過15分鐘則其超出時間窗的時間長度為+∞。

(5)司機對裝卸貨流程和標準的熟悉度符合均勻分布U(30,60)。

(6)本文研究該模型的最終目標原則是總時間最小。

(三)符號說明

(a)O''={o1,o2,…,on,on+1}：表示車場和所包含的客戶點的集合其中on+1代表車場。

(b)P={p1,p2,…,pe′}：表示司機提取貨物的供應地集合；

(c)R={r1,r2,…,rf′}：表示需求點的集合；

(d)S={s1,s2,…,sq}：表示一個周期S包含q天，訂單集合的數目是在這個周期內的數目之和；

(e)m：表示車輛在m個時間段上行駛時有m個速度區段。

(f)K：表示每個車場中車輛的數目；

(g)ai：表示顧客允許的最早送達貨物的時間點；

(h)ai′：表示比顧客允許的最早送達貨物的時間點早的時刻，大小為ai-15；

(m)bi：表示顧客允許的最晚送達貨物的時間點；

(o)bi′：表示比顧客允許的最晚送達貨物的時間點晚的時刻，大小為bi+15；

(p)Tski表示在周期s車輛k到達點i的時間點，其中，s=1,2,…,q,i=1,2,…,n+1；

(q)tskij：表示在周期s車輛k從需求點i到需求點j的行駛時間，其中，s=1,2,…,q,k=1,2,…,K,i,j=1,2,…,n+1；

(r)FTsi：表示在周期s車輛在點i的標準服務時間，其中，s=1,2,…,q,i=1,2,…,n+1；

(s)α：表示司機對裝卸貨流程和標準的熟悉度；

(u)Lski：表示在周期s車輛k從需求點點i離開的時刻，其中，s=1,2,…,q,k=1,2,…,K,i,j=1,2,…,n+1;

(w)vm：代表車輛從客戶i至客戶j行駛時所處的時間區段m上的速度；

(y)l：表示兩個客戶點之間所在的時間區段的個數；

(z)c(Tski)：代表與車輛到達客戶點時間有關的超出時間窗的時間長度的計算函數；

問題的決策變量如下：

c(Tski)超出時間窗的時間長度函數的計算方式如下：當車輛到達客戶點i的時間Tski在該客戶點的時間窗內時，c(Tski)=0；當車輛早到但沒有早過ai′時，c(Tski)=ai-Tski，到達時間早過ai′時c(Tski)=+∞；當車輛晚到但沒有晚過bi′時，c(Tski)=Tski-bi，到達時間晚過bi′時，c(Tski)=+∞。c(Tski)計算公式如下式：

(1)

α表示司機對裝卸貨流程和標準的熟悉度會影響到FTsi的值，α越大表示熟悉度越小，裝卸貨的時間FTsi越長。

α計算公式如下式：

(2)

(3)

(四)模型建立

本文將基于多車場的需求可拆分的路徑優化問題轉化為單車場的需求拆分問題，目標是使車輛行駛時間和超出時間窗的時間長度最小。其目標函數模型如下：

(4)

約束條件為：

(5)

(7)

(8)

(9)

(10)

(11)

(12)

Lski+tskij=Tskj,s=1,2,…,q,k=1,2,…,K,i=1,2,…,n+1

(13)

(14)

其中式(4)是模型的目標函數，表示車輛總的行駛時間和車輛到達時間與客戶時間窗只差的總和；式(9)表示每個客戶點的任務被完成且完成一次；式(10)表示車輛k從點p進入完成任務后從點p出來；式(11)表示每輛車由配送中心出發；式(12)表示每輛車回到配送中心；式(13)表示每輛車若到達j點必為j服務；式(14)表示一個周期內從車場出發的車輛數目不超過K；式(15)表示每輛車的總行駛時間不能超過一個周期的長度；式(16)表示在一個周期內車輛離開客戶點的時間等于車輛到達該點的時間加上在該點的服務時間。

三、求解需求可拆分路徑問題的改進粒子群算法

(一)改進的粒子群算法

在粒子更新過程中更新全局最優解。一般的粒子群算法是在整個粒子群更新完之后找到整個群體的最優解，再和沒有更新前的全局最優解比較，兩者中較優的作為下一代更新的全局最優解。本文的方法是在粒子群更新的過程中如出現比當前全局最優解更優的解則將此粒子更新后的位置作為最優解替代當前的全局最優解。

(二)求解需求可拆分問題的改進粒子群步驟

(1)初始化粒子群，包括粒子個數，每個粒子的位置和速度。

(2)計算每個粒子的適應度函數，找到各個粒子的當前個體極值，找到整個粒子群的當前全局最優解。根據改進的粒子群算法得到新的全局最優解。

(3)根據公式(15),(16)更新各個粒子的速度和位置。

(4)判斷更新次數是否到達最大更新次數，如果等于最大更新次數，則結束更新，將當前最優解輸出作為求解模型的最優解。如果沒有達到最大更新次數則轉到步驟(2)。

粒子更新公式如下：

Vid=w*Vid+c1*c12*(Pid-Xid)+c2*c22*(Pgd-Xid)

(15)

Xid=Xid+Vid

(16)

四、算例分析

本算例以一個車場30個客戶點6個供應點為基礎，車輛需在48小時內返回車場。算法中的w=1.2，c1=0.8，c2=0.8。其中w是慣性因子，w越大表示粒子搜索的空間越大，c1和c2是學習因子，分別表示粒子對本身歷代最優解的學習和對全局最優解的學習，c1和c2越大表示粒子越向最優解靠近。表3中的目標值單位是秒，表示車輛行駛時間和車輛到達時間與需求點的時間窗的差值的總和。部分算例數據如下表：

表1 需求點坐標

表2 需求點坐標

表3 改進前后對比

五、結語

本文在模型中加入司機對裝卸貨流程和標準的熟悉度因素，并考慮將需求點虛擬化以解決超過車輛裝載量問題。針對該問題建立了需求可拆分的路徑問題，并用改進的粒子群算法求解。仿真實驗表明，該算法能較快找到相對最優解。算法中如何更好地調整參數使之找到更優的解釋之后值得研究的方向。w越大表示粒子搜索的空間越大，發現更優解的可能性越大，c1和c2越大表示粒子越向最優解靠近，所以w與c1與c2之間有相互制約的關系，只有互相配合的取值大小才會保證粒子既能有大的搜索空間的可能有能向最優解靠近。