馮存梅 李 威 沈 忱

（1.上海電機(jī)學(xué)院 電子信息學(xué)院，中國(guó) 上海201306；2.上海電機(jī)學(xué)院 機(jī)械學(xué)院，中國(guó) 上海201306）

0 研究背景

班車(chē)站點(diǎn)及線路的優(yōu)化設(shè)計(jì)是屬于典型的車(chē)輛路徑問(wèn)題（Vehicle Routing Problem,即VRP 問(wèn)題）。VRP 問(wèn)題在國(guó)外最早是由Dantzing 和Ramser[1]于1959 年首次提出的。早在1962 年，Balinski 等人就提出集分割[2]，直接考慮可行解集合并在此基礎(chǔ)上進(jìn)行優(yōu)化建立了最簡(jiǎn)單的VRP 模型。1971 年，Eilon 等人[3]提出將動(dòng)態(tài)規(guī)劃法用于固定車(chē)輛的VRP,通過(guò)遞歸方法求解。1991 年，Gendreau 等人[4]將禁忌搜索方法應(yīng)用于VRP。M.L.Fisher 于1995 年 在 “Vehicle Routing Handbooks in Operations Research&Management Science”[5]中對(duì)車(chē)輛路徑問(wèn)題作了總結(jié)，他把車(chē)輛路徑問(wèn)題的研究方法歸結(jié)為三個(gè)階段。第一個(gè)階段，是20 世紀(jì)60 年代到70 年代，這個(gè)階段主要是應(yīng)用一些簡(jiǎn)單的啟發(fā)式方法來(lái)研究車(chē)輛路徑問(wèn)題，研究的重點(diǎn)主要局限于局部搜索和交換技術(shù)；第二個(gè)階段，是20 世紀(jì)70 年代到80 年代基于啟發(fā)式方法的設(shè)計(jì)階段，這個(gè)階段主要是利用不同于一般啟發(fā)式方法的近似優(yōu)化算法來(lái)求解車(chē)輛路徑問(wèn)題。到了第三階段，即20 世紀(jì)80 年代至今，研究的重點(diǎn)主要放在精確的優(yōu)化算法和新興的人工智能算法，包括模擬退火算法、禁忌搜索算法、遺傳算法和人工神經(jīng)元網(wǎng)絡(luò)方法[6]。

在國(guó)內(nèi)對(duì)VRP 研究最早的是郭耀煌教授，1989 年郭教授與其學(xué)生就多車(chē)場(chǎng)多車(chē)型等問(wèn)題進(jìn)行了研究[7]。1999 年姜大立等人[8]建立了VRP 的遺傳算法。2001 年，李嘉等人[9]設(shè)計(jì)了遺傳算法和禁忌搜索啟發(fā)式的混合算法。2004 年崔雪麗等人基于人工螞蟻系統(tǒng)給出了快速求解VRP 的螞蟻搜索算法。還有不少研究者均對(duì)VRP 的研究做出了很大的貢獻(xiàn)。單這些研究都是理論的東西，能夠更好的解決實(shí)際問(wèn)題才能說(shuō)明研究的價(jià)值。所以這些研究應(yīng)該更偏向?qū)嶋H問(wèn)題。

1 符號(hào)說(shuō)明

M 企業(yè)或單位乘車(chē)總?cè)藬?shù)

L 總車(chē)輛數(shù)(k 表示第k 輛車(chē))

Z 總站點(diǎn)數(shù)

N 總路徑數(shù)

C 每輛車(chē)的容量

Si第i 條路線

Pi第i 個(gè)站點(diǎn)

Yi第Si條路線的總乘客數(shù)

ωijk車(chē)輛k 從Pi站到Pj站的路程

Tijk車(chē)輛k 從Pi站到Pj站經(jīng)歷的時(shí)間

2 班車(chē)站點(diǎn)設(shè)置的數(shù)學(xué)模型

