哈密爾頓圖在快遞送貨中的應(yīng)用

周海兵

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

關(guān)鍵詞：哈密爾頓圈；最佳推銷(xiāo)員回路；近似算法；最小生成樹(shù)算法；遺傳算法

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

一般地，所有快件到達(dá)某地總部以后，比如武漢總站，會(huì)安排車(chē)輛盡快送到各個(gè)區(qū)分站點(diǎn)。各個(gè)區(qū)分站點(diǎn)再及時(shí)把快件送達(dá)各個(gè)小的投遞點(diǎn)。本文應(yīng)用哈密爾頓圖、最佳推銷(xiāo)員回路，建模解決最優(yōu)快遞送貨策略。

1、定義和符號(hào)

（1）G（V，E，W）表示加權(quán)圖，V表示點(diǎn)集合，E表示邊集合，W表示邊的權(quán)集合。

（2）經(jīng)過(guò)圖G的每個(gè)頂點(diǎn)正好一次的路，稱(chēng)為圖G的哈密爾頓路。經(jīng)過(guò)圖G的每個(gè)頂點(diǎn)正好一次的圈，稱(chēng)為圖G的哈密爾頓圈，簡(jiǎn)稱(chēng)H圈。包含H圈的圖稱(chēng)為哈密爾頓圖。

（3）在加權(quán)圖G（V，E，W）中權(quán)最小的哈密爾頓圈稱(chēng)為最佳H圈，經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次且權(quán)最小的閉通路稱(chēng)為最佳推銷(xiāo)員回路。

2、模型的假設(shè)

（1）假設(shè)路況良好，沒(méi)有意外交通擁堵。

（2）假設(shè)車(chē)輛容量足夠大，交貨時(shí)間忽略。

3、模型建立

總站到分站，一般會(huì)安排一個(gè)車(chē)輛負(fù)責(zé)運(yùn)送到其中幾個(gè)分站點(diǎn)，再要帶回分站點(diǎn)要投遞的快件返回總站（分站到投遞點(diǎn)情形類(lèi)似處理）。那么尋求路程最短，時(shí)間最少的投遞線(xiàn)路，就是尋求最佳推銷(xiāo)員回路問(wèn)題。最佳推銷(xiāo)員回路問(wèn)題可轉(zhuǎn)化為最佳圈問(wèn)題。

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

4、模型求解

4.1近似算法

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

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

（3）隨機(jī)搜索出G（V，E，W）中若干個(gè)H圈；

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

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

4.2最小生成樹(shù)算法

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

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

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

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

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

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

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

4.3遺傳算法

遺傳算法包括3個(gè)基本操作：選擇、交叉和變異。回路長(zhǎng)度是度量某個(gè)染色體的優(yōu)良性的標(biāo)準(zhǔn)，長(zhǎng)度越小說(shuō)明染色體越優(yōu)秀，應(yīng)該保留，這也是算法中適用度函數(shù)的考量點(diǎn)。

算法描述：

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

（2）個(gè)體評(píng)價(jià)。用適應(yīng)度函數(shù)對(duì)每個(gè)基因進(jìn)行評(píng)價(jià)。

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

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

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

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

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

對(duì)于三種算法得到的最佳圈，分別計(jì)算各個(gè)對(duì)應(yīng)的權(quán)值，比較得到權(quán)值最小的，即就是要尋求的最杭快遞送貨策略。

5、模型的評(píng)價(jià)

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

此方法還可應(yīng)用生活中于災(zāi)情巡視、旅游線(xiàn)路安排、交通車(chē)最佳巡回路線(xiàn)等。