基于C.W節(jié)約算法及禁忌搜索的路徑優(yōu)化

徐錫芬

【摘 要】隨著經(jīng)濟(jì)的發(fā)展，物流在社會(huì)生產(chǎn)和生活中扮演著越來越重要的作用，第三方物流企業(yè)在整個(gè)物流系統(tǒng)中占據(jù)著很大的比重。車輛運(yùn)輸路徑（VRP）的選擇直接影響著第三方物流公司的物流水平，合理的運(yùn)輸路線選擇可以降低物流成本，增加與商家進(jìn)行運(yùn)輸運(yùn)價(jià)談判的籌碼。本文采用了啟發(fā)式算法里的C.W節(jié)約算法，對(duì)運(yùn)輸路線進(jìn)行設(shè)計(jì)，并用禁忌搜索對(duì)設(shè)計(jì)的每條路線進(jìn)行檢驗(yàn)是否最優(yōu)，并嘗試局部?jī)?yōu)化。

【關(guān)鍵詞】第三方物流;VRP;C.W節(jié)約算法;禁忌搜索

一、緒論

近十多年來，第三方物流企業(yè)在我國(guó)成高速發(fā)展的態(tài)勢(shì)，在這眾多的中小物流企業(yè)中，大部分依然沒能擺脫傳統(tǒng)的物流運(yùn)作模式。如何在中小物流企業(yè)管理技術(shù)力量不足，針對(duì)第三方物流企業(yè)運(yùn)輸配送特點(diǎn)與實(shí)際需求，以實(shí)現(xiàn)運(yùn)輸合理化為目標(biāo)，進(jìn)行運(yùn)輸配送方案優(yōu)化，從而促進(jìn)我國(guó)第三方物流企業(yè)的發(fā)展。

二、案例分析

P第三方物流公司要完成Q公司邯鄲生產(chǎn)基地的銷售物流業(yè)務(wù)，將邯鄲生產(chǎn)的產(chǎn)品運(yùn)往A～O 15個(gè)銷售地。

已知P公司與A～O15個(gè)銷售地之間以及各銷售地之間的距離（km）如下表一。P公司有載重量為2t和4t的兩種車輛可供使用，但車輛一次巡回的行駛距離不能超過40km。為簡(jiǎn)化模型，距離取兩地之間的最短距離。假設(shè)往返距離相等。A-O十五點(diǎn)的需求量分別為：1.5、0.6、0.7、0.6、0.6、1.4、0.8、0.9、0.3、1.2、0.4、0.6、0.8、0.7、0.9。

表一 各銷售地之間的距離 單位：km

三、優(yōu)化方案

（一）運(yùn)用C.W節(jié)約算法優(yōu)化求解

第一步：根據(jù)最短距離表，計(jì)算節(jié)約值Sij。當(dāng)節(jié)約值Sij為負(fù)數(shù)時(shí)，無實(shí)際意義，故取值為零。

第二步：所有的節(jié)約值Sij按從大到小的順序排列，見下表三。

第三步：按照節(jié)約值Sij的大小順序，以及車輛載重量和行駛距離的限制，逐步構(gòu)造配送線路。

（1）線路合并

按節(jié)約值的上述順序，逐個(gè)考察其端點(diǎn)i和j，若滿足以下條件，則連接i、j。其條件是：

a、點(diǎn)i和點(diǎn)j不在一條線路上

b、點(diǎn)i和點(diǎn)j均與基點(diǎn)相鄰。

（2）重復(fù)此步驟，知道將所有的點(diǎn)考察結(jié)束。

得到最終的結(jié)果如下：P-I-A-C-H-L-P;P-F-O-K-N-B-P和P-G-M-D

-J-E-P?？偟男旭偮烦虨?11km，原來的一對(duì)一往返路線的路程為200km，比之前節(jié)約了89km的運(yùn)力。

（二）運(yùn)用禁忌搜索進(jìn)行檢驗(yàn)并嘗試優(yōu)化

運(yùn)用禁忌搜索對(duì)以求得的路線進(jìn)行檢驗(yàn)是否為最優(yōu)，若不是，對(duì)其進(jìn)行優(yōu)化。

（1）對(duì)P-I-A-C-H-L-P的檢驗(yàn)：

初始解x0=（PIACHLP）， f（x0）=36，設(shè)定禁忌長(zhǎng)度為4

發(fā)現(xiàn)候選解的評(píng)價(jià)值都比原始值要大，所以f（x0）已為最優(yōu)

（2）同理對(duì)P-F-O-K-N-B-P 和P-G-M-D-J-E-P進(jìn)行同樣的禁忌搜索，發(fā)現(xiàn)候選解的評(píng)價(jià)值都要比原始值要大。

因此檢驗(yàn)結(jié)果為P公司該情景下，通過C.W節(jié)約算法得出的路線即為最優(yōu)路線。該公司的配送方案為：派遣三輛載重量為4t的運(yùn)輸車，派送路線分別為P-I-A-C-H-L-P、P-F-O-K-N-B-P 和P-G-M-D-J-E-P。

【參考文獻(xiàn)】

[1]郭娜. 基于節(jié)約算法和移動(dòng)方向的禁忌搜索算法[D]. 大連：大連理工大學(xué)，2009：5-9.

[2]葛玉璽.基于C.W節(jié)約算法的第三方物流運(yùn)輸優(yōu)化研究[D]. 贛州：江西理工大學(xué)，2011：1-2.

[3]蔣長(zhǎng)兵.運(yùn)輸與配送管理建模與仿真[M]. 北京：中國(guó)物資出版社，2011.