設(shè)置站點(diǎn)的第一步是統(tǒng)計(jì)企業(yè)或單位的所有乘客的住址坐標(biāo)（即住址所在的經(jīng)緯度可利用google earth 標(biāo)出）。記每位乘客的住址坐標(biāo)為（ri，ci）（ri為經(jīng)度ci為緯度）。假設(shè)共要設(shè)置站點(diǎn)Z 個(gè),第j 個(gè)站點(diǎn)的坐標(biāo)為（xj，yj）（xj為經(jīng)度yj為緯度）。[10]

為使每位乘客到達(dá)站點(diǎn)距離的總路程最短及每位乘客到達(dá)站點(diǎn)的距離均衡以下給出總距離函數(shù)和最大距離與最小距離之差函數(shù)：

在設(shè)置站點(diǎn)的過(guò)程中還要考慮乘客到達(dá)站點(diǎn)所能承受的最大距離。假設(shè)乘客所能承受的最大距離為d1則有：

在衡量總距離與最大最小距離偏差時(shí)可在兩函數(shù)前加權(quán)重系數(shù)以更清楚地反映實(shí)際情況，綜合以上，可建立如下班車(chē)站點(diǎn)設(shè)置的數(shù)學(xué)模型：

3 路線的優(yōu)化設(shè)計(jì)

線路的設(shè)計(jì)優(yōu)化模型建立過(guò)程中我們從多樣性角度出發(fā)并結(jié)合實(shí)際情況建立了兩種線路的模型。和多數(shù)研究者不同我們考慮了實(shí)際班車(chē)站點(diǎn)和路線在不同企業(yè)或單位中有些比較復(fù)雜但有些比較簡(jiǎn)單，復(fù)雜的問(wèn)題往往會(huì)有更多的目標(biāo)和約束條件，解的過(guò)程也要復(fù)雜很多這是一種情況。在相對(duì)簡(jiǎn)單的情況若仍按照復(fù)雜模型的思路和計(jì)算方法不僅得不到較好的結(jié)果還會(huì)浪費(fèi)過(guò)多的時(shí)間和精力，是不經(jīng)濟(jì)也是不實(shí)際的。因此我們建立了根據(jù)站點(diǎn)數(shù)量不同而路線安排也不同的兩種模型。即以下的模型一和模型二。

模型一：

此模型是針對(duì)一些乘客人數(shù)較少，站點(diǎn)較少或運(yùn)輸資源有限等條件下建立的單一車(chē)輛單一路經(jīng)的數(shù)學(xué)模型。僅僅適用于小型企業(yè)或單位，這種模型相對(duì)簡(jiǎn)單但在實(shí)際應(yīng)用中卻是經(jīng)常要用到的。

在建立此模型中我們假設(shè)只有一輛車(chē)，車(chē)的容量足夠容納所有乘客。在站點(diǎn)已知且站點(diǎn)數(shù)目不是很多（說(shuō)明：站點(diǎn)不多是指在總乘客數(shù)小于車(chē)容量下站點(diǎn)數(shù)一般小于20 個(gè)，此處20 只是對(duì)一般情況的假定，實(shí)際中具體個(gè)數(shù)應(yīng)按實(shí)際需要設(shè)定）的情況下要求：①車(chē)要經(jīng)過(guò)所有站點(diǎn)②車(chē)的路線最短③車(chē)輛行駛時(shí)間最短④除特殊情況外每個(gè)站點(diǎn)只經(jīng)過(guò)一次（說(shuō)明：特殊情況是指如不再次經(jīng)過(guò)此站點(diǎn)車(chē)輛無(wú)法返回）。

從以上要求中可以看出此問(wèn)題應(yīng)屬于TSP （Travelling Salesman Problem）問(wèn)題。此問(wèn)題仍屬于NP-Complete 難題，許多學(xué)者在此問(wèn)題上都花費(fèi)了大量的精力但目前仍沒(méi)有徹底解決該問(wèn)題的方法。這并不意味著此處是做無(wú)用功，在簡(jiǎn)化數(shù)據(jù)和理想化一些條件后仍有一些有效的解決方法。

在上述要求中沒(méi)有提及成本問(wèn)題，其實(shí)對(duì)于單一車(chē)輛單一路徑，車(chē)輛的成本是固定的。剩余的就只有運(yùn)行的成本，運(yùn)行的成本只與路程有關(guān)即只要求。

