遺傳節(jié)約綜合算法在配送路線優(yōu)化中的應(yīng)用

喻　偉　何其超　張?jiān)鰲?/p>

摘要：文章針對(duì)配送路線問(wèn)題進(jìn)行研究，首先提出配送路線優(yōu)化的原則，在此基礎(chǔ)上提出了解決配送路線問(wèn)題的遺傳節(jié)約綜合算法的流程和步驟，最后通過(guò)一個(gè)算例實(shí)現(xiàn)了本文提出的算法，并與其它方法的計(jì)算結(jié)果進(jìn)行了比較，從而證實(shí)了遺傳節(jié)約綜合算法的優(yōu)越性。

關(guān)鍵詞：物流；配送路線；遺傳算法；節(jié)約算法

中圖分類號(hào)：U116.2文獻(xiàn)標(biāo)識(shí)碼：A

Abstract: In studying the distribution routes, the paper first introduces the principle of distribution route optimization, and then presents the process and steps of saving hybrid genetic algorithm solving the distribution issue, and last realizes the algorithm raised in this paper by an algorithm example. Compared to the calculated results of other methods, it proves the superiority of saving hybrid genetic algorithm.

Key words: logistics; distribution route; genetic algorithm; saving algorithm

0 引言

配送是近距離、小批量、多品種的物資，根據(jù)用戶需要，把貨物從配送中心送到所需的各個(gè)用戶手中的物流過(guò)程。配送路線優(yōu)化問(wèn)題主要是指在保證商品準(zhǔn)時(shí)到達(dá)客戶指定點(diǎn)的前提下，如何盡可能地減少運(yùn)輸?shù)能嚧魏瓦\(yùn)輸?shù)目偮烦蘙1]。目前解決此問(wèn)題主要采用節(jié)約啟發(fā)式算法(通常稱為節(jié)約法)、遺傳算法、禁忌搜索算法等單一算法，各種算法均存在一定的缺陷[2]。本文主要通過(guò)將遺傳算法和節(jié)約法兩種算法進(jìn)行結(jié)合產(chǎn)生的遺傳節(jié)約綜合算法來(lái)解決配送路線優(yōu)化問(wèn)題。

1 配送路線優(yōu)化原則

進(jìn)行配送路線優(yōu)化時(shí)，必須有明確的目標(biāo)，遵循基本的原則。配送路線方案目標(biāo)的選擇可以從以下幾個(gè)方面來(lái)考慮：

(1)配送效益最高或配送成本最低；

(2)配送里程最短；

(3)配送服務(wù)水準(zhǔn)最優(yōu)。

在滿足客戶需求的前提下，配送車輛行駛的路程越短，配送的成本越低、效益越高，因此配送成本最低和配送里程最短兩個(gè)目標(biāo)選擇其中一個(gè)即可，本文以配送里程最短為優(yōu)化目標(biāo)。

2 配送路線優(yōu)化的遺傳節(jié)約綜合算法

采用遺傳節(jié)約綜合算法解決以上模型，即在進(jìn)程層次上，依次進(jìn)行全局的遺傳搜索和局部的節(jié)約搜索，是一種兩層串行結(jié)構(gòu)。其中，節(jié)約操作的個(gè)體對(duì)象來(lái)自遺傳的進(jìn)化結(jié)果，而經(jīng)過(guò)節(jié)約操作得到的解群又成為新遺傳操作的進(jìn)一步進(jìn)化的種群對(duì)象，這個(gè)過(guò)程反復(fù)迭代，直到滿足終止條件為止，終止條件作為基本參數(shù)，在運(yùn)行前輸入，可以包括：目標(biāo)函數(shù)滿意值、一定的遺傳代數(shù)、連續(xù)多次運(yùn)算結(jié)果均一致不再出現(xiàn)優(yōu)化值等。遺傳節(jié)約綜合算法主要步驟如下。以下步驟可通過(guò)VB等軟件編程實(shí)現(xiàn)。

step2：設(shè)置參數(shù)。遺傳參數(shù)包括群體規(guī)模n，適當(dāng)大的數(shù)M，遺傳操作的類型(確定型和自適應(yīng)型選一)，并設(shè)置控制參數(shù)；

以下首先進(jìn)行遺傳操作過(guò)程：

step3：令t=0，隨機(jī)產(chǎn)生初始群體p0，群體中包括n條染色體，每個(gè)染色體表示一條可行的配送線路；

step4：將群體pt中n條染色體解碼為線路，計(jì)算其目標(biāo)函數(shù)，即運(yùn)輸成本；

step5：尋找群體pt中最優(yōu)染色體bestt，即目標(biāo)函數(shù)最小的線路；

step6：計(jì)算pt中n條染色體的適應(yīng)度；

step7：若滿足終止條件之一，則停止運(yùn)算，結(jié)束程序，輸出pt中的最優(yōu)染色體bestt作為滿意解；否則，繼續(xù)；

