多順序時段批量批次車輛調(diào)度方法研究*

吳傳良，何葉榮，王建華(淮南師范學(xué)院經(jīng)濟(jì)與管理學(xué)院，安徽淮南232038)

多順序時段批量批次車輛調(diào)度方法研究*

吳傳良，何葉榮，王建華
(淮南師范學(xué)院經(jīng)濟(jì)與管理學(xué)院，安徽淮南232038)

摘要:多順序時段批量批次的車輛調(diào)度問題就是通過對車輛進(jìn)行有計劃、科學(xué)、準(zhǔn)確的調(diào)度以達(dá)到降低物流成本的目的;首先，針對多順序時段內(nèi)變化的速度，采用線性最小二乘擬合方法將變化的速度量化;其次，在加入時間窗約束、容量約束的基礎(chǔ)之上構(gòu)建了多順序時段批量批次貨物運(yùn)輸?shù)能囕v調(diào)度的數(shù)學(xué)模型;最后，針對基本蟻群算法進(jìn)行相關(guān)改進(jìn)，并進(jìn)行了案例仿真分析。

關(guān)鍵詞:多順序時段;車輛調(diào)度;蟻群算法

運(yùn)輸是物流中一個直接與消費(fèi)者相連的環(huán)節(jié)，也是物流公司成本的重要組成部分，據(jù)中國物流與采購聯(lián)合會2011年相關(guān)統(tǒng)計數(shù)據(jù)顯示:運(yùn)輸費(fèi)用占物流費(fèi)用的53%左右。而對于車輛調(diào)度方法的研究可以均衡物流企業(yè)與消費(fèi)者之間的利益，從而實(shí)現(xiàn)物流科學(xué)化。車輛調(diào)度問題(Vehicle Scheduling Problem，VSP)是在1959年由Dantzig和Ramser提出的［1］，對車輛調(diào)度問題的理論與方法進(jìn)行系統(tǒng)研究是物流集約化發(fā)展、構(gòu)建綜合物流系統(tǒng)、建立現(xiàn)代調(diào)度指揮系統(tǒng)、發(fā)展智能交通運(yùn)輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)。車輛運(yùn)輸調(diào)度問題應(yīng)用前景廣闊，已經(jīng)廣泛用于生產(chǎn)、生活的各個方面，如報紙或貨物投遞、垃圾車路線優(yōu)化和包裹快遞等。

對于這種NP難題，多順序時段貨物運(yùn)輸?shù)能囕v調(diào)度比一般的車輛調(diào)度問題更加復(fù)雜。目前，在國內(nèi)外有很多學(xué)者在不同的的車輛調(diào)度問題上取得了一定的成果。Laporte和Nobert［2］等人探討了帶距離和容量限制的車輛優(yōu)化調(diào)度問題; Taillard等人［3］利用禁忌搜索和模擬退火算法，實(shí)現(xiàn)了求解車輛調(diào)度問題的并行化。在國內(nèi)，郎茂祥［4］對于車輛調(diào)度問題的研究可謂頗深，在其出版的《配送車輛優(yōu)化調(diào)度模型與算法》一書中，詳細(xì)闡述了當(dāng)配送車輛優(yōu)化調(diào)度的約束條件(如容量、時間窗、車型、多車場、發(fā)車時間等)不同時，其對應(yīng)的數(shù)學(xué)模型及其優(yōu)化算法。

1　多順序時段批量批次貨物車輛調(diào)度問題的描述及構(gòu)建數(shù)學(xué)模型

1.1問題的描述

研究的多順序時段批量批次貨物運(yùn)輸?shù)能囕v調(diào)度問題所涉及的約束條件主要有:交通流量(即變化的車速)、車輛容量、貨物需求量、貨物需求時間窗以及服務(wù)時間等。它可以描述為:貨物運(yùn)輸是由1個配送點(diǎn)，n個需求點(diǎn)組成，在貨物運(yùn)輸過程中，其路徑上交通流量是不斷變化的，每個需求點(diǎn)的需求量為gi，每輛車限定容量為q，每個需求點(diǎn)有時間窗要求并且服務(wù)時間已經(jīng)確定。

1.2多順序時段批量批次貨物運(yùn)輸?shù)能囕v調(diào)度的數(shù)學(xué)模型

主要通過對車輛調(diào)度約束條件的描述構(gòu)建課題的數(shù)學(xué)模型。

1.2.1多順序時段內(nèi)車輛速度的量化處理

