移動電商下求解DVRP的改進貪心算法

李珊珊

摘要：針對移動電商下的動態車輛路徑問題，實現了從動態問題到靜態問題的轉化，并建立問題模型。在貪心算法的基礎上，結合K-d tree方法和Held Karp模型建立改進貪心算法，并驗證了該模型和算法的有效性。

Abstract： To solve the problem of dynamic vehicle routing problem in mobile e-commerce， dynamic vehicle routing problem is transformed into static vehicle routing problem and the model is established. Based on the greedy algorithm， the improved greedy algorithm is established by combining K-d tree and Held Karp model， and the validity of the model and algorithm is verified.

關鍵詞：移動電商；動態車輛路徑問題；改進貪心算法

Key words： mobile e-commerce；dynamic vehicle routing problem；improved greedy algorithm

中圖分類號：F724.6 文獻標識碼：A 文章編號：1006-4311（2017）08-0072-03

3 算例說明與求解

3.1 算例說明

為了測試所提出模型和算法的有效性，以Li等提出的12個n為560～1200的算例[7]為數據基礎，動態程度？準分別為0.25、0.50、0.75、1.00，如表1所示。

本文的算例中只考慮了新顧客出現的情況，并假設每個算例中的動態顧客在取貨周期中按標號升序方式均勻出現。

3.2 算例求解

本文的求解質量為求解路徑長度與對應靜態算例已知最優解的偏差，求解質量與求解時間如表2。

由表2知，IMGR在求解質量方面優于已知最優解，且求解時間很短，如求解最大的算例DVRP-1200，？準=1.00時，顧客出現的平均時間間隔為24.00s，計算耗時僅為10.35s，能滿足對于算法時間的要求。

4 結束語

本文將移動電商下的DVRP轉化為靜態VRP，建立了動態模型；在GR的基礎上，結合K-d tree法加快求解速度策略和Held Karp模型提高求解質量策略，提出了IMGR方法。并通過對12個算例求解驗證了該模型和算法能在合理的時間內求解DVRP。

參考文獻：

[1]劉宇熹，蔣艷.中國移動電商發展研究及其SWOT分析[A].武漢大學、美國James Madison大學、美國科研出版社，2010：4.

[2]易云飛，董文永，林曉東，蔡永樂.求解帶軟時間窗車輛路徑問題的改進伊藤算法及其收斂性分析[J].電子學報，2015（04）：658-664.

[3]陳志新，陳方玉，胡貴彥，祝亞亭.基于混合粒子群算法的配送車輛復雜路徑優化[J].物流技術，2014（13）：176-178.

[4]王旭，葛顯龍，代應.基于兩階段求解算法的動態車輛調度問題研究[J].控制與決策，2012（02）：175-181.

[5]熊浩，胡列格.多車型動態車輛調度及其遺傳算法[J].系統工程，2009（10）：21-24.

[6]饒衛振.大規模動態車輛路徑問題優化方法研究[D].大連理工大學，2012.

[7]Li FY， Golden B， Wasil Edward. Very large-scale vehicle routing： new test problems， algorithms， and results[J]. Computers&Operations Research， 2005， 32 （5）： 1165-1179.