劉國英　曹才子　吳華香

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

關(guān)鍵詞 圖論思想 最短線路 單目標(biāo)優(yōu)化模型 多目標(biāo)優(yōu)化模型

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A

1公汽線路選擇分析

1.1公汽線路的三種情況

本文依據(jù)公汽行駛的軌跡，綜合考慮實(shí)際情況后將公汽線路主要?jiǎng)澐譃槿N類型：

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

（2）環(huán)行線：對于環(huán)形線路，一次線路無重復(fù)經(jīng)過的站點(diǎn)，以城市中心為基點(diǎn)，從始發(fā)站繞市中心行駛一圈到終點(diǎn)站，且始發(fā)站與終點(diǎn)站相同。

（3）往返線路不一致：上行線、下行線經(jīng)過的站點(diǎn)不完全一致。

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

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

2模型的建立

2.1模型假設(shè)

假設(shè)1：出發(fā)點(diǎn)和目的地都為站點(diǎn)所在地，步行時(shí)間僅為換乘步行時(shí)間；

假設(shè)2：各路徑上公汽發(fā)車頻率相同，相鄰站點(diǎn)平均行駛時(shí)間一定；

假設(shè)3：所有換乘都需再付費(fèi)，因此換乘次數(shù)是費(fèi)用差別產(chǎn)生的主要因素；

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

2.2 模型的準(zhǔn)備

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

其中，為決策變量，當(dāng)，說明弧位于頂點(diǎn)至頂點(diǎn)的線路上，否則。

2.3模型的建立

由于不同的人群乘車時(shí)考慮的側(cè)重點(diǎn)不同，如時(shí)間觀念強(qiáng)的人群側(cè)重縮短時(shí)間；對開銷敏感的節(jié)約型人群側(cè)重減小乘車花費(fèi)；殘疾人士或者不愿轉(zhuǎn)乘的人群側(cè)重減少轉(zhuǎn)乘次數(shù)。針對不同人群，給出三種乘車最佳路線方案，分別為用時(shí)最短方案、費(fèi)用最少方案和綜合最優(yōu)方案，建立如下模型。

2.3.1用時(shí)最短方案

（1）目標(biāo)函數(shù)的建立。

建立最短用時(shí)模型的單目標(biāo)函數(shù)為：

其中從起始點(diǎn)到達(dá)目的地有三種乘車方案，從地直達(dá)地所需時(shí)間為：

換乘一次從地到地?fù)Q乘，再從地到地所需時(shí)間為：

換乘兩次從地到地?fù)Q乘，從地到地?fù)Q乘，再從地到地所所需時(shí)間為：

（2）約束條件的建立。

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

其中，表示換乘次時(shí)乘車所需時(shí)間，表示乘車所需的最短時(shí)間，表示公汽站點(diǎn)之間的平均行駛時(shí)間，表示公汽換乘平均耗時(shí)，表示從站點(diǎn)到站點(diǎn)經(jīng)過的站點(diǎn)個(gè)數(shù)。

2.3.2花費(fèi)最少方案

（1）目標(biāo)函數(shù)的建立。

建立最少費(fèi)用模型的單目標(biāo)函數(shù)為：

MIN = MIN（，，）

其中從起始點(diǎn)到達(dá)目的地有三種乘車方案，從地直達(dá)地所需費(fèi)用為：

換乘一次從地到地?fù)Q乘，再從地到地所需費(fèi)用為：

換乘兩次從地到地?fù)Q乘，從地到地?fù)Q乘，再從地到地所所需費(fèi)用為：

根據(jù)不同的公汽線路收費(fèi)標(biāo)準(zhǔn)，費(fèi)用為：

（2）約束條件的建立。

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

其中，表示從站點(diǎn)到站點(diǎn)經(jīng)過的站點(diǎn)個(gè)數(shù)，表示從站點(diǎn)到站點(diǎn)的費(fèi)用，表示乘車所需最少費(fèi)用。

2.3.3綜合最優(yōu)方案

綜合最優(yōu)方案用時(shí)短費(fèi)用少且換乘次數(shù)少，為使這三方面因素同時(shí)滿足，建立以時(shí)間費(fèi)用和換乘次數(shù)為目標(biāo)的多目標(biāo)函數(shù)：

3模型的求解思路

step1：根據(jù)城市的公汽線路信息數(shù)據(jù)，將公汽線路編號后導(dǎo)入，對每條線路進(jìn)行抽象處理，將其分為上下行線路、往返線路不一致型線路和環(huán)行線路。

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

step3 ：在轉(zhuǎn)乘次數(shù)最少的基礎(chǔ)上考慮行程時(shí)間和乘車費(fèi)用，分別以耗時(shí)最短、費(fèi)用最小為目標(biāo)函數(shù)，以最短時(shí)間矩陣和最少費(fèi)用矩陣為基礎(chǔ)建立單目標(biāo)優(yōu)化模型，給出供公眾選用的多種參考方案以滿足不同乘客需求。

step4 ：建立時(shí)間、換乘次數(shù)、車費(fèi)的多目標(biāo)模型，通過系統(tǒng)的搜索計(jì)算，利用優(yōu)化決策的條件限制，采用基于枚舉的搜索算法使得時(shí)間和費(fèi)用都為最少時(shí)取最優(yōu)。最短時(shí)間為直達(dá)的情況時(shí)其費(fèi)用也最少即為最優(yōu)方案。

4模型的評價(jià)

4.1模型的優(yōu)點(diǎn)及推廣

優(yōu)點(diǎn)：

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

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

推廣：

模型解決的是一個(gè)典型的運(yùn)籌學(xué)最短路線問題，不僅適用于乘客公汽線路選擇問題，而且在工業(yè)、商業(yè)、交通運(yùn)輸、工程技術(shù)、行政管理等領(lǐng)域有著廣泛的應(yīng)用。文中建立的雙目標(biāo)的網(wǎng)絡(luò)模型對圖論類的優(yōu)化問題的求解也可以起到指導(dǎo)作用。

4.2模型的缺點(diǎn)及改進(jìn)

（1）由于假設(shè)相鄰站點(diǎn)平均行駛時(shí)間一定是非現(xiàn)實(shí)的，所以使得模型的計(jì)算與實(shí)際有所偏差，可以嘗試采用更多更有效的指標(biāo)來優(yōu)化模型。

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

參考文獻(xiàn)

[1] 龔劬.圖論與網(wǎng)絡(luò)最優(yōu)化算法[M].重慶大學(xué)出版社，2000.

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