城市末端物流配送問題研究

何俊生，史 昊 HE Jun-sheng,SHI Hao

（重慶交通大學 交通運輸學院，重慶 400074）

車輛路徑問題 （Vehicle Routing Problem,VRP）在交通運輸、工業生產等各領域應用廣泛，目前基于VRP問題研究的成果很多，盡管對于該類問題的求解方法層出不窮[1-5]，其中不乏一些關于末端物流配送問題的管理學模型成果[6]，但是對于這類問題的量化研究成果尚未見文獻報道。

末端配送是指送達給消費者的物流活動，是以滿足配送環節的終端 （客戶）為直接目的。隨著社會經濟活動越來越以消費者的需求為中心， “用戶第一”的基本觀念深入人心，因此末端物流越來越受到重視。能否快速送達是顧客衡量快遞公司的一個重要標準。而末端物流配送需要考慮的很重要的一點則是最短時間配送路徑，因此本文對這一問題進行深入研究。

1 城市末端物流配送路徑模型

1.1 城市末端物流配送路徑模型建立。為了不失一般性，將快遞企業抽象為配送中心，將各個顧客抽象為配送節點。模型建立的目的是為了求得配送中心到各個需求節點的總配送時間最短。變量dij表示節點i到節點j的距離；若從i到j無路徑到達則用dij=∞表示。變量vijTi（）表示Ti時刻車輛從節點i到節點j的行駛速度。變量tijTi（）表示從節點i到節點j所用的時間，同理，若從i到j無路徑則用tijTi（）=∞表示；其中Ti表示到達節點i的時刻，從配送中心出發的時刻用T0表示。tijTi（）可用公式tijTi（）=dijvijTi（）計算得到。令物流配送中心某車配送的客戶集合為N（其中0代表物流配送中心，配送節點的個數為n），Ti（）,i,j∈N為Ti時刻從i點出發到j點的最短行駛時間。則城市末端物流配送問題數學模型如下：

式 （2）到式 （6）為約束條件。xij為決策變量，意為判定節點i與節點j之間是否有可通行路徑；如果節點i和節點j在可通行路徑上i≠（）j，則xij=1，否則xij=0。式 （2）和式 （3）是平衡條件，表明路徑的可逆性；式 （4）表示對每個節點的配送為一次且僅為一次，若為配送中心，則表示車輛離開配送中心后完成配送任務仍回到配送中心；式 （5）表示從節點j出發的時刻；式 （6）為確保配送回路通過配送中心。

1.2 城市末端物流配送路徑模型的遺傳算法。VRP問題屬于NP-Hard問題，解決這類問題多用啟發式算法。遺傳算法是美國密執安大學Holland教授受生物模擬技術啟發，創造出的一種適合于復雜系統計算優化的啟發式算法。該算法具有較強的魯棒性，廣泛應用于車輛路徑問題的尋優計算中，并在多數情況下能得到比較滿意的解。1.2.1 編碼。本文采用自然編碼方式。例如有6個配送節點，其編號分為為1到6號。首先將需要配送的節點進行隨機排列，如假設0為配送中心，這里可在染色體兩邊添加0，形成染色體；就形成了0與0之間的一條配送路徑 （從配送中心出發，最后回到配送中心），即0→1→3→4→6→5→2→0。

通常的研究認為節點間由直線相連[7-11]，但更多情況下節點與節點間是由路網相連的，即從節點到節點的路徑不唯一；因此單一的認為節點間由直線組成是不符合實際的，本文從節點間由路網組成出發，兩點間的路網最短時間路徑由Dijkstra算法求得。

1.2.2 適應函數。這里以目標函數作為適應函數，即完成一條配送路徑所需的時間。個體所對應目標函數值Z即為此個體的適應值。

1.2.3 選擇操作。取種群各染色體適應值倒數除以倒數之和，作為各染色體被選擇的概率；采用輪盤賭的方式選擇染色體復制到新種群，直到新種群規模與父代相同為止。

1.2.4 交叉、變異操作。本文采用部分映射交叉法，從種群第一個染色體開始，兩兩成組，對每組染色體，隨機生成數若小于等于交叉概率pc，則染色體兩端0不動，取中間隨機一段進行交叉互換，否則，該組染色體不進行交叉操作。對于交叉操作，染色體若有與交叉區段沖突數字 （下劃線表示）， 兩染色體互相一一對應交換，交叉結束。例如：

