哈密爾頓圖在快遞送貨中的應用

周海兵

摘要：本文對生活中快遞送貨問題，應用哈密爾頓圖、最佳推銷員回路，建立模型，對完備加權圖給出了近似算法、最小生成樹算法和遺傳算法三種方法，求解最佳圈，即最優(yōu)快遞送貨策略。

關鍵詞：哈密爾頓圈；最佳推銷員回路；近似算法；最小生成樹算法；遺傳算法

近年來，我國快遞業(yè)發(fā)展迅速，企業(yè)數(shù)量大幅增加，業(yè)務規(guī)模持續(xù)擴大，服務水平不斷提升，在降低流通成本、支撐電子商務、服務生產(chǎn)生活、擴大就業(yè)渠道等方面發(fā)揮了積極作用。國務院也在2015年印發(fā)了《關于促進快遞業(yè)發(fā)展的若干意見》，快遞業(yè)已經(jīng)成為現(xiàn)代服務業(yè)的重要組成部分，是推動流通方式轉(zhuǎn)型、促進消費升級的現(xiàn)代化先導性產(chǎ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、模型建立

總站到分站，一般會安排一個車輛負責運送到其中幾個分站點，再要帶回分站點要投遞的快件返回總站（分站到投遞點情形類似處理）。那么尋求路程最短，時間最少的投遞線路，就是尋求最佳推銷員回路問題。最佳推銷員回路問題可轉(zhuǎn)化為最佳圈問題。

首先建立一張完備加權圖G（V，E，W），其中把總站點記為v₀，把n個分站點記為v₁，v₂，…，v_n，邊e_ij表示從站點v_i到v_j的路徑，邊權重w_ij表示從站點v_i到v_j的最短距離或者時間。這樣最優(yōu)快遞送貨策略就轉(zhuǎn)化為求解圖G（V，E，W）中從v₀出發(fā)回到v₀的最佳H圈問題。因為是完備圖，則G（V，E，W）中一定有哈密爾頓圈，所以是哈密爾頓圖。

4、模型求解

4.1近似算法

（1）輸入圖G（V，E，W）中的一個初始H圈；

（2）用對角線完全算法產(chǎn)生一個初始H圈；

（3）隨機搜索出G（V，E，W）中若干個H圈；

（4）對前面所有得到的H圈，用二邊逐次修正法在進行優(yōu)化，獲得近似最佳H圈；

（5）在上一步求出的所有近似最佳H圈，找出權最小的一個。此方法可以找到最佳H圈的近似解，即局部最優(yōu)解。

4.2最小生成樹算法

（1）將完備加權圖G（V，E，W）轉(zhuǎn)化為新圖G（V'，E，W'），其中兩個端點記為s和f。原圖中最佳H圈轉(zhuǎn)化為在新圖G（V'，E'，W'）中求s到f的最佳哈密爾頓路。

其中新圖G（V，E，W）構(gòu)造過程如下：

選取總站點v₀，用兩個端點s和f代替；V=（V-v₀）∪{s，F(xiàn)}W'_ij=w_ij對所有v_i，v_j？{s，f}的邊；w'_sj=w_0j+M，當v_j≠f；w'_if=w_i0+M，當v_i≠s；w'_sf=w'_fs=2M；W'_ii=∞，對所有v_i∈V'。

M選為足夠大的數(shù)，應用最小生成樹算法時與s和f關聯(lián)的邊就不會被選入最優(yōu)回路，顯然在原圖中的最佳H圈與新圖中s到f的最佳哈密爾頓路是對應一致的。

（2）在G（V'，E'，W）中求解最小生成樹T，由w'_sf的取值可知最優(yōu)解一定不含邊e_sf，當最小生成樹的各個頂點度小于等于2時，則得到s到f的最佳哈密爾頓路，將s和f合并為一個點，即為G（V，E，W）的最佳H圈。

（3）若有頂點度大于等于3，則選擇其中次數(shù)較小的進行分枝。G'=G'₁∪G'₂∪G'₃…，G'₁=G＼e_T1，G'₂=G＼e_T2…，其中G'₁，G'₂，G'₃…為分枝以后的新圖，e_T1，e_T2，…為與分枝頂點關聯(lián)的邊。繼續(xù)在G'₁，G'₂，G'₃…中應用最小生成樹算法，最后得到一個權值最小且各點的度均小于等于2的圖，即是G（V'，E'，W'）中的最佳哈密爾頓路。

此方法中分枝定界等一些環(huán)節(jié)在結(jié)點數(shù)n較大時，實現(xiàn)難度增大。在這里單一車輛巡回路，涉及到的結(jié)點數(shù)一般不會很多。

4.3遺傳算法

遺傳算法包括3個基本操作：選擇、交叉和變異?；芈烽L度是度量某個染色體的優(yōu)良性的標準，長度越小說明染色體越優(yōu)秀，應該保留，這也是算法中適用度函數(shù)的考量點。

算法描述：

（1）編碼初始化。設置最大進化代數(shù)MaxG，種群規(guī)模G，貪心替換算子P_r，變異算子P_m，和交叉算子P_c，并生成初始隨機種群。

（2）個體評價。用適應度函數(shù)對每個基因進行評價。

（3）選擇操作。首先用最優(yōu)的染色體方案替換占種群規(guī)模P_r的最壞個體，再用基本輪轉(zhuǎn)法進行選擇。

（4）交叉操作。采用順序交叉操作方法。

（5）變異操作。只有當變異后的基因優(yōu)于原基因時，變異成功。

（6）終止條件。當進化代數(shù)大于MaxG時，算法結(jié)束，否則轉(zhuǎn)向步驟（2）。

在進行選擇操作時，將最優(yōu)值替換和輪轉(zhuǎn)法相結(jié)合，使得算法更容易獲得全局最優(yōu)解。順序交叉操作方法，也更適合于哈密爾頓圈的特性。

對于三種算法得到的最佳圈，分別計算各個對應的權值，比較得到權值最小的，即就是要尋求的最杭快遞送貨策略。

5、模型的評價

這里哈密爾頓圖模型中只考慮單一車輛最優(yōu)巡回路問題，而且假設是最簡單情形，實際情況要復雜的多，要滿足貨物需求量、發(fā)送量、交貨時間、車輛容量限制等目的，需要考慮安排多條送貨線路，使得總時間盡量短，總里程盡量小。同時由于不同時間段可能出現(xiàn)的出行高峰，要組織調(diào)整合適的車輛行駛路徑，才能最終使得快遞企業(yè)運行成本最低。此問題是一個NP-hard問題。

此方法還可應用生活中于災情巡視、旅游線路安排、交通車最佳巡回路線等。