王文正

（安徽工業(yè)大學(xué)管理科學(xué)與工程學(xué)院，馬鞍山243000）

0 引言

共享單車的推出為社會和用戶帶了諸多好處：緩解了城市交通擁堵和污染問題，解決了地鐵和公共交通存在的“最后一公里”問題[1]，完善了城市交通體系。但其在火爆的同時也催生了大量的問題，如在不同時段，不同位置的站點是否有足夠的空停車樁或單車供用戶使用，站點的規(guī)模大小、分布密度是否合理等。共享單車站點選址規(guī)劃問題一直是共享單車系統(tǒng)研究的重點之一，目前國內(nèi)外的研究方法主要分為定性和定量兩類。定性方法從城市功能分區(qū)及配套設(shè)施建設(shè)角度來規(guī)劃站點位置[2-3]，一般建議將站點布局在居民區(qū)、商業(yè)區(qū)、交通站、游樂區(qū)和校園等附近，進(jìn)一步的定性研究是根據(jù)某些評估標(biāo)準(zhǔn)對候選站點進(jìn)行評分來獲取規(guī)劃位置[4-5]。定量方法大多參考設(shè)施選址模型，即決策變量一般使用候選點位置、站點的單車數(shù)或站點容量來表示[6-8]。

本文在原有共享單車系統(tǒng)的基礎(chǔ)上加入再平衡來研究擴建站點選址規(guī)劃問題，確定更加合理的擴建站點位置及設(shè)施配置，彌補選址規(guī)劃中的布局不合理及調(diào)度困難問題，提高共享單車系統(tǒng)的工作效率和用戶滿意度。

1 問題描述和模型

1.1 問題描述

站點選址規(guī)劃的主要研究內(nèi)容包括：確定站點建設(shè)的數(shù)量；確定站點建設(shè)的位置；確定各站點單車數(shù)量和容量（停車樁數(shù)量）。再平衡是指在共享單車的運營過程中，對處于空載或滿載的站點進(jìn)行共享單車的調(diào)入或調(diào)出操作，解決用戶“到達(dá)站點無法借車或還車”的問題。

在擴建站點選址規(guī)劃中考慮再平衡因素，可以有效滿足用戶借還車需求，提高用戶滿意度，緩解因站點分布不合理而導(dǎo)致的再平衡路線選擇困難問題，減輕再平衡系統(tǒng)的壓力并提高共享單車系統(tǒng)的工作效率。本文研究的問題可描述為：在一個現(xiàn)有共享單車系統(tǒng)的研究區(qū)域，給定一組新站點的候選點，在滿足用戶借還車需求的約束下，確定在哪些候選點建設(shè)新站點及站點的容量規(guī)模，并給定站點間的再平衡方案，以達(dá)到最小化再平衡量的目的。

1.2 數(shù)學(xué)模型

本文做出以下假設(shè)：

（1）以一天為一個基本時間段，每個時段結(jié)束（24時）實施再平衡；

（2）以區(qū)域為單位作為擴建站點候選點，新站點只規(guī)劃到在哪些區(qū)域構(gòu)建，而不具體到區(qū)域中的位置；

（3）每個區(qū)域的用戶借還車需求量是已知的。

數(shù)學(xué)符號如下所示：

集合

Z：區(qū)域集合，Z={1，2，…，n}；

T：時段集合，T={1，2，…，m}。

基本參數(shù)

i，j：區(qū)域索引，i，j∈Z；

t：時段索引，t∈T；

ci：區(qū)域i 的原有站點總?cè)萘浚?/p>

fit：區(qū)域i 在t 時段的借車需求量；

git：區(qū)域i 在t 時段的還車需求量；

dmin：站點的容量下限；

dmax：站點的容量上限。

決策變量

xi：如果選擇在區(qū)域i 建造新站點則為1，否則為0；

di：建在區(qū)域o 的新站點容量；

bit：區(qū)域i 在時段t 開始時刻的單車數(shù)量；

rijt：在t 時段結(jié)束時從區(qū)域i 向區(qū)域j 進(jìn)行再平衡的單車數(shù)量。

模型如下所示：

