基于客運站小件快運背景下的車輛配載調(diào)度問題

夏躍華

(甘肅民族師范學(xué)院 數(shù)學(xué)系，甘肅 合作 747000)

?

基于客運站小件快運背景下的車輛配載調(diào)度問題

夏躍華

(甘肅民族師范學(xué)院 數(shù)學(xué)系，甘肅 合作 747000)

指出了車輛配載調(diào)度環(huán)節(jié)是一個物流配送中心配送過程中的關(guān)鍵環(huán)節(jié)，為提高其運作效率，對客運站小件快運業(yè)務(wù)的車輛配載調(diào)度環(huán)節(jié)進行了研究。在貨物可以轉(zhuǎn)運的條件下，為達到貨物處理總時間最短的目標，建立了車輛配載調(diào)度優(yōu)化模型，然后通過改進的遺傳算法求解，通過算例證明：該方法可以解決客運站小件快運業(yè)務(wù)中復(fù)雜的調(diào)度問題，可為決策者提供有效的決策策略。

小件快運； 車輛配載； 車輛調(diào)度； 遺傳算法

1　引言

客運站小件快運業(yè)務(wù)與其他物流方式相比，客運小件快運不需要投入大量資金，能充分利用客車底艙的閑置空間，因而具有成本低、價格實惠的優(yōu)勢。同時，由于其依托于我國發(fā)達的優(yōu)質(zhì)公路網(wǎng)絡(luò)以及密集、快速、準確的車輛發(fā)班優(yōu)勢，又具有更高的時效性，在物流業(yè)競爭中具有較大的優(yōu)勢。然而在實際的小件快運業(yè)務(wù)開展過程中，常常由于客運企業(yè)粗放的管理和運行方式造成其服務(wù)水平的下降和優(yōu)勢的喪失，這在快件業(yè)務(wù)量增大時有所體現(xiàn)。

對于客運站小件快運來講，改善運作方式，優(yōu)化車輛配載及調(diào)度，將現(xiàn)代化的科學(xué)管理技術(shù)應(yīng)用于快件的配送過程，將使其不僅在目前能夠更加充分發(fā)揮其競爭優(yōu)勢，而且可以在快件處理量增大時更能夠提高其服務(wù)水平及作業(yè)效率，在激烈的競爭中獲得更好的發(fā)展。目前對客運站小件快運的配送調(diào)度問題的研究幾乎是空白，所以對該問題的研究具有較大的現(xiàn)實意義。

無論是單純的車輛調(diào)度問題，還是車輛配載調(diào)度問題，目前的研究多局限于傳統(tǒng)物流配送過程[1-5]。客運站的小件快運業(yè)務(wù)又與傳統(tǒng)物流配送中心的業(yè)務(wù)有很大的區(qū)別，它主要利用客車行李艙閑置空間來運送小件貨物，受限制于行李艙的空間和客車的載重能力，小件快運運輸?shù)呢浳锿ǔｓw積較小重量較輕，是一種類似于快遞的業(yè)務(wù)。

筆者在前人研究的基礎(chǔ)上，進一步探討了新興的客運站小件快運業(yè)務(wù)背景下的車輛配載調(diào)度問題，著眼于客運站小件快運與傳統(tǒng)物流配送的不同之處，提出了更加適用于小件快運的模型，為解決其運作效率低的問題提供了更加有效的方法。

2　模型建立

2.1問題描述