由以上要求可建立模型如下：

對(duì)目標(biāo)函數(shù)（1）（2）其中（1）表示車(chē)輛行駛總路程最短（2）表示車(chē)輛行駛時(shí)間最短。對(duì)單一路徑來(lái)說(shuō)當(dāng)車(chē)速一定時(shí)，路程和時(shí)間是成正比的。但為什么此處既對(duì)路程進(jìn)行約束又對(duì)時(shí)間進(jìn)行約束在此說(shuō)明一下。在下文中會(huì)涉及道路飽和度的因素當(dāng)滿(mǎn)足（1）時(shí)在某些情況下會(huì)因?yàn)榈缆愤_(dá)到飽和而使運(yùn)行時(shí)間過(guò)長(zhǎng)，此時(shí)就會(huì)受到（2）的約束改變路線即使行駛路程增加但行駛的時(shí)間卻比原先減少了，這樣更有利于車(chē)輛運(yùn)行效率，也更符合實(shí)際情況。第一個(gè)約束條件表示乘客總數(shù)不大于車(chē)的容量。第二個(gè)約束條件表示車(chē)必須經(jīng)過(guò)每一個(gè)站點(diǎn)。第三個(gè)約束條件表示車(chē)從1 站點(diǎn)出發(fā)必須回到1 站點(diǎn)（假設(shè)1 站點(diǎn)為目的地）。第四個(gè)約束條件表示變量x 的0-1 約束。第七第八約束條件分別表示只有一條路徑和只有一輛車(chē)。

模型二：

此模型較模型一要復(fù)雜，是更具有廣泛性和實(shí)用性的一般性模型。模型二是針對(duì)多人員多站點(diǎn)多線路多種因素綜合考慮建立的。因?yàn)槭且话阈阅Ｐ退阅Ｐ投^模型一相比具有多條線路，多車(chē)輛。在設(shè)置好站點(diǎn)后我們先用floyd 算法求出所有站點(diǎn)之間的最短路，由最短路依次從距原點(diǎn)最遠(yuǎn)，第二遠(yuǎn)…第N 遠(yuǎn)為起點(diǎn)設(shè)置N 條線路，設(shè)置線路按兩條原則一是盡量走最短路二是所有線路盡量囊括所有站點(diǎn)對(duì)有些特殊情況則另作分析。具體方法見(jiàn)模型算法設(shè)計(jì)。

在多條路線中車(chē)輛數(shù)既不能少于總需求量也不能過(guò)多，車(chē)輛數(shù)是決定成本的重要因素所以目標(biāo)函數(shù)首先應(yīng)滿(mǎn)足使總車(chē)輛數(shù)達(dá)到最少。即：

車(chē)輛達(dá)到最少是首先決定因素其次是使所有車(chē)輛行駛總路程最短，因?yàn)槌?chē)輛的固定成本外路程所決定的運(yùn)行成本從長(zhǎng)期來(lái)看也是重要的因素。即：

同樣在保證總路程最短的前一約束下還要使時(shí)間達(dá)到最小化。設(shè)定時(shí)間的約束原因如模型一中設(shè)定時(shí)間約束的一樣，同樣是因?yàn)榈缆凤柡投鹊目紤]，其約束如下：

在所有路線中為出于對(duì)乘客滿(mǎn)意度和公平性的考慮應(yīng)使最長(zhǎng)路線與最短路線的差值在一定的可接受范圍內(nèi)，假定最大差值為d2則有：

綜合以上模型可建立如下：

min（α2f2＋α3f3＋α4f4＋α5f5）

