乘客公汽線路選擇優化模型

劉國英　曹才子　吳華香

摘 要 公汽是整個城市交通系統中的一個重要組成部分，在方便人們出行的同時也給乘客帶來了線路選擇的困擾。本文給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法，首先利用圖論思想建立鄰接矩陣，將其轉化為有向最短線路問題，再根據公眾出行對時間、費用和換乘次數的不同需求，建立單目標優化模型，得出單目標最優方案；此外通過建立多目標優化模型，還提供了同時考慮三種因素的綜合最優方案，供乘客選擇符合自己乘車需求的路線。

關鍵詞 圖論思想 最短線路 單目標優化模型 多目標優化模型

中圖分類號：TP301 文獻標識碼：A

1公汽線路選擇分析

1.1公汽線路的三種情況

本文依據公汽行駛的軌跡，綜合考慮實際情況后將公汽線路主要劃分為三種類型：

（1）上行線、下行線原路返回：這種線路有兩個端點站，在兩個端點站之間雙向行車，而且兩個方向上的行車路線相同，經過同樣的站點序列。由于路線的方向不同，因此上行線和下行線可抽象成兩條線路處理，線路號與收費規則相同。

（2）環行線：對于環形線路，一次線路無重復經過的站點，以城市中心為基點，從始發站繞市中心行駛一圈到終點站，且始發站與終點站相同。

（3）往返線路不一致：上行線、下行線經過的站點不完全一致。

1.2公汽線路選擇的影響因素

隨著城市化的加速，城市交通線路逐漸四通八達，公汽作為城市重要的交通方式之一，在優化城市交通，方便市民出行，發展城市經濟等方面均發揮著重要的作用。在實際生活中，公眾乘坐公汽主要考慮步行時間、轉乘次數、行程時間、車站始發情況、負載量及乘車費用等因素，其中轉乘次數、時間、車費三個因素對乘客公汽線路的選擇影響最大，因此本文主要基于這三個因素建立優化模型來設計不同的乘車方案以滿足乘客不同的出行需求。其中對于換乘次數，本文把換乘次數限制在轉乘兩次之內，這符合大多數乘客的乘車習慣，換乘次數分別為直達、一次換乘和兩次換乘；時間由乘車時間和換乘時間決定，換乘時間包含步行時間和等車時間；費用的差別主要由換乘次數決定，換乘次數越多費用越高。

2模型的建立

2.1模型假設

假設1：出發點和目的地都為站點所在地，步行時間僅為換乘步行時間；

假設2：各路徑上公汽發車頻率相同，相鄰站點平均行駛時間一定；

假設3：所有換乘都需再付費，因此換乘次數是費用差別產生的主要因素；

假設4：為了模型的簡化和計算方便并且考慮到交通系統的合理性及完善性，實際生活中兩次以上換乘情況出現較少，因此本文不討論兩次以上的換乘方案。

2.2 模型的準備

對于特定城市的公汽路線，將所有站點的車輛運行線路做出有P個頂點的向量圖，P為該城市站點總數。其中為始發站的頂點僅有出的邊無進的邊，終點站的頂點僅有進的邊無出的邊，對于中間的站點出入邊都有。用E表示弧的集合，設為鄰接矩陣，其分量為

其中，為決策變量，當，說明弧位于頂點至頂點的線路上，否則。

2.3模型的建立

由于不同的人群乘車時考慮的側重點不同，如時間觀念強的人群側重縮短時間；對開銷敏感的節約型人群側重減小乘車花費；殘疾人士或者不愿轉乘的人群側重減少轉乘次數。針對不同人群，給出三種乘車最佳路線方案，分別為用時最短方案、費用最少方案和綜合最優方案，建立如下模型。

2.3.1用時最短方案

（1）目標函數的建立。

建立最短用時模型的單目標函數為：

其中從起始點到達目的地有三種乘車方案，從地直達地所需時間為：

換乘一次從地到地換乘，再從地到地所需時間為：

換乘兩次從地到地換乘，從地到地換乘，再從地到地所所需時間為：

（2）約束條件的建立。

約束所有的線路在該有向圖上：

其中，表示換乘次時乘車所需時間，表示乘車所需的最短時間，表示公汽站點之間的平均行駛時間，表示公汽換乘平均耗時，表示從站點到站點經過的站點個數。

2.3.2花費最少方案

（1）目標函數的建立。

建立最少費用模型的單目標函數為：

MIN = MIN（，，）

其中從起始點到達目的地有三種乘車方案，從地直達地所需費用為：

換乘一次從地到地換乘，再從地到地所需費用為：

換乘兩次從地到地換乘，從地到地換乘，再從地到地所所需費用為：

根據不同的公汽線路收費標準，費用為：

（2）約束條件的建立。

約束所有的線路在該有向圖上：

其中，表示從站點到站點經過的站點個數，表示從站點到站點的費用，表示乘車所需最少費用。

2.3.3綜合最優方案

綜合最優方案用時短費用少且換乘次數少，為使這三方面因素同時滿足，建立以時間費用和換乘次數為目標的多目標函數：

3模型的求解思路

step1：根據城市的公汽線路信息數據，將公汽線路編號后導入，對每條線路進行抽象處理，將其分為上下行線路、往返線路不一致型線路和環行線路。

step2 ：利用圖論的思想建立線路矩陣和鄰接矩陣，將其轉化為有向最短線路問題。

step3 ：在轉乘次數最少的基礎上考慮行程時間和乘車費用，分別以耗時最短、費用最小為目標函數，以最短時間矩陣和最少費用矩陣為基礎建立單目標優化模型，給出供公眾選用的多種參考方案以滿足不同乘客需求。

step4 ：建立時間、換乘次數、車費的多目標模型，通過系統的搜索計算，利用優化決策的條件限制，采用基于枚舉的搜索算法使得時間和費用都為最少時取最優。最短時間為直達的情況時其費用也最少即為最優方案。

4模型的評價

4.1模型的優點及推廣

優點：

（1）站在乘客的角度，對乘客實際生活中線路選擇可能會引起困擾的因素進行了詳細分析，通過建立不同模型優化線路選擇，給不同需求的乘客提供了單目標最優和綜合最優的線路選擇方案，使得模型的通用性、推廣性更強。

（2）模型中的距離采用的是實際線路距離而非起點終點兩點之間的直線距離，對乘客有更明確的指導。

推廣：

模型解決的是一個典型的運籌學最短路線問題，不僅適用于乘客公汽線路選擇問題，而且在工業、商業、交通運輸、工程技術、行政管理等領域有著廣泛的應用。文中建立的雙目標的網絡模型對圖論類的優化問題的求解也可以起到指導作用。

4.2模型的缺點及改進

（1）由于假設相鄰站點平均行駛時間一定是非現實的，所以使得模型的計算與實際有所偏差，可以嘗試采用更多更有效的指標來優化模型。

（2）在給出路徑源和目的地的條件下，模型通過算法可求得應走的路線，所花的時間及費用。但在現實生活中，交通系統隨時可能發生變化，如上下班時線路交通擁堵或者因交通事故暫時中斷，這樣我們的路徑推薦模型就可能將用戶帶到已經中斷或者是非常擁擠的線路中。但這些在模型中未能反應出來，應建立動態的系統，這樣才能根據最新的數據信息判斷出最優方案。

參考文獻

[1] 龔劬.圖論與網絡最優化算法[M].重慶大學出版社，2000.

[2] 謝金星.優化建模與LINDO/LINGO軟件[M].北京：清華大學出版社，2005：180-190.