基于快遞業(yè)物流的優(yōu)化調(diào)度問題研究

劉艷秋，郭長(zhǎng)亮

摘 要：現(xiàn)代化物流分支廣泛，本文針對(duì)現(xiàn)代化物流業(yè)中的快遞業(yè)物流優(yōu)化調(diào)度問題，建立了為使任務(wù)成本最小的優(yōu)化模型，根據(jù)快遞業(yè)物流特點(diǎn)，基于遺傳算法利用其中。利用真實(shí)的用例來驗(yàn)證遺傳算法在快遞業(yè)物流調(diào)度中的可行性。

關(guān)鍵詞：快遞業(yè)；優(yōu)化模型；遺傳算法

0 引言

快遞業(yè)作為現(xiàn)代物流業(yè)的一個(gè)分支，在電子商務(wù)市場(chǎng)的發(fā)展下，快遞業(yè)物流也得到迅猛發(fā)展。車輛調(diào)度問題（Vehicle scheduling Problem，簡(jiǎn)稱VSP）作為物流業(yè)的核心問題，各個(gè)領(lǐng)域?qū)＜覍W(xué)者提出了不同的研究方案[1，2]。上個(gè)世紀(jì)中葉，Dantzing和Ramser最早提出了商旅問題[3]，標(biāo)志著VSP理論的正式成立。本文從物流業(yè)特點(diǎn)出發(fā)，從快遞業(yè)物流配送物件相對(duì)較小，快遞員（配送人員）能力限制，及客戶點(diǎn)分散等的綜合現(xiàn)狀下分析，找到最優(yōu)的調(diào)度方案。

VSP問題屬于NP-hard問題，在規(guī)模較小的情況下可以使用精確算法求出最優(yōu)解[4]，而啟發(fā)算法則在較大的規(guī)模下有著非常重要的作用[5，6]。目前大量使用的智能算法有模擬退火算法、禁忌搜索算法、蟻群算法等智能優(yōu)化算法，考慮到實(shí)際和本文的模型特點(diǎn)，采用遺傳算法對(duì)問題進(jìn)行求解。

1 問題描述和數(shù)學(xué)模型的確立

快遞業(yè)車輛調(diào)度問題可描述為：有N個(gè)客戶點(diǎn)，并且每個(gè)客戶點(diǎn)的配送量及位置已知，快遞員k從快遞站點(diǎn)出發(fā)到達(dá)這批客戶點(diǎn)?？爝f員在配送任務(wù)完成后，返回快遞站點(diǎn)。在選擇和確定實(shí)際配送路線和完成配送貨任務(wù)過程中，使得總費(fèi)用最小。

用1，2，3，…，M表示快遞員的編號(hào)，令m={1，2，3，…，M}； R表示m的行駛速度，設(shè)為一常值；設(shè)每個(gè)快遞物件重量大小為1（由于快遞物件重量相對(duì)較?。?；Nmax表示為快遞員在一次配送任務(wù)的最大工作量（件數(shù)）；eij表示客戶點(diǎn)i與j之間所需的行駛成本（指距離，費(fèi)用之和等）；設(shè)行駛單位距離成本為q，設(shè)q為1，eij與客戶i到客戶j的行駛的距離dij成線性關(guān)系；p0表示快遞員配送快遞物件的每件提成，為固定值。

設(shè)決策變量為：x■■=1 快遞員m從i離開后前往j0 否則；

模型描述為： min■■■e■+p■x■■ （1）

st.■■x■■=1，i=1，…，N，j≠i （2）

■■x■■=1，j=1，…，N，i≠j （3）

■x■■■x■■=1，m=1，…，M，i=0 （4）

■x■■≤N■，m=1，…，M，j=1，…，N （5）

e■=qd■=d■ i，j=0，1，…，N （6）

x■■∈0，1 i，j=0，1，…，N， i≠j （7）

式（1）表示目標(biāo)函數(shù)，即最小任務(wù)成本。

式（2）（3）確保每個(gè)客戶只能被一位快遞員服務(wù)一次。

式（4）確保所有的快遞員都從快遞站點(diǎn)出發(fā)且最終都返回快遞站點(diǎn)。

式（5）確保每次快遞員的任務(wù)量不超過快遞員的最大工作承受能力，即快遞員容量限制為Nmax。

式（6）i，j之間行駛成本計(jì)算說明。

式（7）確保決策變量為0～1的決策變量。

2 模型求解

快遞業(yè)車輛調(diào)度問題：有N個(gè)客戶點(diǎn)，并且每個(gè)客戶點(diǎn)位置及配送量已知，有M個(gè)快遞員，快遞員從快遞站點(diǎn)出發(fā)，配送完貨物后回到快遞站點(diǎn)，由于快遞員最大工作能力限制，所以每次任務(wù)快遞員配送貨物有限。

本文屬于NP-hard問題，遺傳算法[7]對(duì)上文模型求解具有良好的特性。Malmborg[8]、Baker Barrie[9]等人在遺傳算法應(yīng)用于車輛調(diào)度問題進(jìn)行了研究。本文也采用遺傳算法對(duì)上述模型進(jìn)行求解。具體內(nèi)容如下：

2.1 染色體編碼

染色體結(jié)構(gòu)的設(shè)計(jì)對(duì)遺傳算法是至關(guān)重要的，本文的染色體編碼由三部分組成。第一部分是快遞員編號(hào)，第二部分為客戶點(diǎn)編號(hào)，第三部分為快遞站點(diǎn)編號(hào)（設(shè)置為0）。

例如本文中染色體的S結(jié)構(gòu)可表示為：

S：（1415202360）