以上模型中目標(biāo)函數(shù)的意義在上文中已說(shuō)明此處說(shuō)明一下約束條件的意義：約束條件一表示運(yùn)載能力的限制即最大運(yùn)載量要大于總?cè)藬?shù)。約束條件二表示每條路線的距離。約束條件三表示任意一位乘客只能乘坐一輛車(chē)。約束條件四表示每輛車(chē)的載客量不超過(guò)車(chē)的容量。約束條件五表示任意站點(diǎn)至少有一輛車(chē)經(jīng)過(guò)。約束條件六表示同一輛車(chē)可以從pi站到pj站也可以從pj站到pi站即下行方向?yàn)樯闲蟹较虻姆聪?。約束條件七表示上行方向各路線的目的地為終點(diǎn)站下行方向各路線的發(fā)車(chē)點(diǎn)為終點(diǎn)站（假設(shè)第Z 站為終點(diǎn)站）。

4 道路飽和度的考慮

此處道路飽和度并沒(méi)有用符號(hào)在模型中表示出來(lái)是出于對(duì)模型求解可行性的考慮，因?yàn)榫退銢](méi)有考慮道路飽和度此模型的求解也相當(dāng)困難。但是道路飽和度是實(shí)際問(wèn)題中不得不考慮的一項(xiàng)因素，特別是在大城市的上下班高峰期，往往會(huì)因?yàn)榻煌ǘ氯速M(fèi)大量時(shí)間這是很不合理的。此處對(duì)道路飽和度的考慮，實(shí)際上也是對(duì)路線的修正因?yàn)樵谟行┮堰_(dá)到飽和的道路再安排車(chē)輛通行就不滿(mǎn)足時(shí)間的約束，就需要對(duì)線路進(jìn)行調(diào)整。因?yàn)榈缆肥裁磿r(shí)候達(dá)到飽和往往與時(shí)間有關(guān)，這就要根據(jù)對(duì)不同環(huán)境的實(shí)際經(jīng)驗(yàn)來(lái)判定。當(dāng)?shù)缆愤_(dá)到飽和時(shí)即通行時(shí)間遠(yuǎn)超正常通行的時(shí)間，就在此時(shí)刻對(duì)此線路采用繞道而行的調(diào)整方案。

例如車(chē)輛k 在某時(shí)刻t 從pi站到pj站，在時(shí)刻t 此時(shí)道路ωijk達(dá)到飽和。則車(chē)輛k 在pi站與pj站途中繞經(jīng)pα站，若滿(mǎn)足Tiαk＋Tαjk＜Tijk原來(lái)的路徑就改為車(chē)輛K 從pi站到pα站再到pj站。這樣雖然多走了一些路程但卻節(jié)省了一部分時(shí)間從效率角度講這樣做是合理的。

但對(duì)時(shí)刻t 模型和算法中是無(wú)法給出的，因?yàn)槠湟籺 的數(shù)值無(wú)法確定其二t 具有不穩(wěn)定性即每天情況可能不一樣，只有根據(jù)實(shí)際經(jīng)驗(yàn)才能確定。模型算法最終給出的結(jié)果只要根據(jù)實(shí)際經(jīng)驗(yàn)來(lái)作調(diào)整即可，所以此處只做說(shuō)明。

5 站點(diǎn)設(shè)置的算法設(shè)計(jì)

因?yàn)閷?duì)不同的案例站點(diǎn)的設(shè)置千變?nèi)f化，無(wú)法給出一個(gè)能保證最優(yōu)最精確的解，所以站點(diǎn)設(shè)置算法我們采用一般情況下的啟發(fā)式算法。如上文所描述模型思想按照算法步驟在一般情況下均可得到較滿(mǎn)意的結(jié)果。

（1）輸入：乘客到達(dá)站點(diǎn)所能承受的最大距離d1以及距離函數(shù)與距離偏差函數(shù)的權(quán)重系數(shù)α1，α2；

（2）在地圖上標(biāo)注出每一位乘客的住址（ri，ci）（實(shí)際操作可用google earth 由經(jīng)緯度標(biāo)注出）；

（3）在地圖上建立合理的坐標(biāo)系將乘客住址的經(jīng)緯度轉(zhuǎn)換成坐標(biāo)系中的實(shí)際坐標(biāo)；

（5）統(tǒng)計(jì)出總的區(qū)域個(gè)數(shù)Z 和每個(gè)區(qū)域的住址點(diǎn)數(shù)及乘客數(shù)M；

