考慮總量和體積雙重約束的時(shí)間窗車輛路徑問題研究

金　葉　丁以中

摘要: 車輛路徑問題是被學(xué)者普遍研究的一個(gè)問題，也是一個(gè)經(jīng)久不衰的研究課題。文章通過對(duì)車輛路徑問題的改進(jìn)，基于多種種類的貨物，對(duì)考慮貨物的不同重量和體積限制的帶時(shí)間窗的車輛路徑問題建立模型，通過粒子群算法求解模型，給出合適的解決方案。

關(guān)鍵詞: 車輛路徑；時(shí)間窗；重量；體積；多重約束；粒子群算法

中圖分類號(hào): U116.2文獻(xiàn)標(biāo)識(shí)碼: A

Abstract：VRP is usually studied by researchers from its beginning. An improvement of VRP is studied in this paper. An VRPTW model considering both weight and volume restricts is seted, then solve the problem using PSO（Partical Swarm Optimization）method.

Key words: VPR；time window；weight；volume；mulriple restricts；PSO

0引言

車輛路徑的選擇對(duì)物流配送的成本有很大的影響, 如何在眾多的配送路線方案中選擇一個(gè)較優(yōu)的方案是物流運(yùn)行過程中需要解決的重要問題, 也正是車輛路徑優(yōu)化所要解決的問題。由于車輛路徑問題的重要性及其復(fù)雜性，眾多的學(xué)者在該領(lǐng)域有過研究。早在1962年，Balinski等人首先提出VRP的集分割，直接考慮可行解集合，在此基礎(chǔ)上進(jìn)行優(yōu)化，建立了最簡(jiǎn)單的VRP模型。由于車輛路徑問題的復(fù)雜性，對(duì)其求解有很大的困難，因此不斷有學(xué)者加入此領(lǐng)域的研究。1991年，Gendreau等人將禁忌搜索方法應(yīng)用于VRP。1996年，J.La wrence將遺傳算法用于VRP的研究，并可有效求解帶時(shí)間窗口的VRP。

車輛路徑問題的一般描述是： 對(duì)一系列給定的客戶（送貨點(diǎn)或取貨點(diǎn)），確定適當(dāng)?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序地通過它們，最后返回配送中心，并在滿足一定的約束條件下（如車輛容量限制、行駛里程限制、時(shí)間限制、顧客需求量、交發(fā)貨時(shí)間等），達(dá)到一定的目標(biāo)（如路程最短、費(fèi)用最少、時(shí)間盡量少、使用車輛數(shù)盡量少等）。如圖1所示。

縱觀前人對(duì)車輛路徑問題的研究，絕大多數(shù)是對(duì)于網(wǎng)絡(luò)規(guī)模的擴(kuò)大和求解算法的研究，對(duì)車輛路徑問題模型本身則鮮有改進(jìn)，本文的研究著眼于對(duì)模型的改進(jìn)，結(jié)合被運(yùn)輸貨物本身的多樣性，考慮在貨物多種屬性（主要是重量和體積）的影響下車輛路徑的選擇問題。

1問題描述

在研究車輛路徑問題時(shí)，深入企業(yè)間物流配送運(yùn)作的實(shí)際情況，很多情況下需要考慮被運(yùn)輸貨物的多種屬性。比如在裝運(yùn)時(shí)，有些貨物雖然較輕，但是體積較大，在運(yùn)輸作業(yè)中成為輕泡貨物，假如只考慮車輛的載重量對(duì)其的約束，那么一輛車上能夠運(yùn)載很多這樣的貨物，那顯然是不合理的。這只是一個(gè)簡(jiǎn)單的例子來說明運(yùn)輸時(shí)同時(shí)考慮重量和體積約束的必要性，在實(shí)際運(yùn)載過程中會(huì)遇到很多不同種類的貨物需要同裝一輛車的情況，那么情況就較為復(fù)雜了。本文就是基于這個(gè)角度出發(fā)，對(duì)經(jīng)典的帶時(shí)間窗的車輛路徑問題模型予以改進(jìn)，考慮貨物不同種類造成的其體積和重量雙重約束對(duì)模型的影響，并且對(duì)其進(jìn)行求解。