傳統(tǒng)的車輛調(diào)度問題是基于理想狀態(tài)下進(jìn)行優(yōu)化的，在建模時忽略了每個順序時段內(nèi)的不穩(wěn)定因素，以至于現(xiàn)有多數(shù)優(yōu)化方法以及模型的建立的前提是車輛速度恒定。而每個順序時段情況不同都會對車輛速度產(chǎn)生影響，如早上班、晚下班高峰期車輛的速度較慢，據(jù)有關(guān)統(tǒng)計在北京奧運(yùn)會期間實(shí)行單雙號限行后，車流量降低27%左右，而車速也提高了相應(yīng)的比例，也就是說在貨物運(yùn)輸中配送車輛速度在一天不同時段處于動態(tài)變化并與車流量成反比。

由于動態(tài)變化的速度會增加車輛調(diào)度問題的復(fù)雜程度，擬采用將變化的速度量化并結(jié)合現(xiàn)有車輛調(diào)度算法進(jìn)行課題的研究。將變化的速度量化的步驟為:首先對配送區(qū)域內(nèi)配送需求點(diǎn)之間的路徑上的車流量進(jìn)行統(tǒng)計;然后將數(shù)據(jù)轉(zhuǎn)換為車速數(shù)據(jù)，利用曲線擬合思想并通過Matlab實(shí)現(xiàn)車輛速度與時間函數(shù)的建立;最后將變化的速度量化，主要思想是通過對局部點(diǎn)進(jìn)行逐步曲線擬合，用定積分的思想進(jìn)行求解在多順序時段內(nèi)的總路程，再除以總時間即是多順序時段內(nèi)的平均速度。公式如下:

其中n表示時間段總間隔時間，例如:8∶00－17∶00則時間間隔為11 h; t =［n/m］+ 1; m為設(shè)定的小段時間間隔; f(x)為小段時間間隔內(nèi)利用線性最小二乘法擬合出的速度關(guān)于時間的函數(shù)。

1.2.2多順序時段批量批次貨物運(yùn)輸車輛調(diào)度數(shù)學(xué)模型的建立

在建立多順序時段批量批次貨物運(yùn)輸車輛調(diào)度的數(shù)學(xué)模型之前，需要做假設(shè):配送中心和配送點(diǎn)的位置坐標(biāo)已知;配送車輛車型為同種車型，并且最大載重量已知;配送點(diǎn)需求量已知;配送點(diǎn)要求的時間窗已知;每個客戶必須只能訪問一次且必須滿足每個客戶的配送需求;配送主要路段車流量已知。

數(shù)學(xué)模型的決策變量和參數(shù)定義:配送中心編號為0，客戶點(diǎn)為1，2，…，n，車輛數(shù)為m; Dij表示各配送中心之間的距離;表示已通過上文提出的方法將變化的速度量化后的速度(常數(shù)); w1表示單位距離車輛所耗費(fèi)的成本; xijk=0或1，當(dāng)其為1時表示車輛k由客戶點(diǎn)i(或配送中心)開往客戶點(diǎn)j(或配送中心); yki=0或1，當(dāng)其為1時表示客戶點(diǎn)i的任務(wù)由車輛k完成; si為車輛在客戶點(diǎn)i的服務(wù)時間; gi為客戶點(diǎn)i的需求量;時間窗為［aj，bj］，車輛到達(dá)客戶j時間為Tj，e和f時間窗懲罰系數(shù)。

建立數(shù)學(xué)模型為［5，6］

式(3)表示車輛k所承擔(dān)的客戶總需求不大于車裝載最大容量;式(4)表示任務(wù)i只能由一輛車完成; 式(5)－(8)表示到達(dá)和離開某一客戶點(diǎn)的車輛只有一輛;式(9)和(10)表示時間窗約束;車輛數(shù)m可以根據(jù)式進(jìn)行估計，其中［］表示取整，μ為參數(shù)且在［0，1］之間表示裝卸車復(fù)雜程度以及約束多少的估計，一般μ取值為0.85。

2　多順序時段批量批次貨物車輛調(diào)度算法的設(shè)計

2.1改進(jìn)的蟻群算法［7，8］

(1)局部最優(yōu)搜索策略。蟻群算法容易出現(xiàn)早熟停滯等現(xiàn)象，即搜索過程達(dá)到一定迭代次數(shù)后，對解的空間不再進(jìn)行進(jìn)一步搜索，這樣不利于發(fā)現(xiàn)最優(yōu)解。針對這種情況，采用2－opt策略，其原理就是對每次迭代產(chǎn)生的最優(yōu)解進(jìn)行相鄰邊的交換，這樣以來更加容易尋找到最優(yōu)解。2－opt必須滿足的一個條件就是相鄰邊交換后路徑總長度減小，即:

