王文正

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

0 引言

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

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

1 問(wèn)題描述和模型

1.1 問(wèn)題描述

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

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

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

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

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

（2）以區(qū)域?yàn)閱挝蛔鳛閿U(kuò)建站點(diǎn)候選點(diǎn)，新站點(diǎn)只規(guī)劃到在哪些區(qū)域構(gòu)建，而不具體到區(qū)域中的位置；

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

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

集合

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

T：時(shí)段集合，T={1，2，…，m}。

基本參數(shù)

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

t：時(shí)段索引，t∈T；

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

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

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

dmin：站點(diǎn)的容量下限；

dmax：站點(diǎn)的容量上限。

決策變量

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

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

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

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

模型如下所示：

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

2 算法設(shè)計(jì)

2.1 確定擴(kuò)建站點(diǎn)位置的遺傳算法

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

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

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

（2）初始種群生成。初始化是遺傳算法的第一步，在初始化期間將生成第一代種群。在生成第一代種群中的染色體時(shí)，需要預(yù)先確定一個(gè)值N，即在整個(gè)城市需要擴(kuò)建的新站點(diǎn)數(shù)量，然后從一條染色體的所有基因中隨機(jī)選擇N 個(gè)基因賦值為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)化策略。

選擇過(guò)程采用輪盤賭方法。

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

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

圖2 交叉及交叉策略過(guò)程

2.2 擴(kuò)建站點(diǎn)容量設(shè)置方法

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

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

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

2.4 再平衡方法

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

圖3 不同再平衡方法對(duì)比

3 實(shí)驗(yàn)結(jié)果分析

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

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

表1 擴(kuò)建不同新站點(diǎn)數(shù)量的實(shí)驗(yàn)結(jié)果

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

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

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

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

圖4 場(chǎng)景2-5的擴(kuò)建站點(diǎn)區(qū)域圖

4 結(jié)語(yǔ)

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