2模型建立

目標(biāo)函數(shù)：minZ=cx+PmaxETi-si,0+Pmaxsi-LTi,0

St.xijk=xjik≤1, i=0, k∈{1,2,…,K}（1）

xijk=1, i∈{1,2,…,L}（2）

xijk=1, j∈{1,2,…,L}（3）

gixijk≤q, k∈{1,2,…,K}（4）

vixijk≤V, k∈{1,2,…,K}（5）

ETi≤Si≤LTi, i∈{1,2,…,L}（6）

gi=vi h（7）

其中: 目標(biāo)函數(shù)保證了總成本Z 最小，式中PE，PL分別是指早到的單位懲罰值和晚到的單位懲罰值; 式（1） 確保車輛從配送中心出發(fā)回到配送中心; 式（2）、式（3）保證每個(gè)客戶只能被一輛車服務(wù)一次; 式（4）是車輛的載重能力的約束; 式（5）是對(duì)車輛容積的限制；式（6）是時(shí)間窗約束，這個(gè)約束在目標(biāo)函數(shù)中不存在對(duì)遲到和早到的罰函數(shù)式起效（即硬時(shí)間窗約束），在本文中這個(gè)約束不起作用，因?yàn)楸疚目紤]的是軟時(shí)間窗的約束; 式（7）中Ph是指不同種類的被運(yùn)輸貨物有不同的密度，這樣導(dǎo)致同一車內(nèi)的貨物可能屬于不同的種類，要求我們同時(shí)考慮其重量和體積對(duì)模型的影響，h表示有h種不同的貨物。

Sj=xijkS+S+t，j∈{1,2,…,L}（8）

Sij=cij /v（9）

K=max+1，+1，為車輛裝載噸位利用系數(shù)，為車輛裝載容積利用系數(shù)（10）

式（8）中: Si表示車輛到達(dá)任務(wù)點(diǎn)i的時(shí)間；Sij表示車輛從客戶i 到客戶j 的行駛時(shí)間，如式（9）中所示； ti 表示客戶點(diǎn)i的服務(wù)時(shí)間, i, j∈{0, 1,…,L}, S0=0，t0=0。為了便于求解，模型根據(jù)中的運(yùn)輸量事先確定所需要使用的車輛數(shù)，其依據(jù)是車輛的容積和重量哪個(gè)成為瓶頸約束，就考慮按哪個(gè)約束確定所需要使用的車輛數(shù)。如公式（10）所示，+1是取整的意思，g表示所有需要運(yùn)送貨物的總重量，q表示每輛車所能裝載的重量。表示在考慮了車輛的噸位利用率為時(shí)，考慮重量的限制所需要的車輛數(shù)。同理，+1，v表示所有需要運(yùn)送貨物的總體積，V表示每輛車所能利用的容積，這個(gè)式子是指車輛的容積利用率為時(shí)，考慮體積的限制所需要的車輛數(shù)。

3算法

本模型的求解中采用粒子群優(yōu)化算法（Partical Swarm Optimization，PSO）。粒子群算法是由Kennedy和Eberhart等于1995年開發(fā)得一種演化計(jì)算技術(shù), 該算法通過模擬鳥集群飛行覓食的行為, 通過鳥的集體協(xié)作使群體達(dá)到最優(yōu)目的。

粒子群群算法簡(jiǎn)介：

在PSO 系統(tǒng)中, 每個(gè)備選解被稱為一個(gè)“粒子”（Partical）多個(gè)粒子共存、合作尋優(yōu), 每個(gè)粒子根據(jù)它自身的“經(jīng)驗(yàn)”和相鄰群體的最佳“經(jīng)驗(yàn)”在問題空間中向更好的位置“飛行”, 搜索最優(yōu)解。

