基于遺傳算法的公共自行車調(diào)度優(yōu)化

劉兆仁，徐冠宇，尹 航

（1.西南交通大學 經(jīng)濟管理學院，四川 成都 610031；2.四川旅游學院 信息與工程系，四川 成都 610100）

基于遺傳算法的公共自行車調(diào)度優(yōu)化

劉兆仁1，徐冠宇1，尹 航2

（1.西南交通大學 經(jīng)濟管理學院，四川 成都 610031；2.四川旅游學院 信息與工程系，四川 成都 610100）

伴隨著低碳經(jīng)濟的發(fā)展和人們環(huán)保意識的不斷增強，城市居民對于綠色出行越來越重視，城市公共自行車逐漸在各大中型城市普及，如何高效調(diào)度公共自行車成為亟待解決的問題。在對公共自行車調(diào)度問題進行分析的基礎上，利用遺傳算法建立VRP模型，最后采用標準算例針對算法進行檢驗，結果表明遺傳算法具有較高效率，能夠有效求解自行車調(diào)度模型。

公共自行車；遺傳算法；VRP；調(diào)度優(yōu)化

1 引言

中國是典型的人口大國，是世界上擁有自行車數(shù)量最多的國家。截至2016年底，全國自行車保有量達3.7億輛，自行車在中國人民的日常生活中扮演重要的角色。近年來，隨著居民財富不斷增加和生活質(zhì)量的不斷提高，私家車出行成為許多居民首選的交通方式。然而，私家車的增加給城市發(fā)展造成諸多問題，交通擁堵、環(huán)境惡化等已經(jīng)成為我國大中型城市亟待解決的問題。

為此，許多城市開始大力發(fā)展公共交通，并采取諸如建設公交專用道、換乘免費等一系列措施引導市民選擇公共交通方式出行。這些措施對于緩解交通擁堵問題起到不錯的效果。但由于公交站點的數(shù)量總是有限的，很難保證乘客走出家門或到站后就能馬上到達目的地，這也就形成了“城市最后一公里”問題。為改善乘客公共交通出行質(zhì)量，提高公共交通選擇粘性，國內(nèi)部分城市開始試行“城市公共自行車租賃系統(tǒng)”。歐美等發(fā)達國家的實踐表明，發(fā)展城市公共自行車租賃系統(tǒng)能夠與公共交通相輔相成，從根本上解決城市交通擁堵問題。

公共自行車交通系統(tǒng)（Public Bicycle System，PBS）一般由政府和自行車企業(yè)合作構建、運營。其中，政府起主導作用，負責制定PBS宏觀規(guī)劃；自行車企業(yè)則著眼于微觀，負責布點、調(diào)度、運行和維護。租賃點大多設置在人流較大的地方，如居住區(qū)、公共交通或軌道交通站點附近、旅游景點、學校等等，主要服務于短途出行。自2008年以來，我國一、二線城市開始普及公共自行車，公共自行車逐漸成為城市居民出行的重要組成板塊。與此同時，城市公共自行車系統(tǒng)在發(fā)展過程中也面臨諸多問題，如運營模式、布局選址和車輛調(diào)度等。能否妥善解決城市公共自行車系統(tǒng)發(fā)展過程中遇到的難題對于發(fā)展我國城市公共交通具有重大意義。

為解決城市公共自行車調(diào)度問題，本文運用遺傳算法，建立解決靜態(tài)VRP問題模型，并采用標準算例進行優(yōu)化求解。

2 公共自行車調(diào)度分析

公共自行車調(diào)度是指在租賃點處自行車過多或不足的情況下，使用調(diào)度車輛有序通過這些租賃點進行自行車補給或調(diào)出，目標是保證城市公共自行車系統(tǒng)能夠達到持續(xù)、相對穩(wěn)定的均衡狀態(tài)。本文采用靜態(tài)調(diào)度的方式，每天晚上由營運商派出車輛將公共自行車站點的車輛復原，以便市民出行[1]。

2.1 發(fā)展機遇

（1）交通需求。隨著社會經(jīng)濟的高速發(fā)展和居民生活水平的不斷改善，城市私家車擁有量急劇增長，盡管近年來一、二線城市普遍采取限號出行措施，但交通擁堵問題依然未能很好地解決。雖然我國近年來不斷開發(fā)城市公共交通，地鐵和快速公交的開通一定程度上緩解了城市交通壓力，但公共自行車的發(fā)展是對于現(xiàn)有公共交通的補充，對于完善“最后一公里”出行具有重要的意義，城市公共自行車系統(tǒng)的出現(xiàn)是應當前交通發(fā)展的需求而生，具有廣闊的市場[2]。

