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

劉兆仁，徐冠宇，尹 航

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

2.1 發(fā)展機(jī)遇

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

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

2.2 存在的問題

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

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

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

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

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

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

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

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

3.1 問題描述

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

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

（1）每個(gè)站點(diǎn)只允許被訪問一次；

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

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

3.2 模型構(gòu)建

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

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

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

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

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

C配送車輛的容量上限；

T配送車輛運(yùn)行時(shí)間上限；

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

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

3.3 模型求解策略

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

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

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

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

3.3.4 遺傳算子

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

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

父代染色體

父代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即為通過部分匹配交叉法獲得的新一代個(gè)體。

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

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

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

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

4 實(shí)證分析

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

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

表1 租賃站點(diǎn)距離矩陣及需求表

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

5 結(jié)論

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

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

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

[3]何博,盧青.城市公共自行車系統(tǒng)運(yùn)營模式淺析[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].物流技術(shù),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-），男，碩士研究生，主要研究方向：項(xiàng)目優(yōu)化調(diào)度；徐冠宇（1992-），男，碩士研究生，主要研究方向：物流與供應(yīng)鏈；尹航（1985-），通訊作者，男，博士，工程師，主要研究方向：項(xiàng)目管理。