基于改進貪心算法的動態車輛路徑問題分析

摘要：針對移動電子商務下的動態車輛路徑問題，在貪心算法的基礎上，結合K-d tree方法和Held-Karp模型對貪心算法進行改進，對移動電子商務環境下的動態車輛路徑問題進行案例分析，并驗證該算法的有效性。

關鍵詞：移動電子商務；動態車輛路徑問題；改進貪心算法；案例分析

中圖分類號：O22 文獻識別碼：A 文章編號：1001-828X（2017）001-000-01

一、引言

移動電子商務環境下取貨車輛調度問題的實質就是動態車輛路徑問題（DVRP）。目前對于DVRP問題的解決方法主要包括兩類，一是采用判斷準則將新出現的顧客添加到已經制定的路線中。二是采用優化算法從全局最優角度出發。但是目前上述算法不能實現全局系統最優，且實時性不強。

二、理論概述

1.貪心算法

貪心算法求解DVRP的過程是將任意兩節點構成的邊按邊長升序排列有（Cn2=n（n-1）/2條邊），從最短邊開始依次添加合法邊至當前路徑中，直到添加完所有合法邊，形成每條路徑的兩端點都與配送中心節點O連接形成Hamilton回路為止

2. K-d tree方法

K-d tree方法即k維空間二叉搜尋樹，是一種分割k（本文k=2）維數據空間的數據結構，主要應用于多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。其原理是將系統中n個點所在k維空間進行分割，將分割后的區域視為二叉樹的節點，將整個區域用二叉樹表示。

3.Held-Karp模型

Held和Karp在1970年提出了經典的Held-Karp模型，用于求解旅行商問題的最優解下界。該模型的原理是使用一個實數向量η=（η1，η2，…ηn）改造距離矩陣的模型。

4.改進貪心算法的步驟

對改進貪心算法的整個過程分步驟說明：（1）讀取DVRP問題和第i個新出現的顧客；（2）設置t和α兩個參數；（3）根據顧客和配送中心的坐標信息、t建立K-d tree；（4）根據坐標信息和α計算向量η；（5）根據K-d tree和Held-Karp 模型改造后距離矩陣，計算每個節點i對應的最鄰近節點j，并將邊（i，j）和對應長度rij+ηi+ηj存至Heap，且按邊長升序排列；（6）提取Heap中的第一條最短邊，假設為（x，y）；（7）判斷添加邊（x，y）至當前路徑是否滿足判斷合法邊的4條規則，滿足執行（9）否則執行（8）；（8）更新Heap數組，保證每個可連接節點與最鄰近節點形成的邊均在Heap中，然后執行（6）；（9）添加邊（x，y）至當前路徑中；（10）確定是否還有合法邊存在，如果有則執行（8）；否則將形成的m條路徑的端點分別與配送中心連接得到最終解，結束程序。

三、算例說明與求解

本文以Li等人在2005年提出了12個n為560～1200的算例為數據基礎，算例名稱最后的數量表示顧客數量，動態程度φ分別為0.25、0.50、0.75、1.00。求解質量與求解時間如表1。

改進貪心算法在求解質量方面優于已知最優解，求解時間較短。求解最大的算例DVRP-1200，φ=1.00時，顧客出現的平均時間間隔為24.00s，計算耗時僅為10.35s，能滿足對于算法時間的要求。

四、結語

本文結合K-d tree法和Held-Karp模型提高求解質量策略，提出了移動電子商務環境下動態車輛路徑問題的改進貪心算法，對12個標準算例求解驗證了該模型和算法能在合理的時間內求解DVRP問題。

參考文獻：

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

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

作者簡介：李珊珊（1991-），女，漢族，山東德州人，山東科技大學礦業與安全工程學院碩士研究生，系統理論專業。