（2）政策支持。發(fā)展綠色出行交通受到當前環(huán)保政策的支持，國家“十二五規(guī)劃”明確提出保護環(huán)境的方針政策，發(fā)展城市公共自行車系統(tǒng)符合當前社會發(fā)展的趨勢[3]。

2.2 存在的問題

（1）運營模式。目前公共自行車運營模式隨著各地區(qū)經(jīng)濟文化的差異而采取了不同的方式，有的城市采用政府主導模式，政府在運營中發(fā)揮主導作用，但往往技術更新方面存在缺陷；有些城市采用企業(yè)主導模式，能夠最大化經(jīng)濟效益，但會在一定程度上忽視居民需求。

（2）網(wǎng)絡規(guī)劃。大部分城市目前的公共自行車租賃點較少，網(wǎng)絡規(guī)劃不充分，不能夠完全滿足日益增長的群眾需求，也在一定程度上影響了運營公司在后期階段的車輛調(diào)度。

（3）運營調(diào)度。當前城市自行車車輛調(diào)度措施仍然存在一定的問題，在車輛使用密集時段經(jīng)常會出現(xiàn)無車可借的尷尬情況，在部分集中站點，也會出現(xiàn)無處還車的情況。車輛的調(diào)度對于客戶滿意率造成極大影響。

2.3 運營調(diào)度的特性

城市公共自行車具有時間分布性和空間分布性兩大特點。時間分布性是指在同一個區(qū)域，自行車流量峰值一天內(nèi)將會達到四次，其中兩次大峰值出現(xiàn)在早晚上下班高峰期，兩次小峰值則出現(xiàn)在中午前后。城市公共自行車系統(tǒng)是為了迎合城市居民出行的需求而建立的，其運營時間與城市居民出行的時間有極強的相關性。在早高峰階段，自行車的流向大多數(shù)是寫字樓、產(chǎn)業(yè)園等；與之相反，在晚高峰時，自行車則從寫字樓、產(chǎn)業(yè)園流向居住區(qū)?？梢姡孕熊嚵骶哂休^為明顯的潮汐性特點[4]。

空間的分布性是指同一時間內(nèi)不同空間自行車需求量的不同。早晨設立于住宅區(qū)和郊區(qū)的自行車租賃站點的租用需求較大，位于地鐵口和商業(yè)區(qū)的租賃點還車需求較大，相反，到晚上，市民由商業(yè)區(qū)和公交樞紐向住宅區(qū)流動。隨著時間的變化，整個城市范圍內(nèi)的自行車會有明顯的空間位移，在不同的時間段，會有不同的空間分布，具有一定的規(guī)律可循。

通過以上分析，在兩次大高峰時段，不同租賃點之間實現(xiàn)了公共自行車的循環(huán)流動，但由于早晚高峰之間時間間隔過長，自行車流動方向性和時間性過于集中，導致一些租賃點公共自行車出現(xiàn)飽和、而其他租賃點卻沒有自行車可以租用的情況。因此，針對這一現(xiàn)實問題，對公共自行車調(diào)度進行優(yōu)化，以促進公共自行車調(diào)度實現(xiàn)全面智能化，不僅能夠有效節(jié)約道路資源、緩解交通擁堵以及由此產(chǎn)生的一系列社會問題，而且對于促進城市健康發(fā)展有重要的意義。

3 構建公共自行車系統(tǒng)靜態(tài)調(diào)度問題模型

3.1 問題描述

靜態(tài)公共自行車調(diào)度問題是指租賃點的自行車調(diào)度不是根據(jù)動態(tài)需求實時改進，而是在每一天的特定時刻，統(tǒng)一對城市區(qū)域內(nèi)的所有站點進行調(diào)度，以滿足租賃點的需求。由于現(xiàn)在城市公共自行車系統(tǒng)與大數(shù)據(jù)系統(tǒng)緊密結合，運營商對于租借出去的車輛流向以及租賃點剩余車輛有精確的實時統(tǒng)計，能夠根據(jù)租賃點的不同需求進行分類服務。

本文假設運營商對于車輛供給不足的租賃點進行統(tǒng)一配送，由中心車場進行逐一訪問，并且最終返回車場。

（1）每個站點只允許被訪問一次；