假設(shè)粒子數(shù)為n, 粒子群中第i1≤i≤n個(gè)粒子的位置用向量X 表示, 第i 個(gè)粒子的速度表示為V。第i 個(gè)粒子迄今為止搜索到的最好位置記為Pb, 整個(gè)粒子群迄今位置搜索到的最好位置記為Pg。對(duì)于每一個(gè)粒子，每次迭代之后都要更新其速度和位置，以便能夠朝著更優(yōu)的位置前進(jìn)。根據(jù)如下等式變化:

v[ ]=wv[ ]+c1rand( )(pb-x[])+c2rand( )(pg[]-x[]) （11）

x[ ]=x[ ]+v[ ] （12）

其中加速常數(shù)c1、c2 是兩個(gè)非負(fù)值, 稱為加速因子; rand（ ）是[0, 1]之間的隨機(jī)數(shù); ω稱為慣性因子, ω較大適于對(duì)解空間進(jìn)行大范圍探查（exploration), ω較小適于進(jìn)行小范圍開挖（exploitation）。

算法步驟（如圖2所示）。

Step1：初始化微粒群（群體規(guī)模為m），包括隨機(jī)位置和速度；

Step2：評(píng)價(jià)每個(gè)微粒的適應(yīng)度；

Step3：對(duì)每個(gè)微粒，將其適應(yīng)值與其經(jīng)歷過的最好位置pbest 作比較，如果較好，則將其作為當(dāng)前的最好位置pbest；

Step4：對(duì)每個(gè)微粒，將其適應(yīng)值與全局所經(jīng)歷的最好位置gbest 作比較，如果較好，則重新設(shè)置gbest 的索引號(hào)；

Step5：根據(jù)公式（9）和（10）更新微粒的速度和位置；

Step6：如未達(dá)到結(jié)束條件（通常為足夠好的適應(yīng)值或達(dá)到一個(gè)預(yù)設(shè)最大跌代數(shù)itermax），則返回Step2。

粒子編碼方式及其適應(yīng)度函數(shù)的產(chǎn)生：

本文采用實(shí)數(shù)編碼方式, 將其應(yīng)用于VRP問題。對(duì)L個(gè)客戶點(diǎn)、K輛車VRP問題, 每個(gè)粒子對(duì)應(yīng)一個(gè)L+K－1維向量, 其中各元素值的大小順序表示各客戶點(diǎn)在總路徑中的配送次序。

例如: 設(shè)客戶數(shù)為8, 車輛數(shù)3, 若某粒子的位置向量X見表1。

則按照X的大小排列，得到車輛路徑的順序，結(jié)果見表2。

則該粒子對(duì)應(yīng)解的總路徑為: 0→4→5→0→3→7→1→0→2→6→8→0, 相應(yīng)的分路徑即為:

車1: 0→8→6→2→0。

車2: 0→1→7→3→0。

車3: 0→5→4→0。

適應(yīng)度函數(shù)是在產(chǎn)生的路徑的基礎(chǔ)上，按照產(chǎn)生的路徑順序，計(jì)算按此路徑行走所要耗費(fèi)的時(shí)間或成本，即為適應(yīng)度函數(shù)的值，在迭代過程中既要評(píng)價(jià)這些新粒子的適應(yīng)度是否比種群內(nèi)其他粒子或者原來的適應(yīng)度更優(yōu)，否則淘汰此粒子。

4模型求解算例

算例中存在一個(gè)配送中心和8個(gè)客戶點(diǎn)，他們之間的距離關(guān)系如表3所示，其中0點(diǎn)表示為配送中心。

各節(jié)點(diǎn)需要運(yùn)送的貨物按其密度分可以分為3類，其密度分別為0.5,1.5,2。分別表示為貨物類型A，B，C。每個(gè)節(jié)點(diǎn)需要配送的貨物量如表4所示。

算例中所使用的車輛的屬性為載重量8，車輛容積12。我們?nèi)ボ囕v的噸位利用率為0.8，容積利用率為0.75。根據(jù)公式（10）提前確定所使用的車輛數(shù)為3。

車輛提前或者延遲到達(dá)某一節(jié)點(diǎn)所接受的單位懲罰為50。這樣我們將原來模型改寫，公式（6）的約束條件被取消。轉(zhuǎn)化為目標(biāo)函數(shù)中通過懲罰函數(shù)來體現(xiàn)時(shí)間窗的限制，亦稱為軟時(shí)間窗。

