需求響應式公交系統(tǒng)路徑優(yōu)化算法

王力生，帥 斌

(西南交通大學交通運輸與物流學院，四川 成都 610031)

需求響應式公交系統(tǒng)(demand responsive transit System，簡稱DRTS)是近年來國內(nèi)外研究較多的一種新型公交運營方式，它的基本思想是按照潛在乘客預約(如電話預約)的上下車地點與時間來安排公交車輛，實現(xiàn)門到門運輸。與現(xiàn)有的預約式出租車相比，DRTS具有承載率高、社會成本低等優(yōu)點；與常規(guī)公交相比，又具有機動靈活，出行便捷的優(yōu)點。因此，DRTS適用于乘客密度較低的郊區(qū)或者服務于以老年人、殘疾人和小孩為主體的出行群體[1]。

DRTS的運營組織方式的核心是在滿足乘客出行需求的前提下怎樣安排車輛使運營成本最低。這里提供2種思路：在乘客預約時間間隔較大的情況下，考慮一旦預約人數(shù)達到某一數(shù)量N(顯然N不大于公交車容量C)，就安排發(fā)車，并在既有的城市道路網(wǎng)中選擇關于成本最小的歐拉跡或歐拉回路；當預約間隔較小時，考慮安排若干輛公交車，首先把路網(wǎng)中的乘客分派給這些車輛，然后再選擇各個車輛最短的歐拉跡或歐拉圈以使運營成本最低。

本文主要研究第一種情況，把它轉化為圖論中的遍歷性問題，并給出了相關的算法；對于第二種情況，只提出了將其轉化為動態(tài)規(guī)劃問題求解的思路，供廣大讀者朋友參考研究。

1 問題的提出

對于某城市路網(wǎng)，把交叉口作為頂點，交叉口之間的路段作為邊，抽象成如圖1所示的無向圖。

圖1 某城市路網(wǎng)圖

按照從左上到右下的順序為頂點編號：1,2,…，16，頂點1表示車站(這里不考慮多個車站的情況，即公交車從頂點1出發(fā)并回到頂點1)。把頂點之間的路段(如果有的話)表示為lij,(i=1,2,…，15,j=i+1,i+2,…，16)，把每一乘客預約的上下車地點匹配到相應的路段lij(假定沒有乘客愿意在頂點，即道路交叉口上下車，有乘客上下車的邊用三角形標出)，于是產(chǎn)生如下問題：

從1出發(fā)尋找一個歐拉圈(注意，在不影響計算結果的前提下，這里把哈密頓回路作為特殊的歐拉圈考慮)，遍歷圖中若干指定的邊(即乘客上下車地點所在的邊)，使運營成本最小。

與傳統(tǒng)歐拉圈問題(即管梅谷教授提出的著名的中國郵路問題[2])不同的是，這里不要求遍歷圖中所有的邊。乘客預約數(shù)量的不同，對應于引言中提到的2種運營組織方式，即若乘客預約數(shù)量少于一輛公交車的容量C，那么僅需尋找一條運營成本最低的歐拉圈；若乘客數(shù)量多于一輛公交車容量C，那么還涉及乘客分配的問題，較為復雜。下面的算法解決了第一種情況，至于第二種情況只給出了相關的思路。

2 算法

2.1 算法步驟

步驟1：記原圖為G，由若干指定邊組成的生成子圖記為G′，判斷G′是否為歐拉圖，若是則令G*=G′，轉步驟3；若不是則轉步驟2；

步驟2：記生成子圖G′中度數(shù)為奇數(shù)頂點的個數(shù)為n，由圖論基本定理：奇次頂點的個數(shù)一定為偶數(shù)，即n=2k(k=1,2,…)。那么在圖G中尋找頂點i(i=1,2,…，2k-1)到頂點j(j=i+1,i+2,…，2k)的最短路徑Pi,j，以所有奇次頂點為頂點，生成完全圖K2k，對頂點i,j之間的邊賦權Pi,j，那么問題轉化為在完全圖K2k尋找最小邊權匹配的問題。目前，圖論中關于最大邊權匹配已有成熟的算法，請讀者參考文獻[3]。顯然只需引入較大的正整數(shù)M，用M減去K2k中的邊權Pi,j，即可把原問題中的最小邊權匹配問題轉化為最大邊權匹配問題。在最小邊權匹配的任意匹配2點之間添加最短路徑(當該路徑包含屬于G′的邊時，可添加重復邊)，將G′轉化為歐拉圖G″，令G′=G″，轉步驟1；

