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

徐錫芬

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

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

一、緒論

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

二、案例分析

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

已知P公司與A～O15個銷售地之間以及各銷售地之間的距離（km）如下表一。P公司有載重量為2t和4t的兩種車輛可供使用，但車輛一次巡回的行駛距離不能超過40km。為簡化模型，距離取兩地之間的最短距離。假設往返距離相等。A-O十五點的需求量分別為：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)化方案

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

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

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

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

（1）線路合并

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

a、點i和點j不在一條線路上

b、點i和點j均與基點相鄰。

（2）重復此步驟，知道將所有的點考察結束。

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

-J-E-P。總的行駛路程為111km，原來的一對一往返路線的路程為200km，比之前節(jié)約了89km的運力。

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

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

（1）對P-I-A-C-H-L-P的檢驗：

初始解x0=（PIACHLP）， f（x0）=36，設定禁忌長度為4

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

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

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

【參考文獻】

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

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

[3]蔣長兵.運輸與配送管理建模與仿真[M]. 北京：中國物資出版社，2011.