曹 奕

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

0 前言

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

1 超市班車交通線路的設計優(yōu)化

1.1 研究意義

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

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

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

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

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

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

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

1.4 超市班車線路優(yōu)化問題的數(shù)學簡化模型

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

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

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

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

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

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

兩階段模型的具體步驟如下：1）第一階段為線路初步設計。包括區(qū)域初步劃分、區(qū)域內(nèi)部線路單點環(huán)路最優(yōu)解計算。2）第二階段為方案比選和優(yōu)化。包括對區(qū)域內(nèi)點位劃分進行微調(diào)、區(qū)域內(nèi)部線路單點環(huán)路優(yōu)化設計以及細節(jié)部分中間點調(diào)整。

2.1 案例背景

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

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

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

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

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

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

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

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

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

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

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

圖1 線路1中間點位圖

2.3 第二階段：結(jié)合實際算例的方案比選和優(yōu)化

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

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

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

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

表3 第一階段最優(yōu)路徑設計結(jié)果

表4 第二階段優(yōu)化后最優(yōu)路徑計算結(jié)果

3 結(jié)語

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

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

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