基于VRP問題的大學校園共享單車的優(yōu)化調(diào)度

孫啟隆 李文榮 龐曉軍

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

【關鍵詞】共享單車 優(yōu)化調(diào)度 Logistic模型 VRP問題 遺傳算法

1、引言

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

2、數(shù)據(jù)收集與處理

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

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

3、調(diào)度需求預測方法

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

3.1 各投放點的單車數(shù)量變化

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

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

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

假設單車的增長率函數(shù)為：

3.2 調(diào)度需求模型的建立

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

4、優(yōu)化調(diào)度模型的建立及求解

4.1 區(qū)域劃分

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

4.2 優(yōu)化調(diào)度模型的建立

4.2.1 模型假設及符號說明

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

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

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

假設4：調(diào)度任務在高峰期之前的規(guī)定時間內(nèi)完成。

4.2.2 基于VRP問題的單車優(yōu)化調(diào)度模型的建立

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

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

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

5、實際算例

以山東師范大學內(nèi)青桔單車為例，基于上述模型對學生的騎車需求進行收集分析，對校園共享單車進行優(yōu)化調(diào)度。

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

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

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

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

5.3 優(yōu)化調(diào)度模型的建立與求解

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

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

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

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

參考文獻：

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

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

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

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

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