徐錫芬
【摘 要】隨著經濟的發展,物流在社會生產和生活中扮演著越來越重要的作用,第三方物流企業在整個物流系統中占據著很大的比重。車輛運輸路徑(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??偟男旭偮烦虨?11km,原來的一對一往返路線的路程為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.