[發明專利]一種基于多層次分區的公共自行車高峰期調度方法

在審

• 申請號: 201610039835.7
• 申請日: 2016-01-21
• 公開（公告）號: CN105719083A
• 公開（公告）日: 2016-06-29
• 發明（設計）人: 馬瑩瑩;秦筱然;葉欽海
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q30/06;G06N3/12
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 羅觀祥

1.一種基于多層次分區的公共自行車高峰期調度方法，其特征在于，包括以下步驟：

1)選定研究范圍，采集基礎資料，包括規劃資料、各租賃點的設施資料、需求資料，其中，所述規劃資料包括規劃租賃點位置、各租賃點規劃配備車輛數和租賃點用地性質類型，該租賃點用地性質類型主要分為交通樞紐、公交中途站、公建商業類、居住類和休閑類五類；所述各租賃點的設施資料指實際鎖車樁數；所述需求資料指該租賃點早晚高峰短時段內公共自行車相對準確的借還量，一般記借車量為公共自行車出行發生量，為正值，而還車量為出行吸引量，為負值；

2)確定上層調度區域，分析各租賃點鎖車樁數和借還需求關系，通過各點間車輛流動關聯度將周圍租賃點納入調度區域，直至上層調度區域內為公共自行車高峰期主要流動范圍；

3)在調度區域內進行小區劃分，根據各租賃點高峰期運營數據，結合聚類分析和人工調整方法進行小區劃分和編號；

4)確定區間調度方案：根據步驟3)的小區劃分結果，統計各小區高峰期短時段內總需求量以及小區各租賃點中最早的時間要求，代入調度模型中計算得到區間調度方案；

5)確定區內固定調度方案：根據各小區區內租賃點的分布和道路條件，利用最短路模型進行區內固定調度路線的確定，并結合小區內各租賃點的短時段需求量確定區內調度方案；

6)結合區間和區內調度方案制定高峰期整體方案。

2.根據權利要求1所述的一種基于多層次分區的公共自行車高峰期調度方法，其特征在于：在步驟2)中，分析確定上層調度區域的主要步驟包括：

2.1)判斷各租賃點的高峰期每10分鐘需求量和其鎖車樁數量的差異，若差值超過鎖車樁數量的一半，則將其作為供不應求的調度需求點；

2.2)通過公共自行車借還刷卡數據或預約數據，得到調度需求點主要自行車流向租賃點或自行車吸引租賃點，將其納入上層調度區域內；

2.3)判斷調度區域內租賃點互為主要吸引、發生租賃點，即流入和流出調度區域的公共自行車較少時，停止納入新租賃點；

2.4)判斷調度區域內租賃點個數，較多則剔除部分租借關聯度較低的租賃點，最終確定調度區域范圍；

在步驟3)中，小區劃分的主要步驟包括：

3.1)輸入步驟2)得到的調度區域內各租賃點高峰期每10分鐘的需求數據，利用SPSS軟件進行聚類分析，將高峰期借還特性相近的租賃點歸為一類；

3.2)根據聚類結果，結合設計人員經驗判斷，將聚類相同且距離不大于300米的公共自行車租賃點劃分為一個小區；

3.3)判斷小區內租賃點個數N，若N>6，則剔除部分距離較遠的租賃點另劃分為一區，否則確定小區范圍及內部租賃點，對小區進行編號a∈{a₁,a₂,...,a_m}，同時對小區內部租賃點進行標號b_a∈{b_a1,b_a2,...,b_an}；

在步驟4)中，確定區間調度方案的主要步驟包括：

4.1)統計各小區高峰期每10分鐘的需求數據，即小區內所有租賃點每10分鐘需求數據之和，將此數據作為小區需求數據；

4.2)統計各小區內租賃點的最早的時間窗要求，將其作為相應小區的時間窗；

4.3)采取設置虛擬小區的形式，將分區按相同順序多次編號，按高峰期2小時計算，每10分鐘統計一次需求量，最多來回調度12次，則以小區個數M為一個周期，循環12個周期編號，即a小區及其虛擬點編號集合為A＝{a,a+M,a+2M,...,a+11M}；

4.4)繪制高峰期期間所有小區的各時段時間窗需求表，其中應包括所有小區編號、形心坐標、鎖車樁數、需求量和時間區間；

4.5)根據調度的實際情況，考慮運輸車輛的固定成本、行駛成本以及客戶的滿意度，建立目標函數：

minZ=C0Σj=1nΣk=1mx0jk+C1Σi=0nΣj=0nΣk=1mdijxijk+C2P[Σi=1nΣk=1mmax(ti-li,0)+Σi=1nΣk=1mmax(ei-ti,0)]]]>

其中，表達式等號右邊第一部分為固定成本，其取值與人工費用、車輛折舊費用、車輛其它固定費用有關；第二部分為行駛成本，其取值與車輛單位油耗、租賃點間直線距離、城市道路直線系數有關；第三部分為懲罰成本，其取值與運輸車輛到達服務點的實際時間、租賃點規定的服務時間、乘客等待時間有關；

4.6)根據既定目標函數以及實際調度情況，確定模型的約束條件如下：

①運輸車輛必須從中心車場出發