（6）計(jì)算出每個(gè)圓或矩形的中心（此中心為該區(qū)域總路程最短的中心或住址點(diǎn)的重心），并將這些點(diǎn)的坐標(biāo)作為站點(diǎn)的地理位置；

（7）輸出：所有的站點(diǎn)位置的坐標(biāo)及每個(gè)站點(diǎn)的人數(shù)。

6 路線模型一的算法設(shè)計(jì)

對(duì)于路線一可看做是簡(jiǎn)化的TSP 問(wèn)題,在圖論中有類(lèi)似像哈密爾頓圖以及二次逐次修正法這樣解決行遍性問(wèn)題的一般方法。哈密爾頓圖的定義：設(shè)G＝（V，E）是連通無(wú)向圖，經(jīng)過(guò)G 的每個(gè)頂點(diǎn)正好一次的路徑稱(chēng)為G 的一條哈密爾頓路徑，經(jīng)過(guò)G 的每個(gè)頂點(diǎn)正好一次的圈稱(chēng)為G 的哈密爾頓圈或H 圈，含H 圈的圖稱(chēng)為哈密爾頓圖或H 圖。[11]

在推銷(xiāo)員問(wèn)題中經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次權(quán)最小的閉通路稱(chēng)為最佳推銷(xiāo)員回路。一般來(lái)說(shuō)最佳哈密爾頓圈不一定是最佳推銷(xiāo)員回路，最佳推銷(xiāo)員回路也不一定是最佳哈密爾頓圈。像模型一這樣求單車(chē)路程最短不適合用求哈密爾頓圖的方法，而二次逐次修正法雖然是近似解法卻往往能給出滿(mǎn)意的結(jié)果。但二次逐次修正法的前提是要求所解圖必須是完備圖，對(duì)于車(chē)輛站點(diǎn)路線來(lái)說(shuō)很少有滿(mǎn)足此要求的路線圖。這里我們對(duì)于不滿(mǎn)足條件的圖用替代的方法構(gòu)造成完備圖。即用最短路代替沒(méi)有相鄰的點(diǎn)之間的路徑。具體算法如下：

1）標(biāo)記所有站點(diǎn)（v1v2…vi…vj…vn）并計(jì)算出所有連通站點(diǎn)之間的距離，做出站點(diǎn)路線圖的帶權(quán)鄰接矩陣W。

2）由鄰接矩陣W 應(yīng)用Floyd 算法計(jì)算出此站點(diǎn)路線圖的最短路。

3）任取初始H 圈：C0＝v1v2…vi…vj…vnv1。

4）由于任取的初始H 圈中有些排列相鄰的站點(diǎn)之間在實(shí)際中并不直接相鄰，所以對(duì)這些站點(diǎn)之間的權(quán)值由（2）中所求最短路代替。

5）對(duì)所有i，j，1＜i＋j＜n 若W（vi，vj）＋W（vi＋1vj＋1）＜W（vivi＋1）＋W（vjvj＋1）則在C0中刪去邊（vivi＋1）和（vjvj＋1）加 入邊（vi，vj）和（vi＋1vj＋1），形成新的圈C，即：C＝v1v2…vivjvj－1…vi＋1vj＋1…vnv1。

6）對(duì)C 重復(fù)步驟⑷直到條件不滿(mǎn)足為止，最后求得的C 即為最佳H 圈。

7）將所求H 圈中站點(diǎn)序列從發(fā)車(chē)站依次記錄最終所得站點(diǎn)序列的路徑即為模型一的車(chē)輛路徑。

7 路線模型二的算法設(shè)計(jì)

模型二是屬于多線路的一般性模型，對(duì)于此類(lèi)模型的求解大部分研究者都用了像遺傳算法，啟發(fā)式算法，蟻群算法，動(dòng)態(tài)優(yōu)化法等算法。本文也不例外采用了啟發(fā)式算法，因?yàn)檫@個(gè)模型本身就比較復(fù)雜再由于實(shí)際情況的各種變化，很難給出能解出穩(wěn)定結(jié)果的算法。啟發(fā)式算法雖然不一定能給出準(zhǔn)確結(jié)果，卻能根據(jù)實(shí)際經(jīng)驗(yàn)在復(fù)雜的環(huán)境中給出讓人較為滿(mǎn)意的結(jié)果。其算法過(guò)程具有可調(diào)節(jié)性，在不同條件下很容易根據(jù)實(shí)際情況調(diào)整，使其更切合實(shí)際。具體算法如下：

