超市班車線路設(shè)計兩階段模型

曹 奕

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

0 前言

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

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

1.1 研究意義

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

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

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

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

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

1.3 超市班車線路的設(shè)計步驟

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

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

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

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

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

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

2 超市班車兩階段模型及實(shí)際算例

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

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

2.1 案例背景

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

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

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

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

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

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

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

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

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

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

表2 任意線路站點(diǎn)間距離表

圖1 線路1中間點(diǎn)位圖

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

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

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

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

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

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

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

3 結(jié)語

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

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

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