周海兵
摘要:本文對生活中快遞送貨問題,應用哈密爾頓圖、最佳推銷員回路,建立模型,對完備加權圖給出了近似算法、最小生成樹算法和遺傳算法三種方法,求解最佳圈,即最優(yōu)快遞送貨策略。
關鍵詞:哈密爾頓圈;最佳推銷員回路;近似算法;最小生成樹算法;遺傳算法
近年來,我國快遞業(yè)發(fā)展迅速,企業(yè)數(shù)量大幅增加,業(yè)務規(guī)模持續(xù)擴大,服務水平不斷提升,在降低流通成本、支撐電子商務、服務生產生活、擴大就業(yè)渠道等方面發(fā)揮了積極作用。國務院也在2015年印發(fā)了《關于促進快遞業(yè)發(fā)展的若干意見》,快遞業(yè)已經(jīng)成為現(xiàn)代服務業(yè)的重要組成部分,是推動流通方式轉型、促進消費升級的現(xiàn)代化先導性產業(yè)。
一般地,所有快件到達某地總部以后,比如武漢總站,會安排車輛盡快送到各個區(qū)分站點。各個區(qū)分站點再及時把快件送達各個小的投遞點。本文應用哈密爾頓圖、最佳推銷員回路,建模解決最優(yōu)快遞送貨策略。
1、定義和符號
(1)G(V,E,W)表示加權圖,V表示點集合,E表示邊集合,W表示邊的權集合。
(2)經(jīng)過圖G的每個頂點正好一次的路,稱為圖G的哈密爾頓路。經(jīng)過圖G的每個頂點正好一次的圈,稱為圖G的哈密爾頓圈,簡稱H圈。包含H圈的圖稱為哈密爾頓圖。
(3)在加權圖G(V,E,W)中權最小的哈密爾頓圈稱為最佳H圈,經(jīng)過每個頂點至少一次且權最小的閉通路稱為最佳推銷員回路。
2、模型的假設
(1)假設路況良好,沒有意外交通擁堵。
(2)假設車輛容量足夠大,交貨時間忽略。
3、模型建立
總站到分站,一般會安排一個車輛負責運送到其中幾個分站點,再要帶回分站點要投遞的快件返回總站(分站到投遞點情形類似處理)。那么尋求路程最短,時間最少的投遞線路,就是尋求最佳推銷員回路問題。最佳推銷員回路問題可轉化為最佳圈問題。
首先建立一張完備加權圖G(V,E,W),其中把總站點記為v0,把n個分站點記為v1,v2,…,vn,邊eij表示從站點vi到vj的路徑,邊權重wij表示從站點vi到vj的最短距離或者時間。這樣最優(yōu)快遞送貨策略就轉化為求解圖G(V,E,W)中從v0出發(fā)回到v0的最佳H圈問題。因為是完備圖,則G(V,E,W)中一定有哈密爾頓圈,所以是哈密爾頓圖。
4、模型求解
4.1近似算法
(1)輸入圖G(V,E,W)中的一個初始H圈;
(2)用對角線完全算法產生一個初始H圈;
(3)隨機搜索出G(V,E,W)中若干個H圈;
(4)對前面所有得到的H圈,用二邊逐次修正法在進行優(yōu)化,獲得近似最佳H圈;
(5)在上一步求出的所有近似最佳H圈,找出權最小的一個。此方法可以找到最佳H圈的近似解,即局部最優(yōu)解。
4.2最小生成樹算法
(1)將完備加權圖G(V,E,W)轉化為新圖G(V',E,W'),其中兩個端點記為s和f。原圖中最佳H圈轉化為在新圖G(V',E',W')中求s到f的最佳哈密爾頓路。
其中新圖G(V,E,W)構造過程如下:
選取總站點v0,用兩個端點s和f代替;V=(V-v0)∪{s,F(xiàn)}W'ij=wij對所有vi,vj?{s,f}的邊;w'sj=w0j+M,當vj≠f;w'if=wi0+M,當vi≠s;w'sf=w'fs=2M;W'ii=∞,對所有vi∈V'。
M選為足夠大的數(shù),應用最小生成樹算法時與s和f關聯(lián)的邊就不會被選入最優(yōu)回路,顯然在原圖中的最佳H圈與新圖中s到f的最佳哈密爾頓路是對應一致的。
(2)在G(V',E',W)中求解最小生成樹T,由w'sf的取值可知最優(yōu)解一定不含邊esf,當最小生成樹的各個頂點度小于等于2時,則得到s到f的最佳哈密爾頓路,將s和f合并為一個點,即為G(V,E,W)的最佳H圈。
(3)若有頂點度大于等于3,則選擇其中次數(shù)較小的進行分枝。G'=G'1∪G'2∪G'3…,G'1=G\eT1,G'2=G\eT2…,其中G'1,G'2,G'3…為分枝以后的新圖,eT1,eT2,…為與分枝頂點關聯(lián)的邊。繼續(xù)在G'1,G'2,G'3…中應用最小生成樹算法,最后得到一個權值最小且各點的度均小于等于2的圖,即是G(V',E',W')中的最佳哈密爾頓路。
此方法中分枝定界等一些環(huán)節(jié)在結點數(shù)n較大時,實現(xiàn)難度增大。在這里單一車輛巡回路,涉及到的結點數(shù)一般不會很多。
4.3遺傳算法
遺傳算法包括3個基本操作:選擇、交叉和變異?;芈烽L度是度量某個染色體的優(yōu)良性的標準,長度越小說明染色體越優(yōu)秀,應該保留,這也是算法中適用度函數(shù)的考量點。
算法描述:
(1)編碼初始化。設置最大進化代數(shù)MaxG,種群規(guī)模G,貪心替換算子Pr,變異算子Pm,和交叉算子Pc,并生成初始隨機種群。
(2)個體評價。用適應度函數(shù)對每個基因進行評價。
(3)選擇操作。首先用最優(yōu)的染色體方案替換占種群規(guī)模Pr的最壞個體,再用基本輪轉法進行選擇。
(4)交叉操作。采用順序交叉操作方法。
(5)變異操作。只有當變異后的基因優(yōu)于原基因時,變異成功。
(6)終止條件。當進化代數(shù)大于MaxG時,算法結束,否則轉向步驟(2)。
在進行選擇操作時,將最優(yōu)值替換和輪轉法相結合,使得算法更容易獲得全局最優(yōu)解。順序交叉操作方法,也更適合于哈密爾頓圈的特性。
對于三種算法得到的最佳圈,分別計算各個對應的權值,比較得到權值最小的,即就是要尋求的最杭快遞送貨策略。
5、模型的評價
這里哈密爾頓圖模型中只考慮單一車輛最優(yōu)巡回路問題,而且假設是最簡單情形,實際情況要復雜的多,要滿足貨物需求量、發(fā)送量、交貨時間、車輛容量限制等目的,需要考慮安排多條送貨線路,使得總時間盡量短,總里程盡量小。同時由于不同時間段可能出現(xiàn)的出行高峰,要組織調整合適的車輛行駛路徑,才能最終使得快遞企業(yè)運行成本最低。此問題是一個NP-hard問題。
此方法還可應用生活中于災情巡視、旅游線路安排、交通車最佳巡回路線等。