超市班車線路設計兩階段模型

曹 奕

（上海建瓴工程咨詢有限公司，上海 200032）

0 前言

超市班車系統嚴格意義上不能算作城市公交系統的一部分，但也能發揮一定的公交補充作用。國外由于居民的居住地區分散，且私車保有量高，并無該類公交業態，因此海外相關研究和文獻幾乎為零，國內也鮮有針對此類線路設計的專門方法研究。由于超市班車系統其自身的特性，因此該系統的服務水平對其的吸引力的大小起很大作用，也決定了班車線路是否能發揮最大效用。該文結合成熟的最短路徑計算方法和實際算例，提出了兩階段的班車線路設計和優化方法。

1 超市班車交通線路的設計優化

1.1 研究意義

超市班車公交系統處于公共交通最低層，嚴格意義上還不能算作城市公交系統的一部分，但它卻可以對公交系統產生一定的影響。它起連接主要商業區，尤其是大型超市和周邊居民集散點的作用。但是國外由于巨大的私車保有量以及相對比較分散的居住區分布，并沒有這樣的社會現象，因此國外相關研究和文獻幾乎為零。國內關于該項目的研究也并不多，在超市班車運營中，由于運營者和乘客間的矛盾往往導致一些棘手的問題，這些問題會影響線路運營者的積極性，增加乘客的不滿情緒，不利于提高超市班車系統的整體效率，但是由于超市班車系統其自身的特性，因此該系統的服務水平對班車系統的吸引力的大小起很大作用，也決定了班車線路是否能發揮最大效用。筆者結合現在已有的研究結論，并整合自身的研究，給出了針對該問題的理論與實際相結合的方法，為超市班車未來的發展提供依據，保證超市班車系統的順利運行。

1.2 超市班車路線線型的分類

一般公交線路有2種線性形式，即直線型和環線型。2種線形的特點和適用性見表1。

表1 公交線路線形特地和適用性對照表

在該文中，綜合考慮超市班車服務對象為一定區域范圍內的小區居民，且以超市作為線路起訖點，因此超市班車更適合使用環形型線路（該文的線路設計都默認為環線線路）。

1.3 超市班車線路的設計步驟

超市班車線路的設計一般要經過以下3個步驟：1） 概念性線路設計。結合超市的運營實際情況和經營戰略目標，摸排線路需要覆蓋的范圍和點位。一般可通過調查問卷來分析賣場顧客的主要分布，也可對相鄰的競爭超市開設的線路進行調研（該文不對此進行深入探討，后續算例中的中間點位為給定）。2） 第一階段為線路初步設計。線路初步設計就是對概念性線路設計方案的具體化過程，具體包括對中間站點進行區域劃分，一般根據扇形分區將相近點位劃入同一個區域，對區域內中間站的先后順序進行最優組合。3） 第二階段為方案比選和優化。對線路初步設計中某些明顯劃分不合理的點（例如因該點而造成該線路無法一筆畫、部分點位處于其他線路最優路徑中等）進行區域調整，并優化線路長度。步驟二、步驟三是該文的研究重點。

1.4 超市班車線路優化問題的數學簡化模型

超市班車線路優化實際上是一種路徑選擇問題。在中間站點一定的情況下，會有不同的線路組合、不同的線路數量以及不同的站點排序，如何在眾多組合間選擇一條適合的超市班車線路（在提高顧客對班車滿意度的同時，使超市班車運營成本最小化）就是班車線路優化主要的研究問題。該問題將會以整個班車系統的線路長度作為指標，力求尋找相對物理距離比較短的環狀線路。

班車線路設計是以超市為必經點的閉合最短環路問題，也就是運籌學中經典的旅行商問題，是由超市出發，途中剛好不重復地經過所有中間站點，最后又回到超市，形成一個閉合型環路的問題。在對該類問題的研究中，需要解決的是如何形成一個閉合的最優環路問題。

