城市商業(yè)中心區(qū)機械式立體車庫規(guī)劃模型與算法

陳 莉，王同洲，宋結(jié)焱，王 娜，段 剛

（1.蘭州城市學院，數(shù)學學院，蘭州 730070；2.中鐵集裝箱運輸有限責任公司，蘭州分公司，蘭州 730070；3.蘭州交通大學，交通運輸學院，蘭州 730070）

1 引言

國家統(tǒng)計局的統(tǒng)計公報顯示[1]，2012年末全國民用汽車保有量達到12089萬輛，比上一年末增長14.3%，其中私人車9309萬輛，增長率為18.3%.汽車保有量的快速增長產(chǎn)生了巨大的停車需求.一般情況下，機動車（出租車除外）只有10%-20%的時間是在路上行駛，80%-90%的時間需要停泊，而現(xiàn)有停車場車位遠遠滿足不了需求.《中國城市發(fā)展報告2011》指出[2]，若按照“一車一基本車位，15輛車一公共停車場”的國際慣例，我國城市停車位缺口將高達50%以上.因此，加快我國城市公共停車場的建設(shè)步伐刻不容緩.

傳統(tǒng)停車場占地面積大，平均需10平方米停一輛車，這對城市商業(yè)中心區(qū)等車輛集中且寸土寸金的區(qū)域來說，難以提供足夠的車位.而機械式立體車庫停一輛車平均只需1-2平方米，占地少，容量大，泊車與取車全自動化，節(jié)能環(huán)保，減少了車輛在車庫內(nèi)的尾氣排放和噪聲污染.所以建立機械式立體停車庫是未來城市停車場發(fā)展的必然趨勢.

停車場規(guī)劃以城市規(guī)劃和城市道路交通規(guī)劃為依據(jù)，主要考慮停車場的選址、規(guī)模和收費標準等因素.眾多學者對此進行了研究，文獻[3,4]建立了城市公共停車場選址優(yōu)化模型.目前，對立體車庫選址問題的研究尚不多見，文獻[5]和[6]分別利用粗糙集和GIS空間分析的方法對其進行了探索.文獻[7]考慮了停車場規(guī)模問題，文獻[8]對路內(nèi)停車定價問題進行了優(yōu)化，文獻[9]同時對停車場選址和收費問題進行了優(yōu)化，文獻[10]則研究了停車場停車費和規(guī)模問題.但同時考慮這三種影響因素的文獻還不多見.本文針對商業(yè)中心區(qū)用地緊張，傳統(tǒng)停車場車位不足的情況，計劃建立機械式立體車庫，并同時考慮車庫的選址、車位數(shù)量及收費這三個因素，建立綜合優(yōu)化模型，為市政部門提供決策依據(jù).

2 模 型

2.1 問題描述

在一個商業(yè)中心區(qū)中包含一些商業(yè)點，由于大量駕車出行者到達這些商業(yè)點導致停車需求過大，需要在給定的候選地點中新建若干立體車庫，且每個候選地點最多只能建一個.由于受到資金、土地及運營等方面的限制，還需要確定立體車庫的規(guī)模（停車車位數(shù)量）及收費標準.將商業(yè)中心區(qū)產(chǎn)生的停車需求按出行者出行目的不同分為兩種：一種是由于雇員上班引起的長時間停車需求，另一種是由于購物、娛樂等商業(yè)活動引起的短時間停車需求.出行目的不同的出行者會根據(jù)立體車庫距離其目的地（商業(yè)點）的遠近、收費和停車時間選擇不同的立體車庫存取車.目標是在投資回報期限內(nèi)，使得立體車庫運營總收入與投資成本之差（即利潤）最大化.

2.2 參數(shù)與變量設(shè)置

（1）參數(shù)設(shè)置.

K——商業(yè)點集合；

L——出行目的集合；

I——立體車庫候選地址集合；

J——立體車庫規(guī)模集合；

T——投資回報期（年）；

Nkl——到商業(yè)點k出行目的為l的出行者數(shù)，即停車需求，k∈K,l∈L；

tkl——商業(yè)點k出行目的l的出行者的平均停車時間，k∈K,l∈L；

dik——候選地點i到商業(yè)點k的距離，i∈I,l∈L；

aj——立體車庫規(guī)模為j時的投資（可變）成本，j∈J；

bj——規(guī)模為j的車庫的可用車位數(shù)，j∈J；

cj——規(guī)模為j的立體車庫層數(shù)，j∈J；

sj——規(guī)模為j的車庫每層每個車位的平均面積，j∈J；

