多類型公共自行車調運問題

徐國勛， 李妍峰， 李 軍， 徐冠宇

(1.西南交通大學 經濟管理學院，四川 成都 610031；2.成都飛機工業有限公司，四川 成都 610000)

0 引言

隨著城市化進程的不斷加快，城市交通擁堵問題日益嚴峻，給居民出行帶來諸多不便。自杭州2008在國內建立第一個公共自行車系統以來，我國城市公共自行車系統的建設取得了長足的發展。截止2016年初，我國共有118個城市擁有公共自行車系統[1]。公共自行車可以有效銜接長距離公共交通，與短距離公共交通形成優勢互補，可以替代部分私家車出行，因而已經成為城市公共交通系統的重要組成部分。同時，公共自行車還是一種零碳排放的出行工具，符合未來智慧城市的發展方向。

隨著公共自行車系統的大量建設和推廣，越來越多的問題產生并亟需解決。倪康康等[2]對國內公共自行車系統的發展狀況進行了分析，指出目前公共自行車系統運營過程中亟待解決的問題主要有：(1)道路騎行的安全問題；(2)道路的交通管理問題；(3)公共自行車借車難、還車難、易損壞；(4)公共自行車系統設備安裝運營以及虧損問題。借車難、還車難是阻礙公共自行車系統發展的主要問題，即在需要租車的時候發現站點無車，在需要還車的時候發現站點無空位。為解決此類難題，需要進行合理有效的車輛調運，即調運卡車在公共自行車租賃站點所組成的網絡中，將某些站點的自行車調運到其它站點去。這類問題被稱為自行車調運問題或者自行車再平衡問題。這類問題的研究又分為動態和靜態兩種。當自行車系統使用率非常高時，根據每個站點的實時需求進行實施調運。當自行車系統使用率較低時，選擇在某個時段內(如夜間)對各站點進行調運。由于自行車系統一般是在晚上進行調運，因此現有研究以靜態模型為主，而對動態問題的研究非常少，只有文獻[3～7]進行了研究。無論是動態問題還是靜態問題，已有研究主要以運營成本最小和為滿足的需求最小為目標，或是采用線性加權的方法同時考慮著兩個目標。

通過對已有文獻的梳理，發現目前對靜態公共自行車的研究，除了Li等[17]之外都只針對單類型自行車，多類型自行車的研究處在起步階段。在實際中，很多城市(如中國的杭州、臺北，荷蘭的鹿特丹、海牙、烏得勒支，英國的倫敦，日本的愛知縣等)已經開始將多類型公自行車(如單人座，雙人座，帶小孩座椅等)引入公共自行車系統，在景區中(如杭州西湖，武漢東湖等)更加普遍也更加受歡迎。針對多類型公共自行車的特點，本文做了以下研究：(1)提出了多類型公共自行車的再平衡問題。針對網絡中各類型自行車失衡的情況(如地鐵站附近很難租到單人座自行車，景點附近很難租到雙人座自行車等等)，設計了一個懲罰系數。該系數除了能衡量站內已有自行車數目和目標需求的偏差，還可以實現各租賃站點公共自行車的調運組合優化。(2)考慮了調配時間的限制。在現實生活中，對公共自行車的調配一般集中在某個時段(例如夜間)，因此本文將調配時間限制引入到多類型公共自行車問題。(3)將配送車輛數目擴展至多輛車。Li等[17]對多類型自行車的研究是假定一輛調運車負責所有租賃站點的調運，而在現實中是由第三方物流公司派出多輛調運車輛服務租賃站點。為了使問題更加貼近實際情況，本文研究了多輛調運車輛的情況。

1 問題描述及模型建立

1.1 問題描述

本問題定義在完備圖G=(V,A)上。V表示點的集合{0,1…,n}，包括車場和租賃站點，其中0點表示車場，其余為租賃站點。由于自行車調運有第三方物流公司運作，因此車場內自行車保有數量為0。A表示弧的集合，A={(i,j);i,j∈V,i≠j}，每條弧對應著一個運輸成本。

