班車站點及路線的優(yōu)化設(shè)計

馮存梅 李 威 沈 忱

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

0 研究背景

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

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

1 符號說明

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

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

Z 總站點數(shù)

N 總路徑數(shù)

C 每輛車的容量

Si第i 條路線

Pi第i 個站點

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

ωijk車輛k 從Pi站到Pj站的路程

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

2 班車站點設(shè)置的數(shù)學(xué)模型

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

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

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

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

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

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

模型一：

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

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

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

在上述要求中沒有提及成本問題，其實對于單一車輛單一路徑，車輛的成本是固定的。剩余的就只有運行的成本，運行的成本只與路程有關(guān)即只要求。

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

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

模型二：

此模型較模型一要復(fù)雜，是更具有廣泛性和實用性的一般性模型。模型二是針對多人員多站點多線路多種因素綜合考慮建立的。因為是一般性模型所以模型二較模型一相比具有多條線路，多車輛。在設(shè)置好站點后我們先用floyd 算法求出所有站點之間的最短路，由最短路依次從距原點最遠，第二遠…第N 遠為起點設(shè)置N 條線路，設(shè)置線路按兩條原則一是盡量走最短路二是所有線路盡量囊括所有站點對有些特殊情況則另作分析。具體方法見模型算法設(shè)計。

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

車輛達到最少是首先決定因素其次是使所有車輛行駛總路程最短，因為除車輛的固定成本外路程所決定的運行成本從長期來看也是重要的因素。即：

同樣在保證總路程最短的前一約束下還要使時間達到最小化。設(shè)定時間的約束原因如模型一中設(shè)定時間約束的一樣，同樣是因為道路飽和度的考慮，其約束如下：

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

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

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

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

4 道路飽和度的考慮

此處道路飽和度并沒有用符號在模型中表示出來是出于對模型求解可行性的考慮，因為就算沒有考慮道路飽和度此模型的求解也相當(dāng)困難。但是道路飽和度是實際問題中不得不考慮的一項因素，特別是在大城市的上下班高峰期，往往會因為交通堵塞浪費大量時間這是很不合理的。此處對道路飽和度的考慮，實際上也是對路線的修正因為在有些已達到飽和的道路再安排車輛通行就不滿足時間的約束，就需要對線路進行調(diào)整。因為道路什么時候達到飽和往往與時間有關(guān)，這就要根據(jù)對不同環(huán)境的實際經(jīng)驗來判定。當(dāng)?shù)缆愤_到飽和時即通行時間遠超正常通行的時間，就在此時刻對此線路采用繞道而行的調(diào)整方案。

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

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

5 站點設(shè)置的算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5）對所有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）對C 重復(fù)步驟⑷直到條件不滿足為止，最后求得的C 即為最佳H 圈。

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

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

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

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

3）由Floyd 算法根據(jù)個站點路線圖計算出最短路。

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

5）從S1開始按最短路到終點確定第一條路線，依次確定L 條路線。

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

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

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

9）輸出：S1至SL中L 條路線的站點路線以及每條路線所包含的站點，每個站點的上車人數(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］金燕波.校車路徑優(yōu)化問題研究[D].吉林大學(xué),2006.

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

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

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

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

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