Ri——候選地址i的可利用土地面積，i∈I；

f——資金預算；

Ci——在候選地點i修建一個車庫的固定成本；

eu,ed——分別為最高和最低收費標準；

αu,αd——立體車庫的利用率上下限；

v——平均步行速度；

θl——出行目的l的出行者的時間價值轉(zhuǎn)換參數(shù)，l∈L；

β1,β2——效用調(diào)節(jié)參數(shù).

（2）變量設(shè)置.

yi=新建立體車庫i的收費，i∈I，元/小時輛；

qikl=到達商業(yè)點k且出行目的為l的駕車出行者選擇立體車庫i的數(shù)量，i∈I,k∈K,l∈L

2.3 目標函數(shù)

停車費為立體車庫的唯一收入來源，收費標準以小時為單位，通常有兩種計費方法：一是與停車時間成正比；二是分段計費，且停車時間越長費用增加越多，比如停車1小時內(nèi)費用為10元，2小時內(nèi)第2小時為15元，3小時內(nèi)第3小時為20元，以此類推.分段計費的目的是為了減少停車時間，高效的利用停車設(shè)施，主要是限制到商業(yè)中心區(qū)購物休閑的這部分出行者的停車時間.但對商業(yè)中心區(qū)內(nèi)的工作人員來說，其停車時間往往是一天（按8小時計算），所以分段計費的方式對他們很不公平，而且難以根據(jù)停車時間的長短來區(qū)分出行目的，因此我們采用第一種計費方式.

以一年365天計算，在投資回報期T內(nèi)，新建車庫的總收費為 365T，而總成本為固定成本與可變成本之和，所以，目標為利潤F最大：

2.4 約束條件

(1)每個候選地點最多只能建立一種規(guī)模的立體車庫.

(2)收費限制.

式中 M為非常大的正數(shù)，式(3)表示只有在候選地點新建立體車庫才能收費.

式(6)和式(7)表示分別表示收費上下限.

(3)資金預算限制.

(4)可利用土地面積限制.

(5)所有新建立體車庫提供的車位數(shù)應(yīng)滿足總停車需求.

(6)新建立體車庫利用率要求.

(7)出行者對立體車庫的選擇.

出行者通過步行到達立體車庫的時間和停車費（停車時間乘以單位費用）來選擇立體車庫，并通過時間價值轉(zhuǎn)化參數(shù)θl將步行時間轉(zhuǎn)化為費用，將兩者單位統(tǒng)一，應(yīng)用Logit分擔率計算每個立體車庫吸引出行者停車的數(shù)量.

(8)變量聲明.

3 求解算法

我們采用遺傳算法進行求解.雖然遺傳算法具有簡單、魯棒性好和并行計算等優(yōu)點，但其最大的不足之處在于早熟，即搜索過程過早地陷入局部最優(yōu)解.克服該缺點的方法有很多，比如在搜索過程中嵌入禁忌搜索、模擬退火[11]等算法.遺傳算法是建立在種群多樣性基礎(chǔ)上的啟發(fā)式方法，在計算過程中，一旦種群多樣性遭到破壞，便會陷入早熟，因此本文設(shè)計了基于種群多樣性控制策略的遺傳算法.

3.1 種群多樣性

本文采用的遺傳算法將解分為可行解與不可行解兩種，并分別放入兩個子種群中，在運算過程中始終保持一定數(shù)量的不可行解，這樣無疑可以擴大種群多樣性.通過對可行解與不可行解的交叉、變異等運算，能夠得到更接近搜索空間邊界的解，這也是高質(zhì)量解經(jīng)常出現(xiàn)的地方.

當?shù)欢ù鷶?shù)后，當前最優(yōu)個體仍沒有改變，說明有可能陷入局部最優(yōu)，此時通過引入一定數(shù)量的新個體以代替部分當前個體，從而擴大種群多樣性.為提高計算效率，我們將當前種群中評價值最好的那部分個體保留，替代的都是那些評價值差的個體.其中，新個體的產(chǎn)生與后面介紹的初始化種群的方法相同.

3.2 染色體編碼與解碼

采用整數(shù)編碼，由數(shù)量不同的基因組構(gòu)成，每個基因組包含新建立體車庫地址、規(guī)模及收費三個信息.由于每個染色體的長度不同，為便于后續(xù)操作，我們將新建立體車庫的總數(shù)統(tǒng)計后放在每個染色體的最前方.在圖1的染色體P中，第一組基因(3,2,15)表示在候選地3建立規(guī)模為2的立體車庫，收費為15元，后兩組基因含義與此相同.由于一共建立了3個立體車庫，所以我們將3放在染色體中0的位置.因此該染色體的長度為4.

