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

曹 奕

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

0 前言

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

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

1.1 研究意義

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

1.2 超市班車(chē)路線線型的分類(lèi)

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

表1 公交線路線形特地和適用性對(duì)照表

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

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

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

1.4 超市班車(chē)線路優(yōu)化問(wèn)題的數(shù)學(xué)簡(jiǎn)化模型

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

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

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

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

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

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

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

2.1 案例背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

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

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