目標(biāo)函數(shù)（1）為最小化共享單車系統(tǒng)的再平衡總量。約束（2）定義了在時段t 初始時刻區(qū)域i 的單車數(shù)量要在區(qū)域總?cè)萘恐畠?nèi)。約束（3）定義了在時段t 初始時刻區(qū)域i 的單車數(shù)量。它是時段t-1 初始時刻的單車數(shù)量加上時段t-1 期間的需求量（在區(qū)域i 的還車量與借車量之差）加上時段t-1 期間的再平衡數(shù)量。約束（4）定義了新站點的容量要在一定范圍內(nèi)。約束（5）定義了時段t 區(qū)域i 必須有足夠的單車以滿足借車需求。約束（6）定義了在時段t 區(qū)域i 必須有足夠的空樁以滿足還車需求。約束（7）定義了在時段t 區(qū)域i 向其他區(qū)域進(jìn)行再平衡調(diào)動的單車數(shù)量要小于或等于區(qū)域i存在的單車數(shù)量。約束（8）定義了在時段t 其他區(qū)域向區(qū)域i 進(jìn)行再平衡調(diào)動的單車數(shù)量要小于或等于區(qū)域i存在的空樁數(shù)量。約束（9）和（10）是對決策變量的約束。

2 算法設(shè)計

2.1 確定擴建站點位置的遺傳算法

本文通過改進(jìn)遺傳算法的進(jìn)化策略來確定新站點的位置，在算法中設(shè)計了適用于擴建站點選址的交叉策略和變異策略，以防止不可行解的產(chǎn)生，從而保證了擴建站點數(shù)量的不變性。

（1）編碼。染色體上的每個基因代表一個區(qū)域。如果基因值為1，則將在該區(qū)域中擴建新站點，如果基因值為0，則不會在該區(qū)域建造站點。圖1 為具有六個區(qū)域的染色體結(jié)構(gòu)示例，其中將會在第1、3、4 和6 區(qū)域擴建新站點。

圖1 擁有6個區(qū)域的染色體結(jié)構(gòu)示例

（2）初始種群生成。初始化是遺傳算法的第一步，在初始化期間將生成第一代種群。在生成第一代種群中的染色體時，需要預(yù)先確定一個值N，即在整個城市需要擴建的新站點數(shù)量，然后從一條染色體的所有基因中隨機選擇N 個基因賦值為1，其余為0。按此方法生成M 條染色體后結(jié)束初始化。

（3）適應(yīng)度函數(shù)。目標(biāo)函數(shù)為再平衡總數(shù)量最小，目標(biāo)函數(shù)f（x）越小的染色體被“選擇”的概率越大，因此選擇目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。

（4）進(jìn)化策略。

選擇過程采用輪盤賭方法。

交叉過程是產(chǎn)生新個體的主要方式。由于每條染色體中有N 個值為1 的基因，因此大多數(shù)傳統(tǒng)的交叉策略都會產(chǎn)生非法染色體，為了保持?jǐn)U建站點總數(shù)量不變，本節(jié)設(shè)計了一個交叉策略，該策略的步驟為：先隨機選擇兩個染色體；然后根據(jù)交叉比例概率在兩條染色體中找到一定數(shù)量對應(yīng)位置數(shù)值不同的基因位，并在兩條染色體之間交換對應(yīng)基因位的數(shù)值。

變異策略主要有兩個目的：一是使遺傳算法具有局部隨機搜索能力，二是使遺傳算法保持種群的多樣性以防止早熟收斂。為了在每條染色體上保留N 個值為1 的基因，本節(jié)設(shè)計了一個變異策略：在染色體中隨機找到一個值為0 的基因和一個值為1 的基因，然后互相交換。交叉及變異策略的過程如圖2 所示。

圖2 交叉及交叉策略過程

2.2 擴建站點容量設(shè)置方法

擴建站點容量設(shè)置方法是將區(qū)域中所有原有站點的平均容量作為新站點的容量，其原因是因為同一區(qū)域功能屬性和面向的用戶群體大致相同。例如，在人口流量較大的商業(yè)區(qū)，原有站點的容量通常很高，因此在建新站點時也往往要設(shè)置較高的容量。擴建站點容量設(shè)置方法如公式（12）所示，其中，di是在區(qū)域i 擴建站點的容量，ci為區(qū)域i 原有站點的容量總和，crad（Si）是區(qū)域i 包含原有站點的數(shù)量。

2.3 初始單車數(shù)量設(shè)置方法

區(qū)域在初始時刻的單車數(shù)量將根據(jù)用戶借還需求的比例來設(shè)置，例如一個區(qū)域的借車需求量與還車需求量為3:1，該區(qū)域的總?cè)萘繛?0，那么初始時刻的單車數(shù)量設(shè)置為15（20÷4×3）輛。該方法如公式（13）所示，其中，bi是區(qū)域i 在初始時刻的單車數(shù)量，di+ci為區(qū)域i 的容量總和，fi為區(qū)域i 的借車需求量，gi為區(qū)域i的還車需求量。