（2）所有車輛從中心車場出發(fā)，然后再返回到起點；

（3）每個站點的調(diào)度任務必須由一輛車完全滿足。

3.2 模型構建

本文將以成本最低為目標建立模型，成本主要包括車輛的旅行距離，車輛行駛的距離越長，成本越高。

為了方便敘述，本文引入以下符號：

N0租賃站點數(shù)集合{1,...,n}；

N站點集合，包括車場和租賃站點{0,1,...,n,n+1}；

k配送車輛集合{1,...,k}；

C配送車輛的容量上限；

T配送車輛運行時間上限；

在上述條件基礎上，以成本函數(shù)最低為目標，建立以下模型：

Z表示該模型的目標函數(shù)，該模型以成本最低為目標函數(shù)，即車輛在路程中的消費最低；約束（1）表示所有的站點都將被訪問；約束（2）、（3）表示車輛將從配送中心出發(fā)，并將返回配送中心；約束（4）表示車輛流守恒；約束（5）表示避免子環(huán)約束，該模型中不存在子循環(huán)路徑；約束（6）表示配送車輛所配送數(shù)量不能超過被訪問站點的需求總和；約束（7）表示為0-1整數(shù)變量。

3.3 模型求解策略

以往的調(diào)度方法主要分為兩種：基于優(yōu)先規(guī)則的啟發(fā)式算法和基于搜索的算法。然而，這兩者在解決公共自行車優(yōu)化調(diào)度問題時缺點都比較明顯，即它們在解決小規(guī)模調(diào)度問題時是有效的，但面對規(guī)模較大的調(diào)度問題時卻無能為力。

遺傳算法[5]由美國J.H.Holland教授在20世紀70年代提出。該算法是基于生物進化理論的自適應隨機搜索算法，對于求解車輛調(diào)度問題十分有效。車輛調(diào)度問題是遺傳算法應用十分成熟的領域，該算法求解車輛調(diào)度問題的基本步驟為：編碼操作、產(chǎn)生初始種群、計算適應度函數(shù)、遺傳算子（包括選擇、交叉和變異）、終止規(guī)則。

3.3.1 編碼。車輛調(diào)度問題的編碼方式分為兩種：路徑表示法和相鄰表示法。本文采用第一種編碼方式。舉例說明：設某區(qū)域共設有9個自行車租賃點，其中一個可行閉合路徑為[1 4 3 7 2 5 8 6 9 1]，則對應的染色體編碼可表示為1 4 3 7 2 5 8 6 9。

3.3.2 產(chǎn)生初始種群。初始種群是進行遺傳進化操作的第一代種群，由N個個體組成。本文初始種群通過隨機方式生成，將初始種群規(guī)模設定為N=30，由此則隨機生成30個個體，每個個體代表了一個初始解，由于暫沒有進行遺傳進化，因此這一代種群中個體適應度值偏低。3.3.3 計算適應度函數(shù)。適應度函數(shù)是目標函數(shù)在遺傳算法中的反映。在遺傳算法中，適應度值大的個體將有更大概率將優(yōu)良基因信息傳遞給下一代。本文的目標函數(shù)是成本最低，因此本文采用成本的倒數(shù)作為適應度函數(shù)，分母中加1的作用是為了避免成本為0的特殊情況。個體的適應度值可表示為

3.3.4 遺傳算子

選擇：本文依據(jù)種群中不同個體的適應度值采用輪盤賭方式進行選擇，該方案能夠保證適應度高的個體以更大的概率被選中。

交叉：在遺傳算法中，新個體的產(chǎn)生主要依靠交叉操作。本文進行交叉操作時，為使子代依舊為可行解，采用部分匹配交叉法（PMX）：對兩個父代隨機產(chǎn)生2個位串交叉點，兩點間為交叉匹配區(qū)域，然后基于匹配區(qū)域內(nèi)基因的映射關系重新排列區(qū)域外重復基因。舉例如下：

父代染色體

父代1：138丨27丨4965 父代2：726丨45丨8139

交叉匹配

匹配1：138丨45丨4965 匹配2：726丨27丨8139

子代染色體

子代1：138丨45丨2967 子代2：546丨27丨8139

其中，子代1和子代2即為通過部分匹配交叉法獲得的新一代個體。

變異：交叉操作能夠使子代保持父代的優(yōu)良特性，但也會導致算法過早收斂，陷入局部最優(yōu)。變異操作能夠彌補這一缺點，擴大遺傳算法的搜索空間。本文采用對換變異法：首先，隨機選擇染色體的兩個基因，然后交換位置，完成對換變異，舉例如下：