該類問題通常運用運籌學中的旅行商問題（Traveling Salesman Problem，TSP）求解。這個問題很復雜，如果個站點兩兩相連，那么就有（-1）!/2條線路需要考慮，這是一個至今還沒有被完美解決的非線性規劃問題。

因此在該文中提出了一種針對超市班車線路模型這樣的小型系統路線設計的手算方法：1） 要對給定的站點進行區域劃分，將其歸入不同的線路中。2） 對同一條線路中的節點進行排序，求得較優的環形線路。3） 在不同的劃分和計算方法中進行比較，求出系統路線的最優解。

2 超市班車兩階段模型及實際算例

該部分將會把線路設計分為2個階段，分別為線路初步設計與方案調整比選。其原因是在階段一進行線路初設的過程中，是利用啟發式算法進行較優解的搜索，然而，由于啟發式算法是一種以經驗為基礎的最短路徑算法，并不是精確的數學方法，因此，需要在第二階段中進行方案比選和線路調整。

兩階段模型的具體步驟如下：1）第一階段為線路初步設計。包括區域初步劃分、區域內部線路單點環路最優解計算。2）第二階段為方案比選和優化。包括對區域內點位劃分進行微調、區域內部線路單點環路優化設計以及細節部分中間點調整。

2.1 案例背景

該文選取現實生活中的一家具有代表性的大型超市來簡述運用上述啟發式算法進行手算線路設計的步驟。根據地圖中超市周邊的住宅小區的分布，已確定需途徑的中間站點共39個。

2.2 第一階段：結合實際算例的線路初步設計

第一階段的任務是用1條或若干條合適的線路將給定的線路站點串聯在一起，其中給定的站點一般是超市經調研需要覆蓋的各小區的出入口或其他較大的客源產生地，線路的起點、終點設在超市。初步設計需要解決的問題是要覆蓋已知站點、應開設多少線路、哪些站點屬于同一條線路以及該線路的最優長度。

根據以超市為圓心的扇形對現有的39個中間站點進行區域劃分，劃分在同一區域的點位視為由一條班車線路進行覆蓋。根據問卷調查顯示（此處不進行展示），82%的購物者能夠接受單程購物路程耗時為大約30 min，因此，對一般的線路來說，運行一周的時間必須保持在滿足75%乘客乘坐在班車上的時間不超過30 min。根據該要求并假設班車行駛時速為20 km/h，暫時設定每條線路的站點數大約為10個。以超市為圓心，放射線條把區域分割為扇形，分割原則如下：1） 保證距離比較近的密集點被劃分到同一個扇區。2）保證每個扇區的中間點個數大約為7～11個。根據上述原則對案例進行扇區劃分，按順時針劃分的結果如圖1所示，共分為區域1、區域2、區域3和區域4，分別對應線路1、線路2、線路3和線路4。

學者對兩點間路徑選擇問題的研究主要集中在模型的構建和算法的求解上。一般采用運籌學中的最短路徑問題來解決，選取傳統的Dijkstra法對模型進行最后的求解。

該文在檢索了大量相關資料的基礎上，發現在現有的線路選擇研究中，目標函數的“最優”標準單一，一般以考慮出行距離最短或出行時間最短為目標，算例中以2個站點間的距離作為目標，對目標函數求解最小值得到該線路的最優解，如公式（1）所示。

式中：X為0-1的變量；C為站點和站點之間公交車運行的平均距離，，=1，2，…。

當X=1時，表示站點在一條線路中緊隨站點（，=1，2，…），所謂“緊隨”是指站點和站點之間沒有其他站點。在這里需要假定班車的運行方向，一般認為班車是朝超市站進發的；在其他情況下，X=0，保證對每條非終點的站點來說，有且只有1個站點緊隨其后，因此約束條件∑ X=1（=1，2，3，…-1）。

C可以排成1個×的矩陣。其中，站點是超市站，即超市班車線路的起終點。

