改進的節約算法在車輛路徑優化問題中的應用研究

摘 要：C-W節約算法以其簡單的原理在路徑優化問題中，非常實用，但是傳統的節約算法是理想化的模型，它有一定的局限性，實際生活中的問題有更多的限制因素，傳統的節約算法可能并不十分適用。將傳統的節約算法加以改進，用當量距離代替原先的距離，并引入運達時間的約束，求解出另一種配送方案，以期更符合實際情況。

關鍵詞：節約算法；改進；時間約束；車輛路徑優化

1 傳統節約算法概述

傳統節約算法根據配送中心的運輸能力及其到客戶之間的距離和各客戶之間的相對距離來確定最佳配送路線。它的原理很簡單，可以用兩個圖簡單地表示（圖1）。

但是傳統的節約算法是基于理想化的條件，忽視了很多客觀條件的影響，存在著一定的局限性，它所得出的結果并不一定十分貼合實際情況。兩個地點之間的運輸距離最短并不意味著運輸所使用的時間最短。現實中往往由于路況的原因，造成距離看似較短的兩處地方，卻花費了較多的時間來運輸貨物。此外，很多時候配送的商品必須保證在一定的時間點前送達，特別是生鮮類等易腐商品對配送的及時性做出了一定的要求，而傳統的節約算法在求解時并未考慮到這個問題。

2 改進的節約算法的思路

（1）考慮路況等實際因素的影響，將時間折合成距離，引入當量距離的概念，由事先確定的比重算出當量距離，進而將這些當量距離用于節約算法中，以確定最優的配送路線。而這個比例應由各個企業根據自身情況自行決定，實際距離（d1）所占比重設為α，時間折合成的距離（d2）占所占比重設為β，當量距離設為D，則可得計算公式D=αd1+βd2。

（2）運輸時間折合成當量距離的方法是，將車輛在所有點兩兩之間的實際運輸時間測出tij，然后累加所有點之間的距離，將累加的距離除以累加的時間T，得到一個平均速度值v，則d2=v*tij。

（3）給定一個特定的時間段，一輛運輸車將商品陸續配送到各個客戶時都得保證在這個特定的時間段內。使用節約算法時，依次校驗新加入該條路線中的配送點是否滿足時間的約束，如果滿足，繼續增加新的配送點，如果不滿足，則停止加入新的配送點，此時該條線路已唯一確定。

3 實例分析

有一家企業只有一個配送中心，它同時為8個客戶配送商品，該企業擁有2t和4t的運輸車若干輛。該企業與8個客戶的當量距離以及各個客戶的需求如圖2所示，找出路徑優化后的配送路線結果。

將節約里程按從大到小的順序排列后，順次連接p5、p6，再連接p2、p3，按照節約里程的降序，按照傳統節約算法的規則，依次連接。如果不考慮時間約束，則可以得到三條配送路線：

①P0p4p5p6 47+22=69；②P0p2p3 33+23=56；③P0p1p8p7 55+16=71。

而如果把配送時間限定在一定范圍內，則配送路線可能不符合客戶的要求，為了便于量化，將時間限制反映到距離限制上來，如必須在50km（以平均速度行駛）所應花費的時間段內到達，則原先的第三條路線是不符合要求的。每一條配送路線根據順時針或逆時針方向配送時，在最后一個配送點的最晚到達時間上一般來說是不同的，應選擇較早的配送方向。

所以最終的配送路線應該是四條，分別是：

①p0p4p5p6；②p0p2p3；③p0p1p8；④p0p7

4 結束語

節約算法自誕生以來有很強的生命力，但傳統的節約算法有一定的局限性，許多人試圖改善原始的算法，如加入各種的約束。文章同樣是以一種局部改善的想法來完善傳統的節約算法，并通過一個實例來驗證加入適當的約束后，得出的結果確實與原先的存在差異。節約算法本身的原理十分簡單，文章在原有基礎上加入適當的約束后，也沒有顯著提高節約算法的復雜程度，在路徑優化問題中，可以采用文章的模型求得配送路徑。然而文章仍然存在一定的局限性，因為實際生活中存在著太多的不確定性因素，文章僅僅重點關注了其中的兩個方面。

參考文獻

[1]李遠遠，劉彥，劉光前，等.車輛路徑問題優化——基于改進節約算法[J].社會科學家，2013（11）：76-79.

[2]崔宏志，龔加安.帶時間窗車輛路徑問題的改進節約算法[J].純粹數學與應用數學，2011，27（5）：688-693.

[3]張學志，陳功玉.車輛路線安排的一種改進節約算法[J].物流技術，2008，27（10）：139-141.

[4]劉誠，顧坤坤.具有區間參數的VRP及其改進的C-W節約算法[J].武漢理工大學學報（信息與管理工程版），2010，32（2）：182-185.

作者簡介：吳文佳（1995-），女，漢族，安徽全椒，本科，南京農業大學。