周海兵
摘要:本文對(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)記為v0,把n個(gè)分站點(diǎn)記為v1,v2,…,vn,邊eij表示從站點(diǎn)vi到vj的路徑,邊權(quán)重wij表示從站點(diǎn)vi到vj的最短距離或者時(shí)間。這樣最優(yōu)快遞送貨策略就轉(zhuǎn)化為求解圖G(V,E,W)中從v0出發(fā)回到v0的最佳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)v0,用兩個(gè)端點(diǎn)s和f代替;V=(V-v0)∪{s,F(xiàn)}W'ij=wij對(duì)所有vi,vj?{s,f}的邊;w'sj=w0j+M,當(dāng)vj≠f;w'if=wi0+M,當(dāng)vi≠s;w'sf=w'fs=2M;W'ii=∞,對(duì)所有vi∈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)解一定不含邊esf,當(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'1∪G'2∪G'3…,G'1=G\eT1,G'2=G\eT2…,其中G'1,G'2,G'3…為分枝以后的新圖,eT1,eT2,…為與分枝頂點(diǎn)關(guān)聯(lián)的邊。繼續(xù)在G'1,G'2,G'3…中應(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,貪心替換算子Pr,變異算子Pm,和交叉算子Pc,并生成初始隨機(jī)種群。
(2)個(gè)體評(píng)價(jià)。用適應(yīng)度函數(shù)對(duì)每個(gè)基因進(jìn)行評(píng)價(jià)。
(3)選擇操作。首先用最優(yōu)的染色體方案替換占種群規(guī)模Pr的最壞個(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)等。