移動電子商務環境下取貨車輛調度問題模型研究

摘 要：針對移動電子商務環境下的動態車輛路徑問題，本文將動態車輛路徑問題轉化為靜態車輛路徑問題，建立問題模型，并利用貪心算法進行求解。

關鍵詞：移動電子商務；車輛調度；模型；貪心算法

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

1 引言

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

2 問題描述及建模

2.1 問題描述

移動電子商務環境下動態車輛路徑問題的運作流程：移動電子商務獲取顧客需求量和顧客位置信息，智能交通系統實時獲取交通信息，全球定位系統實時定位取貨車輛，基于位置服務獲取任意兩個顧客之間的距離。調度中心根據移動電子商務平臺將新信息與原信息結合生成新的車輛路徑調度方案，并將指令通過全球移動通訊系統傳達給取貨車輛司機，及時改變路線，提高企業服務質量。

2.2 問題模型

本文僅考慮出現新顧客的情況，解決思路是將不在配送中心的取貨車輛虛擬為一個顧客，且需求量為當前已經裝載量，并將該虛擬點設置為第一個服務的顧客，從而將動態車輛路徑問題轉變為靜態車輛路徑問題。

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

對車輛進行動態調度時，還應滿足以下條件：每輛車都是空載從配送中心出發，取貨完成后再回到配送中心；顧客只能被一輛車服務一次；每輛車的裝載能力不能超過；每輛車的行駛距離不能大于。

3 貪心算法設計

求解移動電子商務環境下的動態車輛路徑最大的難點在于取貨過程中會不斷出現新的信息，所以要求算法的求解速度非常快。本文利進貪心算法求解動態車輛路徑問題，能夠快速的合并新的信息并從全局最優的角度出發得到最優解。

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

貪心算法求解動態車輛路徑時判斷一條邊是否為合法邊的4條準則：

（1）添加該邊后不會使所有點連接邊的數量大于2；

（2）該邊不會使圖中產生邊數小于n的圈；

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

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

4 結論

本文針對移動電子商務環境下的動態車輛路徑問題，將動態車輛路徑問題轉化為靜態車輛路徑問題，建立了取貨車輛調度問題模型并利用貪心算法進行求解。

參考文獻：

[1]劉宇熹，蔣艷.中國移動電子商務發展研究及其SWOT分析[C]. 2010.

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

[3]王旭，葛顯龍，代應.基于兩階段求解算法的動態車輛調度問題研究[J].控制與決策，2012（02）：175-181.

[4]熊浩，胡列格.多車型動態車輛調度及其遺傳算法[J].系統工程，2009（10）：21-24.

[5]饒衛振.大規模動態車輛路徑問題優化方法研究[D].大連理工大學，2012.

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