基于VRP問題的大學校園共享單車的優化調度

孫啟隆 李文榮 龐曉軍

【摘要】如今，共享經濟以及移動互聯網飛速發展，共享單車已成為我國各大院校學生出行的重要工具。因此，收集、分析學生的騎車需求以及時空特征，對校園共享單車進行優化調度具有重要意義。由于校園內單車騎行的特殊規律性，本文提出結合‘吧三stic模型對騎行高峰期需求量進行合理預測，并利用VRF問題確定調度路線，選擇遺傳算法進行求解，最后以山東師范大學為實例，給出優化調度路線。

【關鍵詞】共享單車 優化調度 Logistic模型 VRP問題 遺傳算法

1、引言

從2016年起，共享單車迅速普及，我國各大院校中也出現了共享單車的身影，為廣大學生提供了便利。但是，校園內共享單車的供需關系及調度問題還存在一定的不合理性。因此，分析學生的騎車需求以及時空特征，對校園共享單車進行優化調度具有重要意義。本文利用VRP（Vehicle Routing Problem）問題研究大學校園共享單車的優化i思度，主要分為數據收集與處理、調度需求預測方法、優化調度模型的建立及求解3個階，段。其中，數據收集以問卷調查和實地調查為主;高峰期的調度需求預測通過結合Logistic模型和實際情況實現;在調度優化模型建立及求解部分，首先進行區域劃分，利用VRP問題確定調度路線，并選擇遺傳算法進行求解。

2、數據收集與處理

數據收集主要通過問卷調查和實地調查的方法。問卷調查的主要目的是得到學生對校園內部單車數量、投放情況的滿意程度，以及騎行的時空特征。實地調查的目的是獲取包括不同時間停放量在;內的校園內各投放點的實際情況。

由于實地調查受到時間限制，所獲取數據并不完整，為了得到較為準確的完整數據，本文選擇將得到的數據通過Matlab利用最小二乘法并結合實際進行非線性擬合，將缺失數據完整化。

3、調度需求預測方法

由于校園內單車的騎行時間受到課程安排的影響，在工作日會表現出明顯的規律性，而在周末，學生自由支配時間，出行相對分散，并沒有呈現出明顯的規律。故在本文中，主要對校園內共享單車在工作日的調度需求進行研究。

3.1 各投放點的單車數量變化

將一天24h分為σ個時間段，每個時間段中單車數量變化服從相同的函數關系，則投放點單車數量隨時間變化的函數關系為周期切換函數：

其中，to為初始時刻，D=5為周期，函數f_i（t）表示在i時段的周轉車輛數滿足的函數關系，且f_i（t）不完全相同。

以某高校上課時間前后的教學樓區投放點為例，該時段以單車騎入為主，騎出量可忽略不計，單車數量變化符臺Logistic模型。

假設單車的增長率函數為：

3.2 調度需求模型的建立

在校園中，學生通常會按照出行時間、距離以及特殊天氣狀況等因素對出行方式進行選擇。因此，首先考慮建立出行方式效用函

4、優化調度模型的建立及求解

4.1 區域劃分

同一時間點，各投放點的需求量及調度量受到空間位置的影響，雖然學校內的投放點較多，但工作日尤其是高峰期時段，投放點之間存在明顯的規律性。故可將投放點所在區域根據關聯關系進行分組，對區域進行劃分，從而簡化問題。

4.2 優化調度模型的建立

4.2.1 模型假設及符號說明

假設1：區域i到區域j之間的距離取區域i中心到區域j中心的歐氏距離;

假設2：每輛調運車容量相同，最多裝載G輛共享單車;

假設3：運送每臺單車單位距離所需成本相同;

假設4：調度任務在高峰期之前的規定時間內完成。

4.2.2 基于VRP問題的單車優化調度模型的建立

假設有K個投放點需要進行調酉己，從調度中心K₀派出M輛調度車，在規定時間內去往各投放點，完成調度任務，最后返回調度中心K₀。

設y_ijm為調度車m從投放點i到投放點j運送的單車數量，則M輛調度車的單車調度成本之和C為：

其中，距離取歐氏距離d_ij，U_c表示運送每臺單車單位距離所需

5、實際算例

以山東師范大學內青桔單車為例，基于上述模型對學生的騎車需求進行收集分析，對校園共享單車進行優化調度。

5.1 數據收集及處理。對2019年12月3日—2019年12月7日校園中各投放點的實地調查數據進行‘整理，以2019年12月5日的實地調查結果為例進行數據缺失處理。

通過Matlab利用最小二乘法并結合實際進行非線性擬合得到最終數據如表3所示：

5.2 調度需求模型的檢驗。根據上述7：00-9：00的B區投放點單車數，利用Logistic模型求得該高峰期時段單車數隨時間的變化，并將該數據與實際數據進行比較，得到下圖：

其中，紅色曲線為Logistic模型下單車數量變化曲線，藍色折線由實際數據連接而成，容易看到模型與實際變化趨勢大致相同，且誤差在5輛內波動，故可用來預測高峰期的單車數量。

5.3 優化調度模型的建立與求解

由于在高峰期時段，學生的路線主要是從宿舍樓所在投放點至文淵教學樓區。對此，調度任務是將閑置的車輛提前運送到各宿舍樓投放點。

由于學校宿舍樓總區域占地面積及所跨坡度較大，不妨按照宿舍區域的命名，將宿舍樓投放點區域進行劃分。假設校園中有10個投放點需要調度，根據上述區域劃分方法，將10個投放點分為3個調度區域，分別由3輛最大載車輛為30的調度車進行調度。

利用4.2中的優化調度模型，取100為該算法的迭代次數，初始種群個數為8，交叉概率為0.9，變異概率為0.2，通過Matlab完成遺傳算法。從圖中可以看出，該遺傳算法在迭代50次后開始收斂，在迭代100次后收斂。

求解結果為啟用3輛調度車，調度路徑分別為：1→2→1，1→8→7→6→5→1，1→3→4→1，總長度為1567.9m。其中，1、2、3、4、5、6、7、8分別為以下投放點的編號：文淵教學樓B區、梅苑中心投放點（4#）、圖書館、8#投放點、10#投放點、英華樓投放點、18#投放點、20#投放點。

參考文獻：

[1]王嘉薇，朱家明，祁浩宇，李瑞新.沈陽理工大學學報[J].第37卷第1期2018.81-86.

[2]于夢，蘇春芝，于桂芳，劉思雨，趙宇玲，蘭慧，萬曼曼[J].河北中醫藥學報。第35卷第1期2020.12-15.

[3]史越.共享單車需求預測及調度方法研究[D].北京：北京交通大學.2019.

特別感謝：山東師范大學數學與統計學院的李海濤教授對該論文的修改所提供的建議，以及大學生創新創業項目2019130211的資助。

作者簡介：孫啟隆（1999-），女，山東曲阜人，大學本科在讀，研究方向為信息與計算科學。李文榮（2000-），女，山東肥城人，大學本科在讀，研究方向為數學與應用數學。龐曉軍（1999-），女，山東聊城人，大學本科在讀，研究方向為數學與應用數學。