此外，本問題考慮了不同類型車輛之間需求的替代性。即某類自行車缺貨時，有可能由其他類自行車替代使用。若某站點沒有單人自行車，租賃者可使用雙人自行車作為替代。反之，若使用者想租賃一輛雙人自行車，而站點沒有此類車時，可轉向使用2輛單人自行車作為替代。而某些情形則不允許替代，如帶小孩的租賃者打算租賃一輛帶小孩座椅的自行車，但該站點沒有此類車，這時租賃者沒有辦法使用其他類自行車作為替代。替代策略可以有效緩解需求，但同時也會產生一個替代懲罰成本，這是由于它的替代，會導致其他站點可供此類自行車使用的數量減少。

本問題需要合理地安排車輛的調運路線，同時確定在每個站點每類自行車的裝載或卸載數量，從而使得總成本(包括公共自行車運營公司支付給物流公司的運輸成本、非均衡懲罰成本和替代懲罰成本)最小化。

2.2 符號說明

在建模過程中需要用到以下符號：

(1)集合

K:調運車輛集合；M:行車種類集合；N:租賃站點集合。

(2)參數

(3)決策變量

2.3 數學模型

(1)

s.t.

輔助約束：

(2)

(3)

裝卸載約束:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

路徑約束：

(15)

(16)

(17)

(18)

(19)

(20)

其它約束：

(21)

(22)

(23)

3 求解算法

由于本問題是混合整數規劃問題，因此是NP問題。當問題規模較小的時候可以用Gurobi，CPLEX等商業優化軟件求解，但當問題規模變大后，這些商業優化軟件在規定的時間內甚至無法求得可行解。因此，本文設計了一種混合禁忌搜索算法來求解本問題。在所有的啟發式算法中，禁忌搜索算法可以在較短時間內成功求解TSP問題(如文獻[24])，VRP問題(如文獻[25])，dial-a-ride問題(如文獻[26～28])，Pickup and delivery問題(如文獻[29,30])等一系列路線優化問題。考慮到公共自行車問題也是一類路線優化問題，故本文亦采用禁忌搜索算法作為主干算法，用來確定調運車輛的路線。當路線被確定后，本文將大規模數學規劃優化器Gurobi 7.0嵌入到禁忌搜索算法中，用以確定多類型公共自行車的調運策略。算法具體流程如下所示：

Step1生成當前可行解p；

Step2用p更新Pbest；

Step3將精英集合S設為空集；

Step4如果滿足終止條件轉Step15，否則繼續執行Step5～12，否則轉Step13；

Step5在p的領域中找到最好的解p′；

Step6如果p′優于pbest，用p′更新pbest；

Step7將pbest放入精英集合S，然后更新精英集合S；

Step8用p′更新p；

Step9如果經過IT次迭代仍無法改進pbest，則執行Step10～12；

Step10從精英集合S中隨機選出一個解pr，然后將pr從S刪除；

Step11用pr更新p；

Step12重置禁忌表；

Step13返回pbest。

Step 1～3是算法的初始化步驟。在每次迭代過程中采用了最先改進下降策略來尋找最好的解(Step 5)。根據本文所設計的藐視準則，無法改進pbest的移動不能放入禁忌表中。如果pbest得到了改進，則將pbest放入精英集合S中(Step6～8)。如果經過次迭代仍無法改進pbest，則從精英集合中隨機選出一個解pr，然后更新當前解p，并將禁忌表清空(Step 9～12)。

3.1 解的表示

假定n個租賃站點由k輛調運車輛來服務，則解p的長度為(k+n)。其中k個0表示從車場出發的調運車輛，其余n個自然數表示各個需要被服務的租賃站點。圖1給出了k=3，n=7的例子，表示了3條路線：0→1→2→0,0→5→7→4→0和0→6→3→0。

0120574063

圖1 解的表示

3.2 初始解的生成

本文設計了一種隨機選擇機制的最近鄰算法來生成初始可行解。傳統的最近鄰算法在每次迭代中選擇的是最近的且未被訪問的站點，通過這種簡單的貪心機制來構造可行解。本文所設計的算法用隨機選擇機制替代了簡單的貪心機制。算法流程如下：

Step1將客戶點集合S初始化為φ；

Step2將路線的初始點設置為0；