圖1 染色體的表示方法Fig.1 The representation scheme of chromosome

顯然，該染色體對應(yīng)的解為：x32=1,x51=1,x24=1,y3=15,y5=20,y2=10 ，而 qikl則由式(11)計算得到.

3.3 個體評價值

為使種群多樣化，我們擴大搜索空間，通過放松約束條件將不可行解包含進來.令γh(h=1,2)和(h=1,2,3,i∈I)為懲罰因子，并定義函數(shù)

于是，我們將懲罰因子和上述定義的函數(shù)進行加權(quán)，并同模型中的目標函數(shù)求代數(shù)和，得到個體P的評價函數(shù)為

3.4 交叉與變異

交叉操作采用下面的方法.分別令n1和n2為父染色體P1和P2的新建車庫數(shù)，即兩個染色體第0個位置的值.隨機產(chǎn)生兩個整數(shù)n3∈[1 ,n1]和n4∈[1 ,n2]，然后將染色體P1的n3到n1位基因組和染色體P2的n4到n2位基因組進行交換，得到兩個子染色體C1和C2，它們的新建車庫數(shù)分別為n3+n2-n4和n4+n1-n3.為使交叉操作有效進行，n3和n4不同時為1.例如當n1=3,n2=5,n3=1,n4=4時，兩個染色體的交叉操作如圖2所示.

圖2 染色體交叉操作Fig.2 Crossover of two chromosomes

由于子代染色體C2包含相同的候選地點，所以需要調(diào)整，只需刪去任意一個候選地點相同的基因組即可，并同時對新建車庫數(shù)量進行調(diào)整.調(diào)整后的染色體C3如圖3所示.

圖3 染色體的調(diào)整Fig.3 Repair of the chromosome

采用三種方式進行變異操作，分別為：

(1)對候選地址進行調(diào)整，隨機選擇一個在染色體中沒有出現(xiàn)的候選地點，替換該地點；

(2)對車庫規(guī)模進行調(diào)整，隨機產(chǎn)生一個不同的車庫規(guī)模替換該規(guī)模；

(3)對收費進行調(diào)整，隨機產(chǎn)生一個收費替換該費用.

在染色體的所有基因組中（不包括第0位）隨機產(chǎn)生一個位置，在三種變異方式中隨機選擇一個，對相應(yīng)基因進行調(diào)整.

3.5 種群初始化及管理

采用下面的方法產(chǎn)生染色體：隨機生成一個整數(shù)n，1≤n≤ ||I，其中 ||I為候選地點個數(shù)，染色體的長度為n+1.然后隨機產(chǎn)生n個不同的整數(shù)（范圍在1到 ||I之間），作為建立車庫的地點依次放入染色體的每個基因組中；再從車庫規(guī)模集合中隨機選擇n個整數(shù)，依次放入染色體的每個基因組中；最后為每個基因組隨機產(chǎn)生一個費用.共產(chǎn)生PS個染色體作為初始種群.

得到的解根據(jù)其可行性分別歸入可行解子種群和不可行解子種群，并記錄可行解種群中評價值最好的個體.在交叉和變異后可能導致解的不可行性，這樣會減少可行解的數(shù)量，為保持兩個子種群的合理比例，我們通過變化罰因子的大小來調(diào)節(jié)種群的數(shù)量.令Nf表示當前迭代可行解子種群中染色體數(shù)量，Ninf表示當前迭代不可行解子種群中染色體數(shù)量，則二者的比例σ為

定義一個目標比例σ0，當?shù)舾纱?，比較二者的大小，若相差過大，則對3.3節(jié)中的罰因子γh進行如下調(diào)整：罰因子πhi的調(diào)整與之相同.

4 算例分析

我們以一個商業(yè)中心區(qū)為例，對本文建立的模型和設(shè)計的算法進行驗證.根據(jù)該中心商業(yè)布局特點，我們將其劃分為6個商業(yè)點，將出行目的分為上班和購物兩種，計劃在10個候選地點進行選址，共有12種規(guī)模的立體車庫可供選擇.商業(yè)點及候選地點位置如圖4所示.修建一個立體車庫的投資回報期限為20年，收費最低和最高標準分別為5元/小時和30元/小時，資金預算為4千萬元.假定每個立體車庫的利用率上限為95%，下限為70%.上班出行者的平均停車時間為8小時，購物休閑出行者的平均停車時間為3小時，平均步行速度為5 km/h.上班出行者的時間價值轉(zhuǎn)換參數(shù)為2，購物休閑出行者的時間價值轉(zhuǎn)換參數(shù)為1，效用調(diào)節(jié)參數(shù) β1=1,β2=0.005.其余信息如表1—表4所示.

