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

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

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

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

一、引言

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

二、理論概述

1.貪心算法

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

2. K-d tree方法

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

3.Held-Karp模型

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

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

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

三、算例說(shuō)明與求解

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

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

四、結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]易云飛，董文永，林曉東.求解帶軟時(shí)間窗車輛路徑問(wèn)題的改進(jìn)伊藤算法及其收斂性分析[J].電子學(xué)報(bào)，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.

作者簡(jiǎn)介：李珊珊（1991-），女，漢族，山東德州人，山東科技大學(xué)礦業(yè)與安全工程學(xué)院碩士研究生，系統(tǒng)理論專業(yè)。