1）輸入：最長(zhǎng)路線與最短路線的差值的極限值d2，客車(chē)容量C，各個(gè)站點(diǎn)的坐標(biāo)位置和各站點(diǎn)人數(shù)。

3）由Floyd 算法根據(jù)個(gè)站點(diǎn)路線圖計(jì)算出最短路。

4）在最短路中取距終點(diǎn)最遠(yuǎn)的L 個(gè)站點(diǎn)，根據(jù)距終點(diǎn)的距離由大到小分別計(jì)為線路S1S2…SL的起始站點(diǎn)。

5）從S1開(kāi)始按最短路到終點(diǎn)確定第一條路線，依次確定L 條路線。

6）調(diào)整從S2到SL的L－1 條路線，調(diào)整的原則為：①將未在路線中的站點(diǎn)調(diào)整至路線中；②站點(diǎn)調(diào)整時(shí)只將此站點(diǎn)納入據(jù)此站點(diǎn)最近的路線中；③調(diào)整過(guò)程中路線以走最短路為優(yōu)先原則。若所有未在路線上的站點(diǎn)均調(diào)整在了路線中則轉(zhuǎn)（7）。

7）在所有站點(diǎn)均考慮的前提下，計(jì)算出每條路線的路程分別計(jì)為S1到SL的實(shí)際值，若max（Si－Sj）＞d2則轉(zhuǎn)至（6）重新調(diào)整路線直至max（Si－Sj）≤d2則轉(zhuǎn)至（8）。

8）計(jì)算每條路線上總乘客數(shù)，有多條路線經(jīng)過(guò)同一站點(diǎn)時(shí)只將此站點(diǎn)計(jì)算至其中一條路線。若Yi＞C 則將Si中Yi－C 個(gè)乘客交換到其他路線（以有重合站點(diǎn)的一對(duì)路線為優(yōu)先原則進(jìn)行交換）。直至對(duì)所有路線均有Yi≤C。

9）輸出：S1至SL中L 條路線的站點(diǎn)路線以及每條路線所包含的站點(diǎn)，每個(gè)站點(diǎn)的上車(chē)人數(shù)在不同路線的分配。

［1］Dantzig, Ramser. The truck dispatching Problem, MgtSci[M]. 1959, 6: 81-85.

［2］Balinski M, Quand R. On an integer program for a delivery problem [J].Operations Research, 1962,12: 300-304.

［3］Eilon S, Watson -Gandy C DT, Christofides N. distribution management:mathematical modeling and practical analysis [M].London: Griffin, 1971.

［4］Gendreau M, Hertz A, LaporteG A. tabu search heuristic for the vehicle routingproblem[M]. Montreal: Publication#777, Centre de recherchesur lestranspors,1991.

［5］M.L.Fisher.Vehicle Routing Handbooks in Operations Research & Management Science. Vol8, 1995[S].

［6］金燕波.校車(chē)路徑優(yōu)化問(wèn)題研究[D].吉林大學(xué),2006.

［7］郭耀煌.安排城市卡車(chē)行車(chē)路線的一種新算法[J].統(tǒng)工程學(xué)報(bào),1989,4(2)70-78.

［8］姜大立,等.車(chē)輛路徑問(wèn)題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐,1999(6):40-45.

［9］李嘉,等.一類(lèi)特殊車(chē)輛路徑問(wèn)題(VRP)[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2001,22(3):245-248.

［10］張富朱泰英.校車(chē)站點(diǎn)及線路的優(yōu)化設(shè)計(jì)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2012-02-23.

［11］Herbert Fleischner.歐拉圖與相關(guān)專(zhuān)題[M].科學(xué)出版社,2012-04.