下面算例采用例子群算法，算法中的各個(gè)參數(shù)如下所示：

學(xué)習(xí)因子1, c1=1.4962;

學(xué)習(xí)因子2, c2=1.4962;

慣性權(quán)重, w=0.7298;

最大迭代次數(shù), MaxDT=40;

搜索空間維數(shù)（未知數(shù)個(gè)數(shù)），D=10;

初始化群體個(gè)體數(shù)目, N=20。

經(jīng)過40次的迭代，目標(biāo)值收斂到935，其中路上所花費(fèi)的成本為900，因?yàn)檠诱`或者提前到達(dá)節(jié)點(diǎn)而接受的懲罰值為35，得到的最優(yōu)解為086701540320。這樣路徑為:

車1: 0→8→6→7→0;

車2: 0→1→5→4→0;

車3: 0→3→2→0。

5結(jié)論

本文通過對(duì)車輛路徑模型的改進(jìn)，考慮不同貨物種類對(duì)車輛路徑問題的影響，同時(shí)考慮體積和重量的限制，對(duì)有時(shí)間窗約束的車輛路徑模型進(jìn)行求解，使得模型能跟企業(yè)現(xiàn)實(shí)問題更加貼切。該模型還存在一定的改進(jìn)空間，比如可以將所需要使用的車輛類型考慮進(jìn)去。

參考文獻(xiàn)：

[1]Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959,10(6):80-91.

[2]Christofides N. Mingozzi A. Toth P. The Vehicle Routing Problem[C]//Combinational Optimization, New York' Johnly Wiley, 1979.

[3]郭耀煌. 安排城市卡車行車路線的一種新方法[J]. 系統(tǒng)工程學(xué)報(bào), 1989,4(2)：70-78.

[4]郭耀煌, 李軍. 車輛優(yōu)化調(diào)度[M]. 成都： 成都科技大學(xué)出版社, 1994.

[5]李軍, 郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京： 中國物資出版社, 2001.

[6]王征. 車輛路徑問題的知識(shí)表示及智能建模方法研究[D]. 大連： 大連理工大學(xué), 2007.

[7]Desrosiers J, Soumis F, Desrochers N. Routing with time windows by column generation[J]. Networks, 1984,14:545-546.

[8]Lapore G, Nobert Y, Desrochers M. Optimal routing under capacity and distance restrictions[J]. Operations Research, 1985,33:1050-1073.

[9]Fisher M L. Jaikumar R.A generalized assignment heuristic for vehicle routing[J]. Networks, 1981,11:109-124.

[10]Bullnheimer B, Hartl R F, Strauss C. An improved ant system algorithm for the vehicle routing[J]. Annals of Operations Reseach,1999,89:319-328.

[11]Mazzeo S, Loiseau I. An Ant Colony Algorithm for the Capacitated Vehicle Routing[J]. Electronic Note in Discrete Mathematics, 2004,18:181-186.

[12]李軍. 有時(shí)間窗的車輛路線安排問題的啟發(fā)式算法[J]. 系統(tǒng)工程, 1996,14(5)：45-50.

[13]李軍, 謝秉磊, 郭耀煌. 非滿載車輛調(diào)度問題的遺傳算法[J]. 系統(tǒng)工程理論方法應(yīng)用, 2000,9(3):235-239.

[14]李軍, 郭強(qiáng), 劉建新. 組合運(yùn)輸?shù)膬?yōu)化調(diào)度[J]. 系統(tǒng)工程理論與實(shí)踐, 2001(2):117-121.

[15]李金蘋. 現(xiàn)代物流配送系統(tǒng)的運(yùn)輸優(yōu)化調(diào)度方案[J]. 物流技術(shù), 2002(5):11-13.

[16]霍佳震, 張磊. 有時(shí)間窗集的集貨送貨一體化車輛路徑規(guī)劃啟發(fā)式算法研究[J]. 物流技術(shù), 2004(5):46-66.