基于C.W節約算法及禁忌搜索的路徑優化

徐錫芬

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

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

一、緒論

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

二、案例分析

P第三方物流公司要完成Q公司邯鄲生產基地的銷售物流業務，將邯鄲生產的產品運往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

三、優化方案

（一）運用C.W節約算法優化求解

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

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

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

（1）線路合并

按節約值的上述順序，逐個考察其端點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，比之前節約了89km的運力。

（二）運用禁忌搜索進行檢驗并嘗試優化

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

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

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

發現候選解的評價值都比原始值要大，所以f（x0）已為最優

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

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

【參考文獻】

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

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

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