基于快遞業物流的優化調度問題研究

劉艷秋，郭長亮

摘 要：現代化物流分支廣泛，本文針對現代化物流業中的快遞業物流優化調度問題，建立了為使任務成本最小的優化模型，根據快遞業物流特點，基于遺傳算法利用其中。利用真實的用例來驗證遺傳算法在快遞業物流調度中的可行性。

關鍵詞：快遞業；優化模型；遺傳算法

0 引言

快遞業作為現代物流業的一個分支，在電子商務市場的發展下，快遞業物流也得到迅猛發展。車輛調度問題（Vehicle scheduling Problem，簡稱VSP）作為物流業的核心問題，各個領域專家學者提出了不同的研究方案[1，2]。上個世紀中葉，Dantzing和Ramser最早提出了商旅問題[3]，標志著VSP理論的正式成立。本文從物流業特點出發，從快遞業物流配送物件相對較小，快遞員（配送人員）能力限制，及客戶點分散等的綜合現狀下分析，找到最優的調度方案。

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

1 問題描述和數學模型的確立

快遞業車輛調度問題可描述為：有N個客戶點，并且每個客戶點的配送量及位置已知，快遞員k從快遞站點出發到達這批客戶點。快遞員在配送任務完成后，返回快遞站點。在選擇和確定實際配送路線和完成配送貨任務過程中，使得總費用最小。

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

設決策變量為：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）表示目標函數，即最小任務成本。

式（2）（3）確保每個客戶只能被一位快遞員服務一次。

式（4）確保所有的快遞員都從快遞站點出發且最終都返回快遞站點。

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

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

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

2 模型求解

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

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

2.1 染色體編碼

染色體結構的設計對遺傳算法是至關重要的，本文的染色體編碼由三部分組成。第一部分是快遞員編號，第二部分為客戶點編號，第三部分為快遞站點編號（設置為0）。

例如本文中染色體的S結構可表示為：

S：（1415202360）

表示：編號為1的快遞員從快遞站點出發，經過的路徑為客戶點4→客戶點1→客戶點5→客戶點2→快遞站點0；編號為2的快遞員從快遞站點出發，經過的路徑為客戶點3→客戶點6→快遞站點0。使用的快遞員數為2個。

2.2 種群初始化

初始種群包括多條染色體，每條染色體中客戶點的順序隨機打亂，再根據快遞員能力限制插入快遞員編號。染色體長度是根據客戶點是由使用的快遞員數和客戶點數決定的。

2.3 選擇

本文采用輪盤賭（roulette wheel）的方法，依照適應度函數值，從群里中找到比較適應環境的個體。

2.4 交叉

根據適當的交叉率選擇選擇出需要交叉的種群， 為了說明交叉過程，示例如下：

任意選出兩個父體

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

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

經過交叉，互換兩個基因段，去掉快遞員編號和快遞站點編號，得到兩個子體為

6→1→5→2→2→6

3→3→5→1→4→4

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

6→1→5→3→2→4

2→3→5→1→4→6

根據快遞員能力約束，隨機插入快遞員編號及快遞站點編號，可得到

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

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

2.5 變異

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

2.6 適應度的運算

由遺傳算法得到的每條染色體，本文的適應度函數取總目標值。

■■■e■+p■x■■

從上式適應函數可以看出，當適應函數值越低，則染色體越優。

3 算例

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

對優化目標應用本文的方案進行求解，可得行駛路線具體如下：

編號為1的快遞員：2→1→6→11→16→7→0

編號為2的快遞員：5→9→10→14→15→0

編號為3的快遞員：4→8→12→13→3→0

最終求得最小花費（目標函數值）Bestfitness=615

4 結論

本文對快遞業調度優化問題進行了描述，為了求解該問題，找到適合本文問題的啟發算法-遺傳算法，該算法直觀、簡便、易操作。利用遺傳算法求出配送成本最小的路徑。本文的設計思想更貼合實際生活中快遞業調度問題，此模型可以靈活運用到實際問題中去。

參考文獻：

[1]李軍，郭耀煌. 物流配送車輛優化調度理論與方法[M].北京： 中國物資出版社，2001.

[2]王海濱，孫永道，等.多車場多目標開放式物流配送車輛調度問題的研究[A].計算機測量與控制.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]周明，孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社，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.

基金項目：遼寧省科學技術計劃項目（2013216015）；沈陽市科學技術計劃項目