Step3在所有未被服務過的站點中選擇總成本fcost最小的三個站點，隨機選取一個站點j加入到路線末端的站點i之后，然后將j放入S中；

Step4如果未被服務過的站點只剩s,t最后兩個，則二者被優先訪問的概率為Ps和Pt的關系為Ps+Pt=1，Ps和Pr隨機分布于區間(0,1)；

Step5如果S包含所有客戶點，繼續執行以下步驟，否則轉Step 3；

Step6將剩余k-1個0點隨機插入到路線當中，構造成3.1節表示的解；

Step7如果生成的解不滿足服務時間守恒條件，則轉Step 1，否則算法結束。

在Step 3中，fcost的計算公式如式(22)所示。

(22)

3.3 解的評估

3.4 鄰域算子

鄰域算子是用來從當前解中生成新的解。本文設計了6中鄰域算子，分別是：子序列隨機交換，單點隨機插入，子序列隨機插入，子序列逆序，子序列逆序后隨機插入和子序列逆序后隨機交換。在每次迭代過程中，每個鄰域算子采用均最先改進下降策略：一旦某個算子改進了當前解，則局部搜索從改進后新的當前解重新開始，直到所有鄰域算子都無法改進當前解為止。

圖2 鄰域算子

①子序列隨機交換：在解中隨機選擇兩條獨立的子序列，交換這兩條序列的位置。如圖2-a所示。

②單點隨機插入：在解中隨機刪除一個點，然后將這個被刪除點重新隨機插入到解中。如圖2-b所示。

③子序列隨機插入：在解中隨機刪除一條子序列，然后將這個被刪除的子序列重新隨機插入到解中。如圖2-c所示。

④子序列逆序：在解中隨機選擇一條子序列，然后將該序列逆序。如圖2-d所示。

⑤子路線逆序后隨機插入：在解中隨機選擇一條子序列并刪除，然后將該序列逆序后隨機插入到解中。如圖2-e所示。

⑥子路線逆序后隨機交換：在解中隨機選擇兩條獨立的子序列并且逆序，然后交換這兩條序列的位置。如圖2-f所示。

3.5 禁忌表和藐視準則

3.6 多樣化策略

本文設計了一種基于精英集合的多樣化策略。Nguyen等[31]設計了一種精英集合，此集合是由高品質解組成的具有多樣性特征的解池，其中這些高品質的解在禁忌搜索算法迭代過程中發現的。當算法開始停滯時，精英集合可以使得算法更好地跳出局部最優，使得搜索方向朝著全局最優前進。

精英集合有最大規模上限，并且在算法開始的時候是空集。精英集合的多樣性是通過不斷地加入新的高質量的解，并刪除現有的存在于集合中的某些解來實現的。與Nguyen等[31]的做法不同，本文對解的刪除是基于解之間的相似度來決定。相似度Δ(pi,pj)表示解pi和pj之間相同弧的總數，其中Δ(pi,pj)≤n-1，n表示站點的數目，若有Δ(pi,pj)=n-1，則解pi和pj完全相同。舉例如下，假定解p1=(0,1,2,3,4,0,5,6,7,8),p2=(0,1,2,5,4,0,6,8,3,7)，則p1和p2之間相同弧為(0,1)和(1,2)，因此Δ(p1,p2)=2。算法每次迭代都會將產生的最好的解pbest放入精英集合，但對解做刪除操作時需考慮兩種情況：1)當精英集合未達到規模上限時，將滿足條件Δ(p,pbest)≥n-2的解全部刪除，目的是提高精英集合的質量和多樣性。2)當精英集合達到規模上限時，刪除與pbest相似度最高的解即可。

4 數值實驗

本節通過數值實驗對問題特性進行了描述，并對算法性能進行了分析。混合禁忌搜索算法采用C#編寫，所有實驗均在i7-2600CPU主頻3.40GHz內存16GB的PC上進行。

4.1 非均衡懲罰系數對調運決策的影響

表1 算例參數設置

場景1基本場景。

場景2租賃站點2雙人座自行車需求量很大，保有量無法滿足需求，需增加調入量。

場景3租賃站點3雙人座自行車的需求量很小，同時保有量過多，需增加調出量。