(2)參數(shù)α的改進(jìn)。在基本蟻群算法中，蟻群在搜索的過程中很容易出現(xiàn)過早收斂和停滯現(xiàn)象，認(rèn)為在搜索過程中，由于信息素不斷累積，加強(qiáng)了局部路徑的重要性，使得蟻群過早收斂陷入局部最優(yōu)解，不再探索新的路徑。但是若使信息素啟發(fā)因子α在一定的迭代次數(shù)范圍內(nèi)是一個增函數(shù)，也就是說在迭代的過程中適當(dāng)信息素積累量是一個逐步慢慢累加的過程而不是迅速積累的過程，這樣更有利于尋找到更好的路徑。

通過上述分析提出了信息素啟發(fā)因子α與迭代次數(shù)之間的一個增函數(shù):

其中a＞1，Nc為迭代次數(shù)，n為常數(shù)。信息素啟發(fā)因子α與迭代次數(shù)函數(shù)圖形形狀(圖1):α(Nc)是一個指數(shù)函數(shù)，初始時，信息素啟發(fā)因子α較小，蟻群在逐步搜索更廣闊的區(qū)域，但隨著迭代次數(shù)的增加，信息量達(dá)到一定程度后，幾乎無法在進(jìn)行最優(yōu)解的探索，此時Nc=n，當(dāng)Nc＞n時，蟻群快速收斂。

圖1　改進(jìn)蟻群算法路徑優(yōu)化結(jié)果

2.2算法步驟

Step1:初始化參數(shù)，讀取配送中心和客戶點(diǎn)坐標(biāo)以及其他數(shù)據(jù)，另外設(shè)置全局參數(shù);

Step2:構(gòu)造時間窗懲罰函數(shù);

Step3:將m只螞蟻均勻的放在配送中心節(jié)點(diǎn)上，初始時間t=0和迭代次數(shù)Nc=0，建立禁忌表;

Step4:對于每一只螞蟻，從客戶點(diǎn)列表中尋找沒有走到的點(diǎn)，并按照改進(jìn)后的狀態(tài)轉(zhuǎn)移概率公式選擇下一個客戶節(jié)點(diǎn)j;

Step5:累加路徑(i，j)的貨運(yùn)量得到q，若q大于車輛最大載重Q，那么就跳轉(zhuǎn)到下一步;若q小于車輛最大載重Q，則將其加入可行點(diǎn)集;

Step6:生成最優(yōu)路徑并應(yīng)用2－opt方法對最優(yōu)解進(jìn)行更新;

Step7:對每只螞蟻所走過的路徑的局部信息素和信息素增量進(jìn)行更新;

Step8:如果迭代次數(shù)達(dá)到最大或者找到全局最優(yōu)路徑，程序結(jié)束，否則，清空禁忌表，返回步驟4，并且重復(fù)上述步驟。

3　仿真分析

以上通過詳細(xì)分析，構(gòu)建了多順序時段批量批次貨物運(yùn)輸?shù)臄?shù)學(xué)模型，并設(shè)計出一種新的蟻群算法。現(xiàn)將運(yùn)用以上介紹的知識進(jìn)行案例仿真。仿真數(shù)據(jù)由Matlab 7.0軟件隨機(jī)生成。

3.1量化變化的速度

物流配送時間段一般在早7:00－18:00，在進(jìn)行車流量統(tǒng)計之前，需要制定相關(guān)表格，并且確定車流量統(tǒng)計時間間隔，借助Matlab隨機(jī)生成以下數(shù)據(jù)，時間間隔確定為30 min，具體數(shù)據(jù)見表1。

首先將上述22個時間段分成7個時間段，對這六類時間段逐一進(jìn)行線性最小二乘擬合。

通過直觀判斷可以假設(shè)每一類的函數(shù)都滿足于g(x) = a+bx2，下面就以第一類數(shù)據(jù)為例，通過Matlab 7.0編程得到第一類順序時段速度與時間的函數(shù)為

將程序中數(shù)據(jù)改變得到其他幾類函數(shù)分別為

通過求解得到V =40.06。將不探討車輛在特殊順序時段內(nèi)的配送，故路徑優(yōu)化時速度取值為V =40。

3.2配送路徑生成

通過Matlab隨機(jī)生成客戶點(diǎn)坐標(biāo)以及客戶點(diǎn)服務(wù)時間及時間窗要求，假設(shè)車輛最大載重量為4 t，詳見表2。利用MATLAB 7.6.0語言工具實(shí)現(xiàn)編程，各參數(shù)設(shè)置為:γ= 5，m = 15，ρ= 0.5，Q = 100，NC = 200，W = 4 000。隨機(jī)運(yùn)行10次，運(yùn)行結(jié)果見表3:

表1　多順序時段車流量