②運輸車輛必須回到中心車場

③運輸車輛經過某一小區時，其調度量加上運輸車輛原有的載運量不小于0且不大于運輸車輛的最大載運能力0≤ω_ijk-q_j≤Q；其中，ω_ijk≥0、i,j∈Nk∈{1,2,...,m}；

④進入某小區的車輛，必須要從該小區離開

⑤每個小區只有一輛車服務

⑥任一小區的需求量不大于調度車輛的容量0≤|q_i|y_ik≤Q；

⑦到達小區j的時刻t_j等于到達上一個小區i并開始服務的時刻與該點服務時間與兩點間行程時間t_ij之和t_j＝t_i+t_ij+t_uii,j＝0,1,...,n，t_ij≠0；

⑧到達各小區的上一時間窗的時間必須小于到達該小區下一時間窗的時間t_i＜t_i+M；

上式中：

N：小區編號{0,1,2，…,n}，0代表中心車場；

M：實際小區個數；

K：所需運輸車輛數{1,2，…,m}；

d_ij：小區i到小區j的直接距離，假設d_ij＝d_ji；

q_i：小區i的調度量，調出為負，調入為正；

ω_ijk：運輸車輛k從租賃點i到租賃點j車上的載運量；

l_i：小區i的最晚服務時間；

e_i：小區i的最早服務時間；

t_i：運輸車輛到達小區i的時間；

t_j：運輸車輛到達小區j的時間；

t_ij：運輸車輛從小區i到達小區j的時間；

t_ui：運輸車輛在小區i的裝卸時間；

P：時間懲罰系數，與乘客的等待時間成正相關關系；

C₀：運輸車輛的固定成本；

C₁：運輸車輛單位里程的成本費用；

C₂：等待時間的成本費用；

4.7)采用遺傳算法對模型進行求解，主要步驟如下：

①染色體編碼

遺傳算法在進行搜索前，先將解空間的解數據表示成遺傳空間的基因串結構數據，這種從表現型到基因型的映射稱為編碼；適合本次研究調度模型的遺傳編碼方式是符號編碼，具體表示為g＝(w₁,w₂,...,w_N)，其中w表示每個租賃點被哪輛車服務，w_i＝(m-num,s-num)表示第i個租賃點接受車輛編號為m的運輸車輛的配送服務；

②生成初始種群

系統通過染色體的編碼方式來隨機生成一系列染色體，作為最初的初始種群；初始種群的數量視調度區域的規模大小來確定，其取值在50-200之間；

③計算適應度值

本調度模型中，求的是目標函數的最小值，因此將函數值的倒數作為個體的適應度值，函數值越小的個體，適應度值越大，個體就越優；

f_i＝1/Z

④選擇操作

選擇操中從舊群體中以一定概率選擇優良個體組成新的種群，以繁殖得到下一代個體，個體被選中的概率跟適應度值有關，個體適應度值越高，被選中的概率越大；本次研究選擇輪盤賭法，即基于適應度比例的選擇策略，個體ⁱ被選中的概率為其中，f_i為個體i的適應值；N為種群個體數目；

⑤交叉操作

從種群中隨機選擇兩個個體，通過兩個染色體的交換組合，把父串的優秀特征遺傳給子串，從而得到新的優秀個體；

⑥變異操作

從種群中隨機選取一個個體，選擇個體中的一點進行變異以產生更優秀的個體；

⑦判斷是否滿足終止條件；停止規則一般為最大進化代數；或算法在連續進化一定代數后，解的適應度沒有明顯改進；

4.8)整理求解得到的調度順序和各租賃點應調度的車輛數，制定小區間調度路線方案；

在步驟5)中，確定區內固定調度路線的主要步驟包括：

5.1)采集小區內各租賃點周邊道路高峰期交通量數據，以及各租賃點間的連接道路長度；分別對兩類數據進行分級賦值，數據最大值賦5，最小值賦1，中間數值根據比例關系賦值，保留兩位有效數字；

5.2)將各租賃點間每條連接道路的交通量等級值和道路長度等級值求和，作為該條連接道路的阻抗

式中：Q_ijk——小區內租賃點i至租賃點j間第k條連接道路的交通量等級值；

L_ijk——小區內租賃點i至租賃點j間第k條連接道路的長度等級值；

5.3)比較小區內租賃點i至租賃點j所有連接道路的阻抗值，取最小者作為租賃點i和租賃點j間的路徑，其阻抗

5.4)為確保區內服務點有且僅有一次均被服務到，建立最優路徑模型，代入道路阻抗值求得小區內固定最優路徑：

s.t.x_ij+x_ji≤1

Σi=1MXij=1]]>

Σj=1MXij=1]]>

i≠j

式中：Ω——小區內調度總阻抗值；

5.5)根據步驟5.4)得到的最優調度順序，結合步驟5.3)中最小阻抗值道路，確定區內調度路線；

5.6)結合各租賃點的需求數據制定區內調度方案。

3.根據權利要求1所述的一種基于多層次分區的公共自行車高峰期調度方法，其特征在于：在步驟6)中，將區內調度方案銜接于區間調度之后，形成從小區到租賃點的完整調度方案。