摘 要：針對移動(dòng)電子商務(wù)環(huán)境下的動(dòng)態(tài)車輛路徑問題，本文將動(dòng)態(tài)車輛路徑問題轉(zhuǎn)化為靜態(tài)車輛路徑問題，建立問題模型，并利用貪心算法進(jìn)行求解。

關(guān)鍵詞：移動(dòng)電子商務(wù)；車輛調(diào)度；模型；貪心算法

DOI：10.16640/j.cnki.37-1222/t.2017.04.134

1 引言

移動(dòng)電子商務(wù)的位置選擇具有隨機(jī)性、便利性、區(qū)域性以及個(gè)性化等特點(diǎn)，使得顧客的需求呈現(xiàn)出多樣化、個(gè)性化、批量小、次數(shù)多等特征，給物流快遞企業(yè)的取貨過程增加了一定難度。顧客通過移動(dòng)電子商務(wù)平臺(tái)下訂單、取消或改變訂單等信息可能會(huì)使原定制的取貨路徑方案變的次優(yōu)甚至不可行，因此物流快遞企業(yè)調(diào)度中心應(yīng)根據(jù)平臺(tái)上出現(xiàn)的新信息不斷的與原信息進(jìn)行合并，對顧客需求的變化作出及時(shí)響應(yīng)，快速調(diào)整車輛路徑，滿足顧客需求。因此，鑒于上述背景，本文主要針對移動(dòng)電子商務(wù)下的動(dòng)態(tài)車輛路徑問題，將動(dòng)態(tài)車輛路徑問題轉(zhuǎn)化一系列靜態(tài)車輛路徑問題問題，建立問題模型后利用貪心算法進(jìn)行求解。

2 問題描述及建模

2.1 問題描述

移動(dòng)電子商務(wù)環(huán)境下動(dòng)態(tài)車輛路徑問題的運(yùn)作流程：移動(dòng)電子商務(wù)獲取顧客需求量和顧客位置信息，智能交通系統(tǒng)實(shí)時(shí)獲取交通信息，全球定位系統(tǒng)實(shí)時(shí)定位取貨車輛，基于位置服務(wù)獲取任意兩個(gè)顧客之間的距離。調(diào)度中心根據(jù)移動(dòng)電子商務(wù)平臺(tái)將新信息與原信息結(jié)合生成新的車輛路徑調(diào)度方案，并將指令通過全球移動(dòng)通訊系統(tǒng)傳達(dá)給取貨車輛司機(jī)，及時(shí)改變路線，提高企業(yè)服務(wù)質(zhì)量。

2.2 問題模型

本文僅考慮出現(xiàn)新顧客的情況，解決思路是將不在配送中心的取貨車輛虛擬為一個(gè)顧客，且需求量為當(dāng)前已經(jīng)裝載量，并將該虛擬點(diǎn)設(shè)置為第一個(gè)服務(wù)的顧客，從而將動(dòng)態(tài)車輛路徑問題轉(zhuǎn)變?yōu)殪o態(tài)車輛路徑問題。

移動(dòng)電子商務(wù)環(huán)境下動(dòng)態(tài)車輛路徑問題可以描述為：存在圖其中節(jié)點(diǎn)集合表示1個(gè)配送中心和個(gè)顧客，邊集合表示任意兩節(jié)點(diǎn)的邊，邊長用表示。物流配送中心有輛車，每輛車的裝載能力為，每輛車的最大行駛距離為，整個(gè)取貨過程中出現(xiàn)新信息的次數(shù)為，每個(gè)顧客的需求量為，且（）；新信息出現(xiàn)的時(shí)間為，表示時(shí)末服務(wù)的顧客數(shù)，表示在時(shí)方案中的車輛數(shù)，表示時(shí)正在執(zhí)行取貨任務(wù)的車輛數(shù)量，表示在時(shí)任意兩點(diǎn)之間的距離，表示車輛k從顧客i到顧客j，經(jīng)過則為1，否則為0；v表示車輛平均行駛速度，為保證每輛車均能在周期內(nèi)完成取貨任務(wù)，設(shè)（T為取貨周期），表示動(dòng)態(tài)程度：在取貨過程中，出現(xiàn)的新顧客數(shù)量與總的顧客數(shù)量的比值。

對車輛進(jìn)行動(dòng)態(tài)調(diào)度時(shí)，還應(yīng)滿足以下條件：每輛車都是空載從配送中心出發(fā)，取貨完成后再回到配送中心；顧客只能被一輛車服務(wù)一次；每輛車的裝載能力不能超過；每輛車的行駛距離不能大于。

3 貪心算法設(shè)計(jì)

求解移動(dòng)電子商務(wù)環(huán)境下的動(dòng)態(tài)車輛路徑最大的難點(diǎn)在于取貨過程中會(huì)不斷出現(xiàn)新的信息，所以要求算法的求解速度非?？?。本文利進(jìn)貪心算法求解動(dòng)態(tài)車輛路徑問題，能夠快速的合并新的信息并從全局最優(yōu)的角度出發(fā)得到最優(yōu)解。

貪心算法是通過選擇來得到一個(gè)問題的解，它所做的每一次選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇。貪心算法求解動(dòng)態(tài)車輛路徑的過程是將任意兩節(jié)點(diǎn)構(gòu)成的邊按邊長升序排列有（條邊），從最短邊開始依次添加合法邊至當(dāng)前路徑中，直到添加完所有合法邊，形成每條路徑的兩端點(diǎn)都與配送中心節(jié)點(diǎn)O連接形成Hamilton回路為止。

貪心算法求解動(dòng)態(tài)車輛路徑時(shí)判斷一條邊是否為合法邊的4條準(zhǔn)則：

（1）添加該邊后不會(huì)使所有點(diǎn)連接邊的數(shù)量大于2；

（2）該邊不會(huì)使圖中產(chǎn)生邊數(shù)小于n的圈；

（3）添加該邊生成的單條路徑包含的所有顧客需求總量之和不會(huì)超過C；

（4）添加該邊所在的路徑長度與該路徑兩端點(diǎn)至配送中心的長度之和不會(huì)超過D。

4 結(jié)論

本文針對移動(dòng)電子商務(wù)環(huán)境下的動(dòng)態(tài)車輛路徑問題，將動(dòng)態(tài)車輛路徑問題轉(zhuǎn)化為靜態(tài)車輛路徑問題，建立了取貨車輛調(diào)度問題模型并利用貪心算法進(jìn)行求解。

參考文獻(xiàn)：

[1]劉宇熹，蔣艷.中國移動(dòng)電子商務(wù)發(fā)展研究及其SWOT分析[C]. 2010.

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

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

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

[5]饒衛(wèi)振.大規(guī)模動(dòng)態(tài)車輛路徑問題優(yōu)化方法研究[D].大連理工大學(xué)，2012.

作者簡介：李珊珊（1991-），女，山東德州人，碩士研究生。