基于改進(jìn)貪心算法的動態(tài)車輛路徑問題分析

摘要：針對移動電子商務(wù)下的動態(tài)車輛路徑問題，在貪心算法的基礎(chǔ)上，結(jié)合K-d tree方法和Held-Karp模型對貪心算法進(jìn)行改進(jìn)，對移動電子商務(wù)環(huán)境下的動態(tài)車輛路徑問題進(jìn)行案例分析，并驗證該算法的有效性。

關(guān)鍵詞：移動電子商務(wù)；動態(tài)車輛路徑問題；改進(jìn)貪心算法；案例分析

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

一、引言

移動電子商務(wù)環(huán)境下取貨車輛調(diào)度問題的實質(zhì)就是動態(tài)車輛路徑問題（DVRP）。目前對于DVRP問題的解決方法主要包括兩類，一是采用判斷準(zhǔn)則將新出現(xiàn)的顧客添加到已經(jīng)制定的路線中。二是采用優(yōu)化算法從全局最優(yōu)角度出發(fā)。但是目前上述算法不能實現(xiàn)全局系統(tǒng)最優(yōu)，且實時性不強。

二、理論概述

1.貪心算法

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

2. K-d tree方法

K-d tree方法即k維空間二叉搜尋樹，是一種分割k（本文k=2）維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索（如：范圍搜索和最近鄰搜索）。其原理是將系統(tǒng)中n個點所在k維空間進(jìn)行分割，將分割后的區(qū)域視為二叉樹的節(jié)點，將整個區(qū)域用二叉樹表示。

3.Held-Karp模型

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

4.改進(jìn)貪心算法的步驟

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

三、算例說明與求解

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

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

四、結(jié)語

本文結(jié)合K-d tree法和Held-Karp模型提高求解質(zhì)量策略，提出了移動電子商務(wù)環(huán)境下動態(tài)車輛路徑問題的改進(jìn)貪心算法，對12個標(biāo)準(zhǔn)算例求解驗證了該模型和算法能在合理的時間內(nèi)求解DVRP問題。

參考文獻(xiàn)：

[1]易云飛，董文永，林曉東.求解帶軟時間窗車輛路徑問題的改進(jìn)伊藤算法及其收斂性分析[J].電子學(xué)報，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-），女，漢族，山東德州人，山東科技大學(xué)礦業(yè)與安全工程學(xué)院碩士研究生，系統(tǒng)理論專業(yè)。