step13：根據(jù)各輛車所承擔(dān)的貨運(yùn)任務(wù)總量，進(jìn)行從大到小的排序，并將相應(yīng)的車輛重新編號(hào)為L(zhǎng)-m；

stepl4：令當(dāng)前車輛號(hào)mo=1，待選池A1=空集；

step15：針對(duì)第mo輛車所承擔(dān)的各個(gè)任務(wù)節(jié)點(diǎn)，計(jì)算費(fèi)用節(jié)約值，并進(jìn)行從大到小的排序；

step16：進(jìn)行第mo輛車的原始子路徑Ra安排。按照費(fèi)用節(jié)約值從大到小的順序，將各個(gè)貨運(yùn)節(jié)點(diǎn)插入，產(chǎn)生原始子路徑Ro；

step17：第mo輛車的原始子路徑Ro安排中，若有不滿足容量約束的節(jié)點(diǎn)，則將此節(jié)點(diǎn)放入待選池A1；

step18：計(jì)算待選池A0中的各個(gè)待選節(jié)點(diǎn)與原始子路徑Ro的起點(diǎn)、終點(diǎn)之間的費(fèi)用節(jié)約值（不包括待選節(jié)點(diǎn)相互之間），并進(jìn)行從大到小的排序；

step19：按照step18中費(fèi)用節(jié)約值從大到小的順序，將各個(gè)待選節(jié)點(diǎn)嘗試接入原始子路徑Ro。若滿足容量和時(shí)間約束，則插入，并從A0中刪除該節(jié)點(diǎn)；否則繼續(xù)，直至A0所有待選節(jié)點(diǎn)考察完畢，得到第mo輛車的子路徑R；

step20：令A(yù)0=A0+A1，A1=空集，即將A0和A1合并為A0，同時(shí)清空A1；

step2l：令mo=mo+1，若mo≤m(車輛總數(shù))，則轉(zhuǎn)step15；否則，將m輛車的子路徑合并到一起。形成第j條完整的配送線路，并繼續(xù)；

step22：令j＝j(luò)+1，若j≤n(群體規(guī)模)，則轉(zhuǎn)step12，否則繼續(xù)；

step23：將n條配送線路編碼為n條染色體，形成新的群體pt+1，令t=t+l轉(zhuǎn)step4。

3 算法的實(shí)現(xiàn)

某配送中心使用載重量為4噸的廂式貨車向其13個(gè)客戶(C1—C13)配送物資，各點(diǎn)間單位運(yùn)費(fèi)均一樣，配送中心（C0）和各客戶間距離如表1所示，各客戶配送量如表2所示。

根據(jù)以上數(shù)據(jù)，采用節(jié)約法優(yōu)化配送路線，其結(jié)果如表3。

采用遺傳節(jié)約綜合算法求解基本過(guò)程如下，最終結(jié)果如表4。

4 結(jié)論

將節(jié)約法和遺傳節(jié)約綜合算法的計(jì)算結(jié)果進(jìn)行對(duì)比，派車數(shù)二者均為4輛，總行駛距離綜合遺傳算法的結(jié)果較節(jié)約法少29公里，且車輛實(shí)載率有三車達(dá)到97.5％，較節(jié)約法結(jié)果也更優(yōu)。

通過(guò)以上分析，遺傳節(jié)約綜合算法將遺傳算法和節(jié)約算法相結(jié)合，相互補(bǔ)充，較好地解決了配送路線優(yōu)化的問(wèn)題。但由于該算法需要進(jìn)行一定數(shù)量的迭代計(jì)算，因此需要通過(guò)計(jì)算機(jī)編程實(shí)現(xiàn)，存在不適合于手工計(jì)算的情況。

參考文獻(xiàn)：

[1] 李永生，鄭文嶺． 倉(cāng)儲(chǔ)與配送管理[M]． 北京：機(jī)械工業(yè)出版社，2005．

[2] 徐天亮． 運(yùn)輸與配送[M]． 北京：中國(guó)物資出版社，2002．

[3] 李軍，郭耀煌． 物流配送車輛調(diào)度優(yōu)化理論與方法[M]． 北京：中國(guó)物資出版社，2001．

[4] 趙家俊，于寶琴． 現(xiàn)在物流配送管理[M]． 北京：北京大學(xué)出版社，2004．

[5] 朱德通． 最優(yōu)化模型與實(shí)驗(yàn)[M]． 上海：同濟(jì)大學(xué)出版社，2003．

[6] 《運(yùn)籌學(xué)》教材編寫組． 運(yùn)籌學(xué)[M]． 北京：清華大學(xué)出版社，2008.

[7] 龔沛曾，陸慰民，楊志強(qiáng)． Visual Basic程序設(shè)計(jì)教程[M]． 北京：高等教育出版社，2003．

“注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”。