步驟3：記G*中的頂點集合為V*，若頂點1∈V*，則尋找從頂點1出發(fā)的歐拉圈即為最小歐拉圈L*；若1?V*，則在圖G中尋找頂點1與頂點vk(vk∈V*)的最短路徑，記為P1,vk，此時在G*中添加重復路徑P1,vk就得到歐拉圖G*′，尋找從頂點1出發(fā)的歐拉圈即為最小歐拉圈L*。

對于在圖中尋找最短路、歐拉圈以及最小邊權匹配算法可參考文獻[3],圖論相關算法的MATLAB實現(xiàn)方式可以參考文獻[4]，限于篇幅，算法中未予闡述。

算法可表示為圖2所示的流程圖。

圖2 算法流程圖

2.2 算法證明

為確保由上述算法一定能在賦權圖中尋找到覆蓋若干指定邊的最小歐拉圈，現(xiàn)給出如下引理和定理的證明過程(以下記號同算法步驟)。

引理一：對于賦權圖G及其生成子圖G′，若G′為歐拉圖，則遍歷G′中所有邊的最小歐拉圈一定不包含邊e∈E(G)-E(G′)。(E(G)表示圖G的邊集合，所謂最小歐拉圈或圖是指歐拉圈或圖中所有邊的邊權之和最小，這里認為邊權都為正值)

證明：由歐拉圖的基本定理[5],若圖G′是歐拉圖，那么一定存在只包含G′中所有邊的歐拉圈L，假定存在包含任意一條ek(k=1,2,…，m)∈E(G)-E(G′)且遍歷G′中所有邊的歐拉圈L′滿足條件，必有l(wèi)(L′)>l(L)(l(L)表示歐拉圈L的長度)，與“最小歐拉圈”矛盾，因此引理成立。

引理二：對于賦權圖G及其生成子圖G′，若G′不是歐拉圖，則最小邊權匹配法一定能在G中尋找到覆蓋圖G′中所有邊的最小歐拉子圖G″。(最小邊權匹配是指在賦權圖中偶數(shù)個頂點之間，尋找以兩個頂點為一組且滿足每組頂點之間路徑總和最小的問題)

證明：引理分為兩步證明，其一是G″為歐拉圖，其二是G″的最小性。要證明G″為歐拉圖，只需證明G″中頂點的度均為偶數(shù)。由圖論基本定理[5]，任意圖中奇次頂點的個數(shù)為偶數(shù)，由于G′不是歐拉圖，則必含偶數(shù)個奇次頂點，由最小邊權匹配的算法過程，在任意2個奇次頂點之間加一條路徑，那么G′中奇次頂點的度數(shù)都增加1，偶次頂點度數(shù)不變，因此所有頂點度均為偶數(shù)，即一定可以產(chǎn)生歐拉圖G″。對于G″最小性的證明，設存在異于圖G″的圖G″′是圖G中覆蓋G′所有邊的最小歐拉圖，由最小邊權匹配算法過程保證G′轉變?yōu)闅W拉圖G″增加路徑邊權總和最小，必有l(wèi)(G?)>l(G″)，與G″′是最小歐拉圈矛盾；因此G″是G中覆蓋圖G′的最小歐拉子圖。

引理三：對于賦權圖G及其生成子圖G′，其頂點集分別表示為V,V′，若G′為歐拉圖，?v∈V-V′，記Pv,v′表示v到v′(v′∈V′)的最短路徑，那么添加重復路徑Pv,v′，得到圖G中包含G′與v的最小歐拉圖G″。

定理：按照2.1節(jié)中的算法步驟，一定能在賦權圖中尋找到覆蓋若干指定邊和指定頂點(如公交車車站)的最小歐拉圈。

證明：分情況對定理進行證明。1)若指定邊組成的子圖為歐拉圖，當指定頂點屬于該子圖時，由引理一，一定可以在該子圖中找出若干歐拉圈，取其中最小的歐拉圈即滿足條件；當指定頂點不屬于該子圖時，由引理三，可在指定頂點和歐拉子圖個頂點的重復最短路徑形成新的歐拉圖，再利用引理一即得證。2)若指定邊組成的子圖不是歐拉圖，那么由引理二，可將子圖轉化為歐拉圖，回到1)的情形，也可找到最小歐拉圈。綜合上述2種情形，那么一定能在賦權圖中尋找到覆蓋若干指定邊和指定頂點的最小歐拉圈。

2.3 乘客數(shù)量大于一輛公交車容量的算法思路

