多源車輛最優(yōu)路徑問題研究

摘要：隨著我國城市化發(fā)展步伐的急速加快，城市交通問題已成為發(fā)展中最關(guān)鍵的一個瓶頸問題。拼車問題應(yīng)運而生，在這種現(xiàn)象中，由于司機和乘客自已的出發(fā)點和目的地不同，怎樣選擇最優(yōu)路徑接送乘客成為需要慎重，認(rèn)真考慮的核心問題。本文正是基于這個問題給出最優(yōu)路徑的構(gòu)建模型及實現(xiàn)方法。并依據(jù)實驗結(jié)果證明了方案的正確性及高效性。

關(guān)鍵詞：多源車輛路徑問題；拼車；最短路徑

中圖分類號：TP14 文獻標(biāo)識碼：A 文章編號：1007-9599 （2012） 23-0000-02

1 源車輛路徑問題描述

拼車是一種新興的現(xiàn)象，不相識的乘客因為路線相同乘坐同一輛出租車出行，車費由乘客按自己的路程各自分?jǐn)偡Q為拼車。在我國，因為受到車輛限制和交通壓力，這種情況也受到政府支持。圖1是假設(shè)拼車中乘客和駕駛員的起點終點位置分布：乘客的起點和終點是隨機分布于路線中的，很可能存在A乘客的終點在B乘客的起點之前，C乘客的起點在D乘客的終點之后的情況。

2 研究問題的邊界界定

在這里我們忽略司機的載客數(shù)量和乘車的時間約束，只關(guān)注在問題的約束條件內(nèi)，多源車輛最優(yōu)路徑問題的求解過程?？梢酝ㄟ^手工輸入精確的坐標(biāo)來獲取司機和乘客起點終點位置，算法以對外的接口接收這些數(shù)據(jù)，并將最終的最優(yōu)路徑以點序列的形式對外輸出。

為了簡化、量化問題，對于最優(yōu)路徑的求解過程，這里不再考慮兩點之間具體的行車路線，而是運用兩點之間的直線距離來取代其真實距離，因為在交通路線中，通常兩點間的直線距離越遠，則其真實距離也越遠。所以用這種近似值求得的結(jié)果準(zhǔn)確不會受到影響，也能使算法更加優(yōu)化。

3 數(shù)學(xué)模型構(gòu)建

根據(jù)以上對問題的描述，建立如下的數(shù)學(xué)模型：

n：乘客的編號，有n個乘客其編號為0到n-1；N：所有點的編號，有n個乘客的話則有2n+2個點，其中包含2個司機起點終點，2n個乘客點。并且點位置情況為：第一個點位司機起點，前n個點為n個乘客的起點，后n個點為n個乘客對應(yīng)的終點，最后一個點位司機的終點。以司機的行駛路線最短為約束得出如下數(shù)學(xué)模型：

式1表示該模型以司機的行駛距離最短為最優(yōu)解。式2表示所有點除了司機的起點（即j=0這個點）都有一個點指向它，即汽車從前面的一個點行駛到它為它服務(wù)。式3表示司機的起點（即j=0這個點）沒有任何一個點指向它，即汽車沒有從其它點行駛到它，實際上該點是出發(fā)點。式4表示所有點除了司機的終點（即i=N-1這個點）都有下一個指向點，即汽車從該點行駛到其它點。式5表示司機的終點（即i=N-1這個點）沒有下一個指向點，即汽車不會從該點行駛到其他點，實際上該點是終點。

4 最優(yōu)路徑算法設(shè)計

假設(shè)（s，f）是路徑問題的一個實例，求某一可行解i屬于s，使得f（i）=minf（i），i屬于s。則本算法的計算步驟如下：

4.1 任選一個可行解作為S的初始解；選定初始溫度T0>0，降溫系數(shù)p（0

4.2 在溫度Tk下進行如下迭代：