圖4 商業(yè)中心區(qū)示意圖Fig.4 The central business district diagram

表1 停車需求（輛）Table 1 Parking demand（vehicle）

表2 候選地點與商業(yè)點距離（公里）Table 2 The distance between candidate location and business site（kilometer）

表3 車位信息Table 3 Berth information

由于遺傳算法對交叉概率和變異概率的選取較為敏感，因此為了尋求二者的最佳取值，我們采用VC++6.0編程，在配置為AMD速龍?II×4645(3.1GHz)、2G DDR3 SDRM臺式機上，對兩種概率組合分別做20次測試.首先取變異概率為0.1，交叉概率每次變化0.05，評價值的平均值如圖5所示，得到交叉概率的最優(yōu)值為0.9.在此概率下，變異概率每次變化0.1，得到評價值的平均值如圖6所示，變異概率的最優(yōu)值為0.6.其余參數(shù)分別為遺傳代數(shù)1000，種群規(guī)模PS=40，目標比例σ0=60%，初始罰因子γh=10=1.每經(jīng)過50代對罰因子進行一次調(diào)整，每運算100代調(diào)整一次種群多樣性，每次調(diào)整替換種群中70%的個體.

表4 候選地點信息Table 4 Candidate location information

為說明上述提高種群多樣性所采取的多種方法的有效性，我們將一般的遺傳算法（沒有區(qū)分可行解與不可行解并調(diào)整二者比例，也沒有對種群的部分個體進行替換）與本文提出的基于種群多樣性控制的遺傳算法進行對比，結(jié)果如圖7所示.前者在450代就已經(jīng)收斂，充分說明了其早熟性，而本文提出的方法在迭代的最后階段（870代）評價值仍有改善.

在得到的方案中，一共新建8個立體車庫，分別在候選地點4，5和7建立一個25層150個車位的車庫，在地點3和9分別建立一個20層160個車位的車庫，在地點2，6和8分別建立一個25層200個車位的車庫，總共提供1370個車位（總需求為1228個）.

圖5 交叉概率測試Fig.5 The test of crossover probability

圖6 變異概率測試Fig.6 The test of mutation probability

圖7 兩種算法收斂性對比Fig.7 Comparison of two algorithms convergence

按出行目的劃分，到達同一商業(yè)點的出行者選擇每個停車場的人數(shù)如表5所示.例如到商業(yè)點II上班的出行者共有45人，選擇在新建車庫地點2和8停車的人最多，各有7人，而各有4人選擇新建車庫地點5和7，是最少的.從表5停車總數(shù)統(tǒng)計一欄不難看出，選擇在新建車庫地點的出行者人數(shù)與該地所建車庫規(guī)模正相關(guān)，即車庫規(guī)模越大吸引的出行者越多.但車庫利用率卻正好相反，規(guī)模最大的三個車庫地點2，6和8的利用率最高為83.5%，規(guī)模最小的三個車庫地點4，5和7的利用率基本為95%，中間規(guī)模的二個車庫利用率則接近95%.

表5 停車需求分配方案Table 5 The distribution of parking demand

每個新建立體車庫的收費標準如表6所示，總利潤為100396.6萬元，其中停車收費為104336.6萬元，修建車庫成本為3940萬元，包括固定成本115萬元和可變成本3825萬元.我們看到，吸引較多出行者的地點2，6和8收費反而最低，都不超過25元/小時輛，而其余地點收費則較高，地點4和5達到了上限30元/小時輛.由此我們得出一個規(guī)律：收費與停車數(shù)之間存在相反的關(guān)系，即收費越低，停車數(shù)越多.這與薄利多銷的營銷策略相吻合，而為收回成本，停車數(shù)少的車庫只能采取提高收費單價的辦法.

表6 收費方案Table 6 Charging scheme

5 研究結(jié)論