在客運小件快運問題中，一個客戶會把貨物放在一個客運站，所以客運站小件快運背景下的車輛調(diào)度問題首先可以看作是只有一個配送中心，即單車場車輛調(diào)度問題。同時，為提高快件運送效率，本文擬將周圍其它客運站作為貨物中轉(zhuǎn)站考慮，在貨物運輸時既可以選擇直達線路又可以選擇中轉(zhuǎn)線路，加快貨物運出速度。同時，客運站小件快運運輸?shù)呢浳锞鶠樾〖?，每件貨物的體積及重量遠小于客車底艙的容積和車輛的剩余載重量，所以該問題可以看作是非滿載的車輛調(diào)度問題。另外，對于客運站小件快運問題，考慮的是貨物從一個客運站到另一客運站的過程，可以理解為是車輛不返回的車輛調(diào)度問題。根據(jù)客運站實際情況來看，長途客車類型分為大型車，中型車和小型車，不同車型底艙容量限制不同，同時由于底艙被占用程度不同，車上人數(shù)不同，車輛的剩余容量及剩余載重能力均不相同，所以可以將其理解為多車型的車輛配載問題。本文在研究車輛配載時既考慮了行李艙容積約束，又考慮了車輛載重約束，所以屬于二維車輛配載問題。

在設(shè)計優(yōu)化模型之前，必須有明確的目標?？瓦\站小件快運背景下的車輛配載調(diào)度問題與傳統(tǒng)的車輛配載問題又有區(qū)別：首先客運站車輛路徑是點對點，而不是一輛車依次經(jīng)過一些點；其次是客運站車輛為每班車必須發(fā)出，車輛成本已經(jīng)由車票收入承擔，所以本文將車輛配載調(diào)度的目標設(shè)定為快件運輸總時間最短，由此客運站小件快運可以充分利用資源發(fā)揮其時效性方面的優(yōu)勢。為了使資源更合理配置，本文引入貨物的時效等級概念，將快件分為急件，普通件和慢件，不同時效要求等級的貨物區(qū)別對待 ，按等級處理快件，在目標函數(shù)中加入時效等級乘數(shù)。本文為了使問題研究思路更加清晰，將問題簡化為貨物只有一個目的地的情形來處理。

2.2模型設(shè)計

模型所涉及符號定義如下：

m表示車輛編號；m=1,2,3，…,M；

n表示貨物編號；n=1,2,3,…,N；

tm表示車輛m達到目的地所需時間；

Gm表示車輛m的額定載重量；

Vm表示車輛m行李艙的額定容積；

gn表示貨物n的重量；

Vn表示貨物n的體積。

2.3模型構(gòu)建

根據(jù)前文描述建立總配送時間最短優(yōu)化模型如下：

f(x)=minφ(x)

(1)

(2)

(3)

(4)

(5)

xmn=0或1

(6)

目標函數(shù)(1)式表示所有快件的總處理時間最短，(2)式表示所有快件總處理時間的計算過程，約束條件(3)式表示所有快件都要被運輸并且每個快件只能被運輸一次，(4)式表示每輛車所裝載的貨物重量不得超過車輛載重，(5)式表示每輛車所裝載的貨物體積不得超過車輛行李箱體積，(6)式表示決策變量0-1取值約束。

3　算法設(shè)計與實現(xiàn)

車輛配載和車輛調(diào)度問題均屬于NP-hard問題，本文所研究的客運站小件快運背景下的車輛配載調(diào)度問題結(jié)合了車輛配載和貨物運輸路線選擇的過程，是一個復(fù)雜的組合優(yōu)化問題，精確算法難以求解，所以本文采用啟發(fā)式算法進行求解，元啟發(fā)式算法是啟發(fā)式算法的一個分支，包括如模擬退火算法，蟻群算法，禁忌搜索算法和遺傳算法等，此類算法通常可以一較高的效率給出一個問題接近于最優(yōu)解的交友街。元啟發(fā)算法中的蟻群算法[6,7]工作原理簡單，且已經(jīng)在較多的復(fù)雜規(guī)劃問題上顯示除了較好的性能，本文將利用遺傳算法的主要思路并結(jié)合問題的實際情況進行一定程度的改進，對客運站小件快運車輛配載調(diào)度模型進行求解。

3.1算法實現(xiàn)過程

遺傳算法的整體結(jié)構(gòu)主要包括以下幾部分內(nèi)容：編碼、初始種群、適應(yīng)度、選擇、交叉、變異。見圖1。

圖1　遺傳算法流程

3.1.1編碼設(shè)計