令L=1，從解i的鄰域中隨機產(chǎn)生一個新的解j，如果f（j）<=f（i），則直接接受新解j作為當(dāng)前解；否則根據(jù)概率來確定是否接受新解，該概率為：如果exp（f（j）-f（i））/Tk）>nn為[0，1]上的隨機數(shù)，且最好為均勻分布），則接受新解j作為當(dāng)前解。如果L<=Lmax，則令L=L+1，并跳轉(zhuǎn)到第2.2步；否則到3。

4.3 如果Tk滿足終止條件，則輸出當(dāng)前解，算法結(jié)束跳轉(zhuǎn)到4；否則進行降溫：令Tk+1=p*Tk，k=k+1.跳轉(zhuǎn)到2

由于模擬退火算法思想的過程基本上是通過控制兩個內(nèi)外循環(huán)進行的，一旦算法初始化，則內(nèi)外循環(huán)的次數(shù)實際上是確定的。那么對于算法速度的改進上則主要集中在各層循環(huán)的耗時上。對于外層逐漸降溫這一循環(huán)，只有一些基本的賦值語句以及一個判斷是否結(jié)束外循環(huán)的語句，這些沒有什么可改進或值得在意的地方。而值得注意的則是算法的內(nèi)循環(huán)上，即在當(dāng)前溫度下的多次新解產(chǎn)生與迭代過程，如果內(nèi)循環(huán)內(nèi)的操作足夠快的話，則整個算法的效率將會是很高的。對于內(nèi)循環(huán)，其本質(zhì)上是新解的產(chǎn)生與新解的接受或拒絕兩部分構(gòu)成。如何快速生成可行的新解以及快速的對新解進行接受或拒絕將決定了算法的整體效率。下面將介紹對于這兩個問題的優(yōu)化策略。

新解的產(chǎn)生在前面我們介紹過是通過簡單置換兩個隨機的點進行的，雖然是簡單置換兩個隨機的點，但是實際上，這兩個隨機點也是需要謹(jǐn)慎生成的。你可以設(shè)想一旦這兩個點為某一乘客的起點和終點，然后將它們進行交換，則新解顯然不是可行解；或者當(dāng)兩點交換后使得某一乘客的起點位于終點之后，這都是不合理的。所以，在算法中兩個隨機點的生成問題上，我們必須謹(jǐn)慎的控制以及判斷。

5 實驗結(jié)果分析

下表是對于用戶點分布進行解析后的具體坐標(biāo)。

對于四名乘客及司機點簡單分布的實驗，作者故意選擇了乘客點分布正好位于某一條線上。在實驗結(jié)果得出之前，即可通過圖上的標(biāo)記看到最優(yōu)路徑的結(jié)果。經(jīng)過算法的計算，也確實得到了這條最優(yōu)路徑。此組實驗證明了作者的算法在點的排序上的正確性，它沒有把乘客的終點放到乘客的起點前面，它正確的對乘客點進行了路徑上的排序。

本文所提出的多源車輛路徑問題屬于車輛路徑問題這一大的范疇之內(nèi)的一個分支，雖然是極小的一個分支領(lǐng)域，但是多源車輛路徑問題的提出卻是對以往車輛路徑問題的擴充。同時，多源車輛路徑問題的提出以及解決對于現(xiàn)實中常見的拼車路徑最優(yōu)問題，同城快遞的收發(fā)快件策略等類似問題有極其重要的指導(dǎo)意義。

參考文獻：

[1]張瑾.出租車“拼車”問題研究及其服務(wù)系統(tǒng)設(shè)計實現(xiàn)[M].蘭州：蘭州交通大學(xué)，2009.

[2]劉云忠，宣惠玉.車輛路徑問題的模型及算法研究綜述.管理工程學(xué)報，2005，1：124-130.

[3]李相勇.車輛路徑問題模型及算法研究[M]上海：上海交通大學(xué)，2007.