根據區域劃分分為4條線路，對每條線路中的各中間站點進行標注，并進行測距，將任意2點之間的行駛距離進行列表：1） 線路一。對線路一來說，超市所在點位命名為#，其余區域內的中間站點如圖1中標識字母所示（用圈（○）來表示），線路的點位分布如圖1所示，每兩點間的距離見表2。根據計算較優路線為---------#-；等價路線為 #----------#。電子地圖上測距得路線一的最短長度為7.5 km，如果按假設中的超市班車以時速=20 km/h行駛，則行駛1圈的時間為22.5 min。2） 線路二 。字數受限圖表省略，計算方法同線路一，僅表述結論，后同經計算，線路二的較優路線為 #-/--------#。在電子地圖上測距得路線二的最優長度為14.1 km。如果按假設中的超市班車以時速=20 km/h行駛，則行駛1圈的時間為42.3 min。3） 線路三。經計算較優路線為----------/-#-。等價路線為 #----------/-#。由電子地圖上測距得路線三的最優長度為9.7 km。如果按假設中的超市班車以時速V=20 km/h行駛，則行駛1圈的時間為29.1 min。4） 線路四。經計算較優路線為-----------# 和。等價路線為 #------------#。在電子地圖上測距得路線四的最優長度為9.77 km。如果按假設中的超市班車以時速=20 km/h行駛，則行駛1圈的時間為29.31 min。

表2 任意線路站點間距離表

圖1 線路1中間點位圖

2.3 第二階段：結合實際算例的方案比選和優化

第二階段的任務是在第一階段計算結果的基礎上對奇點進行觀察，對中間站的區域劃分進行微調，并對各線路長度進行優化。通過方案對比，挑選最短路徑和最優方案，并且討論造成差異的原因，對實例進行分析，將其中原因一般化。

在為線路三定線的過程中，發現由于存在點/，導致線路三無法一筆畫出，因此，線路為滿足經過站點/而繞行了大量路程。另外發現點/恰好處于線路一的途徑線路上，因此考慮將點/調整進入線路一中。如果線路一增加點/，線路一的長度不發生改變。

而線路三則需要進行重新定線計算長度，經計算線路三+的較優路線為----------#-。等價路線為 #-----------#。在電子地圖上測距得線路三的最優長度為7.05 km，較原有線路三最優長度9.7 km縮短了1.375 km。如果按假設中的超市班車以時速=20 km/h行駛，則行駛1圈的時間較原設計最優線路三縮減了約8 min。優化前-后的總線路長度見表3、表4（將局部點/從線路三調整到線路一中各條線路長度）。

對表3和表4進行比較，發現由于存在/點位，導致線路三無法一筆畫成，而該店恰好處于線路一的最優線路路徑中，因此調整了該點之后，沒有增加線路一的長度，但是卻通過減少繞行而減少了線路三的長度，調整點的確有改善系統的線路長度。

表3 第一階段最優路徑設計結果

表4 第二階段優化后最優路徑計算結果

3 結語

兩階段班車線路設計模型可以在一定邊界條件下得到相對的最優解，即得到班車系統的最短路線。

模型成立的假設是線路條數給定的前提下，通過位置接近的點位劃入同區域（同線路），再對單一線路進行最短的線路求解。由于線性規劃目標的單一性，這些本該作為目標函數的參數卻作為約束條件限制可行解的取值。當班車系統很小時，這個缺陷并不能體現出來；隨著班車系統規模的擴大，這個缺陷將被成倍地放大。因此這個模型只適用于比較簡單的情況。由于現實條件下的復雜的情況，例如機動車限制形式、道路的單向通行等情況都會導致模型中的約束數量大增，使模型求解更加困難，而且也會弱化精確的數學模型求解的優勢。

由于上述的理論算法需要通過計算機程序才能夠實現，因此適用于模型比較簡單但是點數較多的情況，而事實上，超市班車系統是一個相對比較小型和簡單的系統，利用理論的最短路徑方法進行計算復雜度太高，并且由于現實中的約束條件太復雜，例如單行道、機動車禁行等，在建立模型時用數學形式表達現實約束還存在困難。