2.4 再平衡方法

再平衡方法采用問題站點優(yōu)先再平衡原則，問題站點是指當(dāng)前單車或空停車樁數(shù)量無法滿足下一時段用戶需求的站點。當(dāng)一個時段結(jié)束時，優(yōu)先在問題站點（需要調(diào)出單車和調(diào)入單車的站點）之間進(jìn)行再平衡，然后再從問題站點和非問題站點之間進(jìn)行再平衡。如圖3 為不同再平衡方法的對比，站點1（S1）為需要調(diào)出5 輛單車才能滿足下一時段用戶需求的問題站點，站點4（S4）為調(diào)入10 輛單車的問題站點。采用問題站點優(yōu)先再平衡的方法只需搬運總共10 輛單車即可完成再平衡，比就近再平衡方法少了5 輛。

圖3 不同再平衡方法對比

3 實驗結(jié)果分析

本文使用Python 3.6 進(jìn)行編程，所有實驗均在配置為Intel Core i7-7700HQ CPU @2.80 GHz、8GB 內(nèi)存、Windows10 64 位操作系統(tǒng)的迅龍筆記本電腦上進(jìn)行。數(shù)據(jù)使用來自紐約花旗單車2019 年3 月1 日-3 月7日的用戶出行數(shù)據(jù)。區(qū)域設(shè)置方法按照人口普查區(qū)劃分，將每一個人口普查小塊看作一個區(qū)域。

表1 為擴建不同數(shù)量新站點的實驗結(jié)果，其中場景1 是不擴建新站點的實驗，場景2-5 分別為擴建30、50、80 和120 個新站點的實驗結(jié)果。圖4 中的a-d 分別為場景2-5 的擴建站點區(qū)域圖，每個擴建區(qū)域上的數(shù)字為擴建站點的容量。

表1 擴建不同新站點數(shù)量的實驗結(jié)果

場景1 作為對照組不擴建任何站點，原有系統(tǒng)總共有12442 輛單車，停車樁總數(shù)量為25258 個，在3 月1 日-7 日的再平衡總量為566 輛。

場景2 為在所有區(qū)域中選擇區(qū)域擴建30 個新站點，通過所提方法計算完成后的最優(yōu)再平衡總量為456輛，即在擴建30 個新站點的情況下，相比于場景1，場景2 的共享單車系統(tǒng)在3 月1 日-3 與7 日的再平衡總量降低了110 輛，擴建的30 個新站點中投放了800 輛單車，設(shè)置了976 個停車樁。

場景3 為在所有區(qū)域中選擇區(qū)域擴建50 個新站點，最優(yōu)再平衡總量為404 輛，較場景1 降低了162輛，擴建的50 個新站點中投放了1112 輛單車，設(shè)置了1641 個停車樁。場景4 為在所有區(qū)域中選擇區(qū)域擴建80 個新站點，最優(yōu)再平衡總量為335 輛，較場景1 降低了231 輛，擴建的80 個新站點中投放了1534 輛單車，設(shè)置了2495 個停車樁。場景5 為在所有區(qū)域中選擇區(qū)域擴建120 個新站點，最優(yōu)再平衡總量為289 輛，較場景1 降低了277 輛，擴建的120 個新站點中投放了2264 輛單車，設(shè)置了3879 個停車樁。

從結(jié)果中可以看出，通過考慮再平衡擴建新站點可以有效地降低單車運營中的再平衡數(shù)量，滿足更多用戶的借還車需求。當(dāng)運營商指定下一步要擴建的站點數(shù)量時，所提方法可以快速地找出在哪些區(qū)域構(gòu)建新站點更加合理，并給出新站點的配置參數(shù)。

圖4 場景2-5的擴建站點區(qū)域圖

4 結(jié)語

本文針對共享單車擴建站點選址規(guī)劃問題，建立了一個以最小化再平衡量為目標(biāo)的優(yōu)化模型，并使用優(yōu)化算法確定擴建新站點的位置，然后提出了確定單車數(shù)量和站點容量的方法，最后通過實驗證明所提方法可以有效地找出在哪些區(qū)域構(gòu)建新站點更加合理，并給出新站點的配置規(guī)模。但是該方法只確定在哪些區(qū)域構(gòu)建新站點，而沒有具體到區(qū)域中的哪個位置，下一步將會根據(jù)每個區(qū)域的原有站點的分布，人口流動性及建筑設(shè)施屬性相關(guān)聯(lián)，給出新站點在區(qū)域中的具體建設(shè)位置。