立體車庫是解決城市尤其是商業(yè)中心區(qū)停車難的一個重要手段，車庫規(guī)劃應(yīng)根據(jù)區(qū)域商業(yè)布局特點和出行需求做到統(tǒng)籌規(guī)劃.本文建立的綜合優(yōu)化模型為車庫選址、建設(shè)規(guī)模和收費標準的合理決策提供了科學依據(jù).本文提出的控制種群多樣性的遺傳算法，通過調(diào)節(jié)可行解與不可行解子種群的規(guī)模，保留較優(yōu)個體淘汰較差個體，維持種群多樣性，克服了一般遺傳算法早熟的缺陷.算例表明了模型和算法的正確性和實用性.

本文尚存在一些不足之處，如收費標準的制定比較單一，沒有針對不同出行目的人群進行細分，比如可以對上班族實行月卡制度，實行一定的優(yōu)惠；商業(yè)點的劃分是人為確定的，尚缺乏定量依據(jù).商業(yè)點的數(shù)量和位置劃分是車庫選址的前提，對決策有很大影響，過細不利于計算，過粗又失去意義.這些將是我們下一步要進行研究的內(nèi)容.

[1]中華人民共和國國家統(tǒng)計局.2012年國民經(jīng)濟和社會發(fā)展統(tǒng)計公報,(2013-2-22)[2013-6-20].http://www.stats.gov.cn/tjgb/ndtjgb/qgndtjgb/t20130221_402874525.htm.[National Bureau of Statistics of China.Statistical Communique of the People's Republic of Chi?na National Economic and Social Development in 2012,(2013-2-22)[2013-6-20].http://www.stats.gov.cn/tjgb/ndtjgb/qgndtjgb/t20130221_402874525.htm.]

[2]《中國城市發(fā)展報告》編委會.中國城市發(fā)展報告(2011)[M].北京：中國城市出版社,2012.[“Urban De?velopment Report in China”Editorial Board.Urban De?velopment Report in China(2011)[M].Beijing:China City Press,2012.]

[3]Aros-Vera F,Marianov V,Mitchell J E.P-Hub ap?proach for the optimal park-and-ride facility location problem[J].European Journal of Operational Research,2013,226(2):277-285.

[4]Tang J X,Tang L X,Wang X P.Solution method for the location planning problem of logistics park with variable capacity[J].Computers&Operations Research,2013,40(1):406-417.

[5]牛國鵬,李建國,蔣兆遠.基于粗糙集的立體停車庫選址決策研究[J].蘭州交通大學學報,2008,27(4):87-89.[NIU G P,LI J G,JIANG Z Y.Study on location decision of solid garage based on rough set[J].Journal of Lanzhou Jiaotong University,2008,27(4):87-89.]

[6]湯旻安,任恩恩,閆軍,等.以蘭州市為例的城市中心區(qū)立體車庫選址分析及評價[J].蘭州交通大學學報,2009,28(3):109-114.[TANG M A,REN E E,YAN J,et al.A study of site selecting analysis and evaluation of urban centers’shared mechanical parking garage in Lanzhou[J].Journal of Lanzhou Jiaotong University,2009,28(3):109-114.]

[7]梅振宇,陳峻,王煒.城市路內(nèi)停車設(shè)置規(guī)模非線性優(yōu)化模型及其算法[J].交通運輸工程學報,2007,7(2):89-93.[MEI Z Y,CHEN J,WANG W.Nonlinear opti?mization model and algorithm of urban curb parking set?ting scale[J].Journal of Traffic and Transportation Engi?neering,2007,7(2):89-93.]

[8]MEI Z Y,XIANG Y Q,CHEN J,et al.Optimizing model of curb parking pricing based on parking choice behavior[J].Journal of Transportation Systems Engineering and Information Technology,2010,10(1):99-104.

[9]Hensher D A,King J.Parking demand and responsive?ness to supply,pricing and location in the Sydney cen?tral business district[J].Transportation Research Part A,2001,35(3):177-196.

[10] 鄭士源.信息不完全時公共停車場停車費和規(guī)模優(yōu)化[J].交通運輸工程學報,2010,10(5):81-89.[ZHENG S Y.Parking fee and scale optimization of pub?lic parking lot with incomplete information[J].Journal of Traffic and Transportation Engineering,2010,10(5):81-89.]

[11]段剛,李引珍,田麗娜.基于技術(shù)站中轉(zhuǎn)作業(yè)的集裝箱空箱動態(tài)調(diào)運優(yōu)化模型與算法[J].交通運輸系統(tǒng)工程與信息,2012,12(2):111-118.[DUAN G,LI Y Z,TIAN L N.Dynamic empty container allocation model and algorithm based on technique station transfer opera?tion[J].Journal of Transportation Systems Engineering and Information Technology,2012,12(2):111-118.]