變異前：2 3 8 6 7 1 9 5 4

變異后：2 3 9 6 7 1 8 5 4

3.3.5 終止條件設定。遺傳算法本質(zhì)上是隨機搜索算法，因此難以找到準確的收斂性判別標準。本文采用遺傳算法進化代數(shù)作為終止條件。當進化代數(shù)達到預先設定值3 000代時，算法終止，并輸出適應值最大的個體作為最優(yōu)解。

4 實證分析

根據(jù)上述模型，本文采用標準算例（數(shù)據(jù)來源于Rainer-Harbach等的標準實例）來進行分析。首先建立公共自行車系統(tǒng)調(diào)度優(yōu)化模型，然后利用遺傳算法進行求解。本文的遺傳算法采用C語言開發(fā)，其測試與運行均利用CPU 2.5G、內(nèi)存為6G和Windows 7操作環(huán)境下的計算機進行。另外，由于不同的參數(shù)設置對遺傳算法性能有較大影響，因此測試了不同參數(shù)組合下的運算效果，最終選擇種群規(guī)模為30、交叉率為0.7、變異率為0.05。通過運行，得到該問題的解。其中車輛行駛距離采用標準算例，各站點自行車需求數(shù)量由算法隨機生成，設站點需求總量為100輛，設裝配車輛容量為40，表1為租賃站點距離矩陣及需求表。

將遺傳算法運行20次，其中最優(yōu)結果為537，最差結果為543，遺傳算法最優(yōu)調(diào)度計劃見表2，通過觀察可以發(fā)現(xiàn)，該算法具有穩(wěn)定性，能夠有效解決公共自行車配送問題。

表1 租賃站點距離矩陣及需求表

表2 遺傳算法最優(yōu)調(diào)度計劃

5 結論

本文針對城市公共自行車系統(tǒng)的調(diào)度問題，利用遺傳算法建立了VRP模型，通過遺傳算法對車輛調(diào)度模型進行求解，發(fā)現(xiàn)遺傳算法在求解城市公共自行車調(diào)度問題上具有良好的效率。未來還可以進一步研究在靜態(tài)調(diào)度問題上擴展，考慮動態(tài)需求下的車輛調(diào)度情形，還可以考慮調(diào)配車輛同時兼有裝貨和卸貨功能，完成同一個站點的裝卸貨問題。

[1]Dantzig G B,Ramser J H.The truck dispatching problem[J]. Management science,1959,6(1):80-91.

[2]丁濤,向升斌,李表奎,等.基于改進粒子群算法的生鮮電商冷鏈終端配送車輛路徑問題研究[J].物流技術,2016,35(2):68-72.

[3]何博,盧青.城市公共自行車系統(tǒng)運營模式淺析[J].交通企業(yè)管理,2012,27(4):49-51.

[4]Erdogan G,Laporte G,Wolfler Calvo R.The static bicycle relocation problem with demand intervals[J].European Journal of Operational Research,2014,238(2):451-457.

[5]Lenstra J K,Kan A H G.Complexity of vehicle routing and scheduling problems[J].Networks,1981,11(2):221-227.

[6]周磊.基于節(jié)約里程法的配送路線優(yōu)化研究—以蘇寧電器為例[J].物流技術,2016,35(1):109-116.

Study on Optimal Public Bike Dispatching Based on Genetic Algorithm

Liu Zhaoren1,Xu Guanyu1,Yin Hang2
(1.School of Economics&Management,Southwest Jiaotong University,Chengdu 610031; 2.Department of Information&Engineering,Sichuan Tourism College,Chengdu 610100,China)

In this paper,on the basis of an analysis of the dispatching of public bikes,we used the genetic algorithm to build the VRP model,then applied it to a standardized numerical example for verification and at the end,according to the findings,demonstrated the efficiency and validity of the genetic algorithm in solving the bike dispatching model.

public bike;genetic algorithm;VRP;dispatchingoptimization

U484;O224

A

1005-152X(2017)02-0078-04

10.3969/j.issn.1005-152X.2017.02.019

2017-01-08

劉兆仁（1990-），男，碩士研究生，主要研究方向：項目優(yōu)化調(diào)度；徐冠宇（1992-），男，碩士研究生，主要研究方向：物流與供應鏈；尹航（1985-），通訊作者，男，博士，工程師，主要研究方向：項目管理。