結(jié)合客運站車輛配載調(diào)度的實際情況，本文提出一種新的染色體編碼方式，染色體中的每一位基因表示每個貨物將要裝載的車輛，染色體長度為貨物數(shù)量，基因數(shù)字為車輛的編號。比如一個長度為10的染色體[1132431233]，其意義為第1、2、7個貨物裝入一號車；3、6、9、10號貨物裝入3號車，以此類推。

3.1.2建立初始種群

按上述編碼規(guī)則隨機生成符合問題約束要求的一個初始種群，記作E0={e1,e2,e3,…,eL}。同時，需要確定初始種群大小，本文根據(jù)實際算例復(fù)雜程度，在100-1000種群數(shù)量中選取多個種群數(shù)量進行試算，最終選擇種群數(shù)量為300。

3.1.3計算適應(yīng)度

本文將目標函數(shù)值作為適應(yīng)度值，對染色體性能優(yōu)劣程度的評價指標為適應(yīng)度值越小染色體性能越好。同時，如果種群中出現(xiàn)不可行解，則使其適應(yīng)度值等于一個極大的整數(shù)，使算法可以自動排除掉該解。

3.1.4設(shè)定停止要求

遺傳算法是一個循環(huán)迭代的過程，需要一個停止條件。通常采用的算法停止條件為最大迭代次數(shù)，經(jīng)過多次計算，發(fā)現(xiàn)算法在300代左右已趨于成熟，不再有進化趨勢，故設(shè)定最大迭代次數(shù)500次作為算法停止條件。

3.1.5遺傳算子設(shè)計

(1)保留精英個體。本文選取種群中一定數(shù)量的適應(yīng)度值最小性能最優(yōu)個體，替換掉經(jīng)過交叉和遺傳操作生成的新一代種群中適應(yīng)度值最高即性能最差的個體，以此來使最優(yōu)的染色體得以保留，不會被選擇，交叉和變異的過程破壞。

(2)選擇算子。本文采取輪盤賭法選擇參與遺傳的個體，該方法是依概率進行有放回抽樣選出下一代種群，適應(yīng)度值越低性能越好的個體被選中的概率越高，這種方法使得性能更好的基因更多的保留到下一代種群中。

(3)交叉算子。本文采用多點交叉的方法，并使用了能夠根據(jù)基因適應(yīng)度性能變化交叉概率的交叉算子設(shè)計，優(yōu)劣不同的基因有不同的交叉概率，該方法可以使優(yōu)秀基因得到更多的保留，同時保持種群的多樣性。

(4)變異算子。本文采用基本位變異的方法，依據(jù)變異概率選擇染色體上的某些基因進行變異運算，同樣使用了能夠根據(jù)基因適應(yīng)度性能變化變異概率的交叉算子設(shè)計保留優(yōu)秀基因。

3.2算法程序?qū)崿F(xiàn)

集合GATBX遺傳算法工具箱，通過MATLAB編程實現(xiàn)該問題的遺傳算法程序。本文所編寫的遺傳算法程序共分為7個部分，分別形成各自的m文件，各部分內(nèi)容如下。

(1)建立初始種群部分。該部分通過隨機數(shù)生成函數(shù)產(chǎn)生初始種群，并計算初始種群中的個體是否滿足約束條件，對于不滿足條件的解重新生成。

(2)解碼器部分。該部分完成對染色體的解碼工作，將染色體表示為車輛搭載貨物的情況，已進行目標函數(shù)值的計算、載重及容積約束的計算以及最終結(jié)果的顯示。

(3)時間計算部分。該部分用于計算每條染色體對應(yīng)的可行解的貨物運輸總時間。

(4)目標函數(shù)計算部分。該部分調(diào)用解碼器m文件解碼染色體，將解碼后的染色體調(diào)用時間m文件計算總時間。

(5)交叉算子部分。該部分用于執(zhí)行自適應(yīng)交叉操作。

(6)變異算子部分。該部分用于執(zhí)行自適應(yīng)變異操作。