表2 四種場景下各類型自行車的調運數量

注：表中負值表示從配送車上卸載，即站點自行車增加。同理，正值表示往配送車上裝載，即站點自行車減少。

表3 四種場景下目標函數值和調運車輛路線

表3給出了4中場景下調運車輛的運行路線以及目標函數值。與場景1相比，場景2，3和4的目標函數值和運行路線都發生了變化。這是由于，不同的懲罰系數會產生了如表2所示不同的自行車調運組合，進而產生了不同了懲罰成本。同時，不同的調運組合會影響調運車輛的訪問順序，故產生了不同的運行路線。

4.2 替代策略對調運決策的影響

表4 不同替代策略下的結果

表4結果表明替代策略能夠獲得更低成本，因為第一類自行車具有相對較高的非均衡單位懲罰成本，采用替代策略能夠降低第一類自行車非均衡的程度，并使得總的成本降低。該分析表明調運方在操作過程中可采取更加靈活的替代策略，以滿足不同類型自行車的需求。

4.3 混合禁忌搜索性能分析

Nguyen等[31]發現精英集合規模增加到一定程度后，對解得改進作用開始不顯著。他們的實驗結果表明精英集合規模為5時，可以在解的質量和求解時間之間達到均衡。本文采用Nguyen等[30]的做法，將精英集合規模設置為5。此外出于求解時間的考慮，本文將設置為10，算法終止時間設置為100代。

表5 算法性能比較

表5詳細給出全部數據的求解結果，Gurobi求解模型(終止時間為2小時)得到的上界(UB)、下界(LB)和反應Gurobi求解質量的gap。表5還給出了混合禁忌搜索求解結果，包括運行20次得到的求得的目標函數平均值(Avg.obj.)，平均運行時間(Avg.cpu)和標準差(Std)，以及反應與Gurobi求解下界(LB)差距的相關gap，其中gap=(Avg.obj-LB)/LB。

當|N|=10，Gurobi運行約100秒后求得了最優解。當問題規模逐漸增大(|N|=20,30,60,90)，gap逐漸變大，這種情形下Gurobi在規定時間內只得到了可行解。當問題規模進一步變大(|N|=120，Gurobi在規定的時間內無法求得可行解。這表明精確求解方法求解本問題上具有很大局限性。而文本所設計的混合禁忌搜索算法穩定性較好(標準差均值約25)，同時能在短時間內(平均運行時間不到4分鐘)可求得所有規模數據的可行解，與精確算法形成了明顯的對比。

為了比較混合禁忌搜索算法的求解質量，計算了相對于Gurobi求解下界的gap。由表5可得，當|N|=10，gap=0.2%，而平均運行時間約8秒。這意味著當問題規模較小的時候，混合禁忌搜索算法可在非常短的時間內求得十分接近最優值的可行解。當|N|=20,30，混合禁忌搜索求解gap雖然高于Gurobi求解gap，但差距在逐漸變小。當|N|=60,90，混合禁忌搜索求解gap比Gurobi求解gap要小，這意味著前者在600秒內求解效果比Gurobi求解兩小時還要好。當|N|=120，混合禁忌搜索在短時間內仍然可以求得可行解。

5 結束語

本文研究了靜態環境下多類型公共自行車問題，以運營成本最小目標建立了相應的混合整數規劃模型。為求解問題，設計了混合禁忌搜索算法。其中禁忌搜索用來處理調運車輛路線的搜索空間，而租賃站點的各類型公共自行車的調配組合由嵌入的精確算法來確定。在數值分析部分，通過不同規模的算例比較，測試了混合禁忌搜索的性能。結果混合禁忌搜索能在較短時間內求解更大規模的問題，并且求解質量較好。測試算例還展示了非均衡懲罰系數對調配策略的影響，結果表明非均衡懲罰系數的變化可以決定了租賃站點各類自行車數量的增減和調配車輛的運行路線，本問題引入的懲罰系數成功地實現了不同租賃站點的公共自行車調運組合優化的目標。不同類型的自行車需求的替代使得調運決策更加靈活。下一步研究可考慮對損壞自行車的回收，動態環境下的調運以及和共享單車的比較等等。