表2　各配送區(qū)域點(diǎn)的坐標(biāo)位置、貨物的需求量及服務(wù)時間

表3　改進(jìn)蟻群算法計算結(jié)果

表3中大多數(shù)目標(biāo)函數(shù)值都是相同數(shù)值，則利用改進(jìn)后蟻群算法求得的最優(yōu)解為386.27，路徑如圖1所示。

車輛1－6改進(jìn)蟻群算法下的最優(yōu)路徑依次為:0-14-9-2; 0-18-8-11-0; 0-6-17-7-0; 0-12-15-4; 0-1-15-13; 0-3-16-10。改進(jìn)后的蟻群算法較平穩(wěn)，不容易陷入局部最優(yōu)解，且收斂速度相對于基本蟻群算法并沒有放慢許多。

4　結(jié)語

主要研究多順序時段批量批次貨物運(yùn)輸?shù)能囕v調(diào)度問題。首先，借助于線性最小二乘擬合思想以及相關(guān)數(shù)學(xué)知識并結(jié)合matlab編程對多順序時段內(nèi)變化的速度進(jìn)行了量化。其次，通過建立時間窗懲罰函數(shù)將時間成本量化，在滿足客戶需求點(diǎn)的需求量大小及時間窗等約束條件的前提下，構(gòu)建了多順序時段批量批次貨物運(yùn)輸?shù)能囕v調(diào)度的數(shù)學(xué)模型。最后，針對車輛調(diào)度實(shí)際問題進(jìn)行了蟻群算法的改進(jìn)，通過仿真分析，改進(jìn)后的蟻群算法收斂速度平穩(wěn)，且容易尋找到最優(yōu)解。

目前，對于車輛問題的研究仍處于探索階段，故研究工作尚存在不足，例如:車輛調(diào)度問題不僅僅是車輛路徑的優(yōu)化，其包括貨物配裝、人員安排等，現(xiàn)只研究了車輛路徑的優(yōu)化;同時，將多順序時段內(nèi)不斷變化速度量化并不是最好的優(yōu)化思想，而應(yīng)建立一種隨時間變化而變化的速度模型，這更有利于尋找到最優(yōu)路徑。

參考文獻(xiàn):

［1］DANTZIT G B，RAMSER R H.The Truck Dispatching Problem［J］.Management Science，1959(4):1128-1131

［2］LAPORTE G，NOBERT Y，DESROEHERS M.Optimal Routing with Capacity and Distance Restrictions［J］.Operations Research，1985(4):1050-1073

［3］TAILLARD E.Parallel Interactive Search Method for Vehicle Routing Problem［J］.Networks，1993，23:661-673

［4］郎茂祥.配送車輛優(yōu)化調(diào)度模型與算法［M］.北京:電子工業(yè)出版社，2009

［5］李琳，劉士新，唐加福.改進(jìn)的蟻群算法求解帶時間窗的車輛路徑問題［J］.控制與決策，2010，25(9):1379-1382

［6］李秀娟，楊玥.蟻群優(yōu)化算法在物流車輛調(diào)度系統(tǒng)中的應(yīng)用［J］.計算機(jī)工程與應(yīng)用，2013，33(10):2822-2826

［7］吳潔明.物流配送車輛路徑優(yōu)化問題的仿真研究［J］.計算機(jī)仿真，2011，28(7):357-360

［8］潘斌斌.多目標(biāo)路徑規(guī)劃問題的算法綜述［J］.重慶工商大學(xué)學(xué)報:自然科學(xué)版，2012，29(5):78-81

Research on the Vehicle Scheduling Method with
Multiple Sequential Time and Batch

WU Chuan-liang1，HE Ye-rong1，WANG Jian-hua1
(School of Economic and Management，Huainan Normal University，Huainan 232038，China)

Abstract:Through plan，scientific and accurate scheduling，scheduling vehicle with multiple sequential time and batch is to achieve the purpose of reducing logistics cost.Firstly，according to multiple sequential period change speed，this paper adopts the linear least squares method to change speed quantization.Secondly，adding time window constraints，capacity constraint，this paper construct good vehicle scheduling model of smultiple sequential time and batch.Finally，according to the basic ant algorithm，the model is improved and simulated.

Key words:multiple sequential time; vehicle scheduling; ant algorithm

中圖分類號:C931

文獻(xiàn)標(biāo)識碼:A

文章編號:1672－058X(2015) 08－0038－06

doi:10.16055/j.issn.1672－058X.2015.0008.009

收稿日期:2014－10－26;修回日期:2014－12－10.

*基金項目:國家自然科學(xué)基金資助(51374114).

作者簡介:吳傳良(1989-)，男，安徽六安人，碩士，從事物流與供應(yīng)鏈管理研究.