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

李珊珊

摘要：針對移動電商下的動態(tài)車輛路徑問題，實現(xiàn)了從動態(tài)問題到靜態(tài)問題的轉(zhuǎn)化，并建立問題模型。在貪心算法的基礎(chǔ)上，結(jié)合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.

關(guān)鍵詞：移動電商；動態(tài)車輛路徑問題；改進貪心算法

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]為數(shù)據(jù)基礎(chǔ)，動態(tài)程度？準分別為0.25、0.50、0.75、1.00，如表1所示。

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

3.2 算例求解

本文的求解質(zhì)量為求解路徑長度與對應(yīng)靜態(tài)算例已知最優(yōu)解的偏差，求解質(zhì)量與求解時間如表2。

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

4 結(jié)束語

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

參考文獻：

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

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

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

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

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

[6]饒衛(wèi)振.大規(guī)模動態(tài)車輛路徑問題優(yōu)化方法研究[D].大連理工大學(xué)，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.