變異操作是對種群每一個染色體，隨機生成數若小于等于變異概率pm，則染色體兩端0不動，隨機取染色體兩個數字并交換位置，形成新染色體，否則，該染色體不進行變異操作。

1.2.5 計算過程

Step 1：各參數初始化，并設置達到最大迭代次數gen max為算法終止條件；

Step 2：gen:=1時，隨機產生初始群體chromgen；

Step 3：計算種群各個體的適應值，并選出得到最優的適應值和最優的個體；

Step 4：根據輪盤賭選擇法，復制染色體生成新的種群；

Step 5：對新的種群進行交叉、變異操作；

Step 6：采用精英策略，取上一代最優個體替代新一代對應位置染色體；

Step 7： gen:=gen+1；

Step 8：若滿足終止條件，轉到step 9，否則轉到step 3；

Step 9：取種群最優的適應值benefitgen即為最短時間，對應個體bestpopgen為最優方案。

2 算例分析

設路網中共有25個節點，利用random函數生成的隨機點坐標如表1所示。由表1生成的路網拓撲圖如圖1所示。

其中的數字為各個節點編號，紅色方塊表示配送中心，紫紅色圓形表示各個配送點。

考慮到實際情況，在不同時段不同路段的行車速度不同。故設所有路段在非高峰時段行車速度為40km/h，某些路段高峰時段 （7:30-9:00，17:00-19:00）平均行車速度如表2所示。

若上午8:00從節點6發車，設種群規模為40，迭代次數為100次。在CPU2.0GHz，內存2GB的計算機上多次利用遺傳算法求出的最短時間為1小時54分鐘，其中一條行駛路徑為：6→17→12→3→11→7→24→16→19→14→8→13→15→22→9→10→6 （見圖 2）。

3 結 論

本文討論了實時路網下的一類直接面對消費者的末端物流配送問題，建立了末端物流配送路徑模型。通過結合Dijkstra算法的優化遺傳算法求得最優解，經過數值算例的驗證，該模型更加符合物流配送的實際情況，該算法能在實時路網環境下有效地找到最短時間路徑，減少車輛行駛的總時間。進一步的研究工作可以從多車輛路徑實時路網末端物流配送路徑建模及模型快速求解優化算法等方面展開。

[1] 孫國華.基于真實路網的車輛路徑問題研究[J].物流技術，2011,30(1):43-45.

[2] 韓世蓮.帶時間窗的多目標配送線路選擇問題的目標規劃模型[J].物流技術，2008,184(1):44-45.

[3] 賀竹磬，孫林巖.動態交通下車輛路徑選擇模型及算法[J].交通運輸工程學報，2007,7(1):111-115.

[4] Babak Farhang Moghadam,Seyed Mohammad Seyedhosseini.A particle swarm approach to solve vehicle routing problem with uncertain demand[J].International Journal of Industrial Engineering Computations,2010(1):55-66.

表1 路網節點坐標

表2 高峰時段路段擁堵平均行車速度

[5] Yiyo Kuo,Chi-Chang Wang.Optimizing the VRP by minimizing fuel consumption[J].Management of Environmental Quality,2011,4(22):440-450.

[6] 藍伯雄，張躍.一種新型的末端物流配送服務模式[J].管理世界，2003(6):147-148.

[7] 郎茂祥.基于遺傳算法的物流配送路徑優化問題的研究[J].中國公路學報，2002(3):76-79.

[8] 宋少忠，孔繁森.時變路網下VRP準時路徑的選擇[J].吉林大學學報 （理學版），2012,3(50):309-314.

[9] 洪聯系.帶時間窗口動態車輛路徑規劃模型及其求解算法[J].計算機工程與應用，2012,48(4):244-248.

[10] 周長峰，譚躍進，廖良才.實時條件下多車輛路徑與調度[J].系統工程，2006,5(24):35-39.

[11] 劉勇，崔丙謀，王小東.物流配送路徑優化問題的模型及改進混合算法[J].物流科技，2008(4):26-30.