值得說明的是，上述算法并不適用于乘客數(shù)量大于一輛公交車容量的情形，即不能通過首先安排一輛公交車裝載數(shù)目為容量C的乘客，安排第二輛公交車時把第一輛公交車輸送的人從圖中去掉，以此類推。一個簡單的例子是當旅客上下車地點不變時，若某一路段上車人數(shù)為公交車容量C，那么不需遍歷其他上車地點以及相應的下車地點的邊了。

為解決這一問題，這里提供2種思路，礙于作者水平，不能深入探討，有興趣的讀者可以查找相關的文獻資料。

思路一：轉化為一維動態(tài)規(guī)劃問題。把每安排一輛車記為一個階段，狀態(tài)變量記為當前路網(wǎng)上需要覆蓋的邊數(shù)，狀態(tài)轉移表述為前一輛車輸送的乘客產(chǎn)生的覆蓋邊的減少。與上面的例子不同的是，這里每一階段尋找車輛歐拉圈的過程應轉化為“容量約束中國郵遞員問題”[3]，目標函數(shù)為各階段產(chǎn)生的運營成本之和最小。但是，已有學者證明“容量約束中國郵遞員問題”是NP完全問題，目前尚無有效的算法。

3 算例

為圖1的各邊賦權并指定乘客上下車地點所在的邊(圖中三角形覆蓋的邊)，得到圖3，在該圖中按照上述算法尋找從頂點1出發(fā)并覆蓋指定邊的最小歐拉圈。

圖3 賦權及指定邊無向圖

步驟1：找出由指定邊組成的生成子圖4，因為有奇次頂點，故不是歐拉圖，奇次頂點為：3,4,5,8,12,14。

圖4 生成子圖

步驟2：在原圖3中，尋找上述6個頂點中任意2個之間的最短路徑，如表1所示。

表1 奇次頂點之間最短路徑表

表1(續(xù))

以6個奇次頂點為頂點，生成完全圖，各頂點之間的邊權記為相應的最短路徑長度，得到圖5。

圖5 邊權為最短路徑長度的完全圖

在圖5中尋找最小邊權匹配集合，得到{3,5},{4,14},{8,12}，此時邊權之和12+9+4=25為最小，那么在生成子圖4中添加路徑{3,5},{4,14},{8,12}得到歐拉圖6，圖中虛線表示添加的路徑，重復邊表示走2次。

圖6 歐拉子圖

步驟3：在原圖3中尋找頂點1到圖6各頂點的最短路徑，結果為1-3，路徑長度為6，在子圖6中添加頂點1即重復路徑1-3，得到新的子圖7。

圖7 新子圖

在歐拉子圖7中按照尋找歐拉圈的Fleury算法，可得唯一歐拉圈：

1-3-5-8-12-14-11-4-8-12-9-5-3-1

在原圖3中用粗實線標出，用箭頭表示行駛方向與次數(shù)(對存在歧義的地方給出了數(shù)字標注，數(shù)字大小表示先后順序)，即得覆蓋所有指定邊的最小歐拉圈，如圖8所示。此時，最小成本為90。

圖8 標注車輛行駛路徑圖

4 結束語

本文研究了需求響應式公交系統(tǒng)路徑的優(yōu)化算法，將需求響應式公交系統(tǒng)路徑選擇問題抽象為在圖中尋找覆蓋若干條指定邊的歐拉圈問題，提出乘客數(shù)量不大于公交車容量和乘客數(shù)量大于公交車容量2種情況下的公交車運營組織方式。算例給出了尋找覆蓋若干條指定邊的歐拉圈算法，至于其“最小性”的證明請參考算例部分給出的引理和證明。本文把乘客預定數(shù)量不大于公交車容量限制條件下的DRTS路徑選擇問題轉化為圖論中尋找覆蓋若干指定邊的最小歐拉圈問題，并研究了相關的算法；對于乘客預定數(shù)量大于公交車容量的情況，給出了轉化為動態(tài)規(guī)劃問題的思路。

[1]謝成輝,楊冰.城市公共交通發(fā)展新趨勢[J].國外公路,2001，21(2):49-53.

[2]管梅谷.中國投遞員問題綜述[J].數(shù)學研究與評論,1984，4(1)：113-119.

[3]龔劬 .圖論與網(wǎng)絡最優(yōu)化算法[M].重慶：重慶大學出版社,2009:95.

[4]王海英,黃強,李傳濤，等 .圖論算法及其MATLAB實現(xiàn)[M].北京：北京航空航天大學出版社,2009：21-26

[5]Alan Tucker. 應用組合數(shù)學[M]. 馮速，譯. 北京：人民郵電出版社,2009:19.

[6]滕宇,梁方楚.動態(tài)規(guī)劃原理及應用[M].成都：西南交通大學出版社,2011:81.