表示：編號(hào)為1的快遞員從快遞站點(diǎn)出發(fā)，經(jīng)過的路徑為客戶點(diǎn)4→客戶點(diǎn)1→客戶點(diǎn)5→客戶點(diǎn)2→快遞站點(diǎn)0；編號(hào)為2的快遞員從快遞站點(diǎn)出發(fā)，經(jīng)過的路徑為客戶點(diǎn)3→客戶點(diǎn)6→快遞站點(diǎn)0。使用的快遞員數(shù)為2個(gè)。

2.2 種群初始化

初始種群包括多條染色體，每條染色體中客戶點(diǎn)的順序隨機(jī)打亂，再根據(jù)快遞員能力限制插入快遞員編號(hào)。染色體長(zhǎng)度是根據(jù)客戶點(diǎn)是由使用的快遞員數(shù)和客戶點(diǎn)數(shù)決定的。

2.3 選擇

本文采用輪盤賭（roulette wheel）的方法，依照適應(yīng)度函數(shù)值，從群里中找到比較適應(yīng)環(huán)境的個(gè)體。

2.4 交叉

根據(jù)適當(dāng)?shù)慕徊媛蔬x擇選擇出需要交叉的種群， 為了說明交叉過程，示例如下：

任意選出兩個(gè)父體

1→4→1→5→2→0→2→3→6→0

1→3→2→5→1→0→2→6→4→0

經(jīng)過交叉，互換兩個(gè)基因段，去掉快遞員編號(hào)和快遞站點(diǎn)編號(hào)，得到兩個(gè)子體為

6→1→5→2→2→6

3→3→5→1→4→4

按照這種交叉的操作方法，一條染色體中會(huì)出現(xiàn)相同的基因，那么就要把沒有進(jìn)行交換操作的基因段的重復(fù)基因與另外一條染色體按順序進(jìn)行交換，可得到

6→1→5→3→2→4

2→3→5→1→4→6

根據(jù)快遞員能力約束，隨機(jī)插入快遞員編號(hào)及快遞站點(diǎn)編號(hào)，可得到

1→6→1→5→3→0→2→2→4→0

1→2→3→5→0→2→1→4→6→0

2.5 變異

按照生物進(jìn)化理論，在繁殖過程中，基因會(huì)發(fā)生一定概率的出錯(cuò)，本文的變異操作過程是隨機(jī)選取兩個(gè)客戶點(diǎn)交換位置，加入判斷，比較與前代染色體的適應(yīng)度，改良則保留，否則舍棄，一直循環(huán)下去，知道產(chǎn)生所能達(dá)到最好的染色體為止。

2.6 適應(yīng)度的運(yùn)算

由遺傳算法得到的每條染色體，本文的適應(yīng)度函數(shù)取總目標(biāo)值。

■■■e■+p■x■■

從上式適應(yīng)函數(shù)可以看出，當(dāng)適應(yīng)函數(shù)值越低，則染色體越優(yōu)。

3 算例

假設(shè)某一快遞站點(diǎn)有3個(gè)快遞員，每個(gè)快遞員一次任務(wù)最大工作能力為10件貨物，在某一時(shí)刻有16個(gè)需要服務(wù)的客戶點(diǎn)，客戶點(diǎn)之間的距離分別如下面的表1所示。要求安排快遞員行駛路線使總費(fèi)用最小。

對(duì)優(yōu)化目標(biāo)應(yīng)用本文的方案進(jìn)行求解，可得行駛路線具體如下：

編號(hào)為1的快遞員：2→1→6→11→16→7→0

編號(hào)為2的快遞員：5→9→10→14→15→0

編號(hào)為3的快遞員：4→8→12→13→3→0

最終求得最小花費(fèi)（目標(biāo)函數(shù)值）Bestfitness=615

4 結(jié)論

本文對(duì)快遞業(yè)調(diào)度優(yōu)化問題進(jìn)行了描述，為了求解該問題，找到適合本文問題的啟發(fā)算法-遺傳算法，該算法直觀、簡(jiǎn)便、易操作。利用遺傳算法求出配送成本最小的路徑。本文的設(shè)計(jì)思想更貼合實(shí)際生活中快遞業(yè)調(diào)度問題，此模型可以靈活運(yùn)用到實(shí)際問題中去。

參考文獻(xiàn)：

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

[2]王海濱，孫永道，等.多車場(chǎng)多目標(biāo)開放式物流配送車輛調(diào)度問題的研究[A].計(jì)算機(jī)測(cè)量與控制.2010.18（12）.

[3]Dantizig G，Ramser J. .The truck dispatching proble[J].Management Science，1959，6：80～91.

[4]Toth P， Vigo D. Exact Solution of the Vehicle Routing Problem[M]. In Fleet Management and Logistics. Dordrecht： Kluwer， 1998.1-31.

[5]Laporte G. The vehicle routing problem： An overview of exact and approximate algorithms[J]. European Journal of Operational Research， 1992，59：345-358.

[6]Laporte G， Gendreau M，Potvin J Y， et al.Classical and moderm heuristicsfor the vehicle routing problem[J]. International Transactions in Operational Research， 2000，7：285-300.

[7]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，1999.

[8]Malmborg，Charles.Genetic algorithm for service level based vehicle scheduling[J].European Journal of Operational Research， 1996，93（1）：121-134.

[9] Baker Barrie M， Ayechew M A. Agenetic algorithm for the vehicle routing problem[J]. Computer & Operations research， 2003，30：787-800.

基金項(xiàng)目：遼寧省科學(xué)技術(shù)計(jì)劃項(xiàng)目（2013216015）；沈陽(yáng)市科學(xué)技術(shù)計(jì)劃項(xiàng)目