(7)主函數(shù)部分。該部分調(diào)用建立初始種群部分、目標函數(shù)計算部分、交叉算子部分、變異算子部分、解碼器部分以及GATBX工具箱完成整個遺傳算法計算過程并輸出最終結(jié)果，畫出目標函數(shù)變化跟蹤圖。

4　算例分析

4.1算例介紹

本文研究的是客運站小件快運背景下的車輛配載調(diào)度問題，根據(jù)前文建立的車輛配載調(diào)度問題模型，建立如下算例進行計算。

假設(shè)有一批到達同一目的地的貨物，貨物數(shù)量為50個，客運站到達目的地共有4條線路，有5輛車可供裝載，其中前四輛為當前即將發(fā)出班次，第五輛為第一條路線的下一班次，故在計算第五輛車運輸時間時加入了到下一班次的等待時間。每件貨物的體積、重量及時效等級如表1所示；車輛的載重、容積、所在線路運輸時間以及屬性如表2所示。

表1　貨物情況一覽

表2　車輛情況一覽

4.2結(jié)果分析

本實驗參數(shù)設(shè)置為：種群大小為300；自適應(yīng)變異概率Pm為0.01和0.02，最大迭代次數(shù)為500次。實驗輸出結(jié)果為車輛裝載方案，如圖2所示，貨物處理總時間變化跟蹤圖，如圖3所示。

圖2　客車貨物裝載方案

圖3　貨物處理總時間變化跟蹤

從圖中的實驗結(jié)果可以看出：整個運算過程中，模型目標函數(shù)，即總處理時間呈下降趨勢，并最終趨于收斂，說明算法起到了優(yōu)化的作用并給出了較優(yōu)的解，最終結(jié)果的貨物總處理時間為5525 min。從圖2中可以看出5號車并未使用，算法通過優(yōu)化配置資源，用四輛車完成任務(wù)。該算例證明了算法的正確性和有效性。

[1]高鵬,董翰強,張子泰.對小件快運的再認識[J].交通標準化,2011(1):189～192.

[2]王煉.道路快件貨物運輸研究[D].西安：長安大學(xué),2006.

[3]曾維嶺.道路客運企業(yè)小件快運業(yè)務(wù)發(fā)展策略[J].交通企業(yè)管理,2012(3):60～61.

[4]屈穎,袁燕霞.公路行包快運的發(fā)展對策[J].物流科技,2010(7):116～119.

[5]程華.北京公路長途客運站小件貨物快運研究[D].北京：北京交通大學(xué),2013.

[6]周昕,凌興宏.遺傳算法理論及技術(shù)研究綜述[J].計算機與信息技術(shù),2010(4):37～39.

[7]曾文飛,張英杰,顏玲.遺傳算法的基本原理及其應(yīng)用研究[J].軟件導(dǎo)刊,2009:54～56.

Analysis on Vehicle Assembling and Scheduling Based on the Background of Small Goods Expressin Passenger Station

Xia Yuehua

(DepartmentofMathematics,GansuNormalUniversityforNationalities,Hezuo,Gansu747000，China)

Vehicle assembling and scheduling plays a key role during distribution process in a distribution center. To improve the operating efficiency, this paper studied the vehicle assembling and scheduling ofsmall goods expressinpassenger station. The small goods express in passenger station involved two aspects. One aspect is the optimum combination of vehicle cargo assembling problem.The other is the optimal choice of vehicle route. These two aspects are interrelating. This paper discussed the problem supposing one passenger station, one destination and a number of routes. Under the condition that the goods can be transported, in order to achieve the lowest cost and time targets, vehicle assembling and scheduling optimization modelwas established, and theproblem would besolved by improved genetic algorithm. Finally, through examples to prove that the method could solve the complex passenger station vehicleassembling and scheduling problem. Meanwhile,we hoped it would provide effective strategies for policy makers.

small goodsexpress;vehicle assembling;vehicle scheduling;genetic algorithm

2016-05-31

夏躍華(1981—)，男，講師，主要從事運籌學(xué)方面的教學(xué)工作。

U492

A

1674-9944(2016)14-0256-04