大型運(yùn)動(dòng)會(huì)專用道設(shè)置問題的多目標(biāo)模型及其求解

李福清，伍乃騏

（廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006）

大型運(yùn)動(dòng)會(huì)專用道設(shè)置問題的多目標(biāo)模型及其求解

李福清，伍乃騏

（廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006）

建立了大型運(yùn)動(dòng)會(huì)專用道設(shè)置問題的多目標(biāo)模型。針對(duì)該多目標(biāo)問題，劃分目標(biāo)的優(yōu)先次序，將其降解為兩個(gè)單目標(biāo)模型。然后以一個(gè)簡(jiǎn)化的大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該模型更符合大型運(yùn)動(dòng)會(huì)的實(shí)際運(yùn)輸需求。

大型運(yùn)動(dòng)會(huì)；專用道設(shè)置問題；多目標(biāo)模型；仿真實(shí)驗(yàn)

1 引言

在諸如亞運(yùn)會(huì)、奧運(yùn)會(huì)等大型運(yùn)動(dòng)會(huì)舉辦期間，組委會(huì)需要安排車輛接送運(yùn)動(dòng)員們往返于運(yùn)動(dòng)員村和比賽場(chǎng)館之間。若前往比賽場(chǎng)館或返回運(yùn)動(dòng)員村的行車時(shí)間太長(zhǎng)，就不利于運(yùn)動(dòng)員們的賽前準(zhǔn)備和賽后恢復(fù)。因此承辦城市在申辦時(shí)就會(huì)承諾這個(gè)行車時(shí)間必在可接受范圍，如廣州在申辦2010亞運(yùn)會(huì)時(shí)承諾這個(gè)行車時(shí)間不超過30min。在運(yùn)動(dòng)員村附近新建所有比賽場(chǎng)館是不現(xiàn)實(shí)的，絕大多數(shù)情況是將現(xiàn)有體育場(chǎng)館作為比賽場(chǎng)館使用。而運(yùn)動(dòng)員村和一些場(chǎng)館離得較遠(yuǎn)，車輛若按正常行駛的話，很難保證在規(guī)定時(shí)間內(nèi)抵達(dá)。若在現(xiàn)有交通網(wǎng)絡(luò)上設(shè)置專用車道，僅供運(yùn)送運(yùn)動(dòng)員車輛行駛，由于該專用道上車輛少，也沒有社會(huì)車輛干擾，就可以極大提高行車速度、減少行車時(shí)間，使運(yùn)動(dòng)員村與各比賽場(chǎng)館之間的行車時(shí)間控制在規(guī)定時(shí)限內(nèi)。事實(shí)上，北京奧運(yùn)會(huì)、廣州亞運(yùn)會(huì)等大型運(yùn)動(dòng)會(huì)舉辦期間都采用了設(shè)置專用道的方法。但設(shè)置專用道這種交通管制措施，是以剝奪普通車輛對(duì)該車道的使用權(quán)為代價(jià)的，如果盲目設(shè)置必然招致受影響者的極大反對(duì)。因此在完成運(yùn)送任務(wù)的前提下如何使專用道的設(shè)置代價(jià)最小是值得研究的問題。

吳瀛峰等人基于2010廣州亞運(yùn)會(huì)的實(shí)際應(yīng)用背景，首次提出了基于大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)的專用道設(shè)置問題（Lane Reservation Problem in Transportation Network of Large Sports，LRPTNLS）的定義，并展開了相關(guān)的研究[1－4]。吳瀛峰等人所做的工作非常有意義，開拓了一個(gè)新的研究方向，并為后來(lái)者研究該問題奠定了基礎(chǔ)，但仍存在著一些不足。本文分析了大型運(yùn)動(dòng)會(huì)中運(yùn)送任務(wù)的特點(diǎn)和要求，在最小化專用道設(shè)置代價(jià)這個(gè)目標(biāo)的基礎(chǔ)上，提出增加最少化運(yùn)送車輛數(shù)目的目標(biāo)，據(jù)此建立相應(yīng)的數(shù)學(xué)規(guī)劃模型，并設(shè)計(jì)了兩階段算法進(jìn)行求解，然后以一個(gè)簡(jiǎn)化的大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)的專用道設(shè)置作為實(shí)例來(lái)驗(yàn)證了模型和算法的正確性和有效性。

2 問題描述

2.1 專用道設(shè)置問題中交通網(wǎng)絡(luò)的構(gòu)成

一般使用網(wǎng)絡(luò)圖表示交通網(wǎng)絡(luò)，其中節(jié)點(diǎn)分為源節(jié)點(diǎn)和終點(diǎn)節(jié)點(diǎn)，分別表示出發(fā)地和目的地，邊或弧就表示路段，邊或弧上的權(quán)表示該路段的參數(shù)，典型的如最短路徑問題、車輛路徑問題等。但在專用道設(shè)置問題中，網(wǎng)絡(luò)圖的含義有所不同。①在專用道設(shè)置問題中，每個(gè)路段需描述多個(gè)屬性，這些屬性至少包括：設(shè)置專用道后車輛通過該路段所需時(shí)間t1、未設(shè)置專用道車輛通過該路段所需時(shí)間t0及在該路段設(shè)置專用道的代價(jià)μ。因此網(wǎng)絡(luò)圖中邊或弧的權(quán)是由多個(gè)屬性構(gòu)成的一個(gè)數(shù)組。②節(jié)點(diǎn)類型不僅包括源節(jié)點(diǎn)和終點(diǎn)節(jié)點(diǎn)，還包括中間節(jié)點(diǎn)，其表示從出發(fā)地到目的地途徑的交叉路口。在路段上因某一運(yùn)輸任務(wù)的要求而設(shè)置專用道，則會(huì)產(chǎn)生專用道設(shè)置代價(jià)，而一旦設(shè)置后，其他運(yùn)輸任務(wù)的車輛通過該路段時(shí)均可使用該路段的專用道。專用道可重復(fù)使用但專用道設(shè)置代價(jià)僅需在第一次設(shè)置時(shí)計(jì)算1次。由于表示專用道設(shè)置代價(jià)的路段屬性不具有累加性，在描述從源點(diǎn)到終點(diǎn)的交通路徑時(shí)就不能省略途徑的中間節(jié)點(diǎn)。若所有中間節(jié)點(diǎn)都考慮的話，則實(shí)際交通網(wǎng)絡(luò)用網(wǎng)絡(luò)圖表示就會(huì)極其復(fù)雜。若某些連續(xù)路段僅被一個(gè)運(yùn)輸任務(wù)的車輛所使用，且假設(shè)這種連續(xù)路段僅考慮連在一起設(shè)或不設(shè)專用道，則可將這種連續(xù)路段視為一個(gè)路段，由此簡(jiǎn)化交通網(wǎng)絡(luò)的表示。

據(jù)此，可用如圖1所示的網(wǎng)絡(luò)圖表示大型運(yùn)動(dòng)會(huì)的交通網(wǎng)絡(luò)。其中（如V0）表示源點(diǎn)即運(yùn)動(dòng)員村，?（如g1，…，g11）表示終點(diǎn)即各比賽場(chǎng)館，○（如n1，…，n11）表示中間節(jié)點(diǎn)，并假設(shè)各路段來(lái)往雙向的道路屬性是相同的而使用雙向箭頭線來(lái)表示路段。

圖1 大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)的網(wǎng)絡(luò)圖表示

2.2 求解目標(biāo)

專用道規(guī)定只供執(zhí)行任務(wù)的車輛使用，那么社會(huì)其他車輛要通過該交通網(wǎng)絡(luò)時(shí)就會(huì)受到影響。若這種影響太大，他們可能就會(huì)反對(duì)設(shè)置專用道。因此，使整個(gè)交通網(wǎng)絡(luò)上設(shè)置專用道的代價(jià)最小化是求解的第一目標(biāo)。從運(yùn)動(dòng)員村到某一比賽場(chǎng)館構(gòu)成了一個(gè)運(yùn)輸任務(wù)，若有n個(gè)比賽場(chǎng)館，則構(gòu)成了n個(gè)運(yùn)輸任務(wù)。一輛車只執(zhí)行其中一個(gè)任務(wù)。實(shí)際上，組織方會(huì)考慮將相鄰場(chǎng)館的運(yùn)輸任務(wù)合并為一個(gè)任務(wù)。一方面當(dāng)參賽人數(shù)不是很多時(shí)可用一輛車運(yùn)送從而減少車輛的使用，另一方面，減少任務(wù)數(shù)量可以減少其他管理成本。針對(duì)任務(wù)合并的要求，有兩種解決方案。一種是在事前進(jìn)行評(píng)估，將可在同一線路上的所有目標(biāo)節(jié)點(diǎn)指定為任務(wù)的目標(biāo)節(jié)點(diǎn)集合，如廣州亞運(yùn)會(huì)時(shí)前往大學(xué)城體育中心的任務(wù)還包含了各大學(xué)體育場(chǎng)館這些節(jié)點(diǎn)集合，前往大夫山公園的任務(wù)還包含了英東體育館節(jié)點(diǎn)[5]。這種方案需要決策者能準(zhǔn)確了解線路管理和車輛使用等方面的成本。實(shí)際上這有一定的難度，所以可采取另一種更加可行的方案，即將最少化車輛使用數(shù)量作為第二求解目標(biāo)。事實(shí)上，LRPTNLS還有其他的求解目標(biāo)，但最小化專用道設(shè)置代價(jià)和最少化車輛使用數(shù)目是其中最主要的兩個(gè)目標(biāo)。

2.3 改進(jìn)后的LRPTNLS定義

根據(jù)上面的分析，將LPRTNLS定義為：在大型運(yùn)動(dòng)會(huì)交通網(wǎng) 絡(luò) G=(V ,A) 中 ，V={0 ,1,2,…,n} 是 節(jié) 點(diǎn) 的 集 合 ，A={( i，j)|i，j∈V}是路段的集合，特殊節(jié)點(diǎn)0是作為起點(diǎn)的運(yùn)動(dòng)員村，S={1 ,2,…,n} 是除運(yùn)動(dòng)員村之外的節(jié)點(diǎn)，G={gi|i=1,2,…,m,m≤n,gi∈S}（即G?S）是作為目標(biāo)節(jié)點(diǎn)的比賽場(chǎng)館集合，O=S-G是既不是起點(diǎn)又不是終點(diǎn)的節(jié)點(diǎn)（即中間節(jié)點(diǎn)）的集合，每個(gè)路段 (i,j)具有權(quán)參數(shù)數(shù)組ωij=，，μij),?(i ,j)∈A，其中t0ij是未設(shè)置專用道之前車輛通過路段(i,j)所需時(shí)間，是設(shè)置專用道后車輛從專用車道通過路段(i,j)所需時(shí)間，＜t0ij，μij是在路段(i ,j)上設(shè)置專用道的代價(jià)，K={1 ,2,…,k}，k≤m是執(zhí)行運(yùn)輸任務(wù)的車輛集合，每輛車的容量無(wú)限制，車輛從起點(diǎn)到各目標(biāo)節(jié)點(diǎn)的行駛時(shí)間不得超過規(guī)定時(shí)限ψ（為一常值）。問題的求解目標(biāo)是在整個(gè)交通網(wǎng)絡(luò)上使設(shè)置專用道的總代價(jià)最小，同時(shí)使用的車輛數(shù)最少。

3 建立問題的數(shù)學(xué)規(guī)劃模型

在建立模型時(shí)，還需使用到的變量的含義見表1。

表1 變量符號(hào)含義

LRPTNLS問題的多目標(biāo)線性整數(shù)規(guī)劃模型如下：

在上述模型中，目標(biāo)函數(shù)由兩部分構(gòu)成，第一目標(biāo)（1）是要求在交通網(wǎng)絡(luò)上設(shè)置專用道的代價(jià)最小化，第二目標(biāo)（2）是要求執(zhí)行運(yùn)輸任務(wù)的車輛數(shù)量最少；約束條件（3）規(guī)定每輛車必須從起點(diǎn)0出發(fā)；約束條件（4）規(guī)定每輛車進(jìn)入某個(gè)中間節(jié)點(diǎn)u后，必須從該節(jié)點(diǎn)u繼續(xù)前進(jìn)；約束條件（5）規(guī)定每輛車經(jīng)過某節(jié)點(diǎn)i最多只能一次，避免車輛行駛路徑包含回路；約束條件（6）規(guī)定每輛車至少為一個(gè)比賽場(chǎng)館提供服務(wù)；約束條件（3）-（6）規(guī)定了每輛車必定從起點(diǎn)出發(fā)，途經(jīng)中間節(jié)點(diǎn)最終抵達(dá)目標(biāo)節(jié)點(diǎn)，且路徑不包含環(huán)路；約束條件（7）規(guī)定每個(gè)場(chǎng)館至少由一輛車提供服務(wù)；約束條件（8）規(guī)定了每輛車途徑各個(gè)路段的通行時(shí)間總和不能超過規(guī)定的時(shí)限ψ；約束條件（9）規(guī)定至少有一輛車經(jīng)過路段（i，j）才能在該路段設(shè)置專用道；約束條件（10）規(guī)定在路段（i，j）上最多只設(shè)置1次專用道；約束條件（11）規(guī)定了每輛車只有經(jīng)過路段（i，j）時(shí)才能在該路段上設(shè)置專用道；約束條件（12）、（13）和（14）規(guī)定了變量取值范圍為0或1。

4 分階段求解與仿真實(shí)驗(yàn)

在大型運(yùn)動(dòng)會(huì)專用道設(shè)置問題上，最小化專用道設(shè)置代價(jià)這一目標(biāo)是最重要和關(guān)鍵的，在此基礎(chǔ)上，追求最少化運(yùn)送車輛數(shù)目。因此，求解時(shí)，可將此多目標(biāo)數(shù)學(xué)規(guī)劃問題分成兩階段的單目標(biāo)規(guī)劃問題進(jìn)行求解。

4.1 最小化專用道設(shè)置代價(jià)目標(biāo)的模型

此時(shí)，每個(gè)場(chǎng)館由一輛車來(lái)提供服務(wù)，因此公式（2）轉(zhuǎn)化為一個(gè)約束條件：

同時(shí)，公式（6）也相應(yīng)更改為：

由公式（1）構(gòu)成目標(biāo)函數(shù)，約束條件（3）-（5），（7）-（16）構(gòu)成該單目標(biāo)的數(shù)學(xué)規(guī)劃模型。

4.2 最少化運(yùn)送車輛數(shù)目目標(biāo)的模型

在前一步完成的基礎(chǔ)上，建立目標(biāo)是最少化運(yùn)送車輛數(shù)目模型，然后進(jìn)行求解。

完成最小化專用道設(shè)置代價(jià)目標(biāo)求解后，不能再增設(shè)或更改專用道設(shè)置，此時(shí)交通網(wǎng)絡(luò)各路段只用一個(gè)屬性即行車時(shí)間 tij來(lái)描述（未設(shè)置專用道路段取，設(shè)置了專用道的路段?。?，約束條件仍是從起點(diǎn)到比賽場(chǎng)館的總行車時(shí)間不得超過ψ，其公式為：

因此，由目標(biāo)函數(shù)公式（2）、約束條件公式（3）-（7）、（13）和（17）就構(gòu)成了第二階段的數(shù)學(xué)規(guī)劃模型。

4.3 仿真實(shí)驗(yàn)與分析

表2 大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)及路段參數(shù)

假設(shè)ψ＝20，通過數(shù)學(xué)規(guī)劃軟件Lingo進(jìn)行求解，結(jié)果表明只需在（v0,n1）、（v0,n3）、（n1,n4）、（n1,n5）、（n4,g6）、（n4, g3）、（n5,n9）、（g3,n11）、（n11,g8）、（g7,g9）、（g6,g11）這幾個(gè)路段上設(shè)置專用道即可，得到整個(gè)交通網(wǎng)絡(luò)專用道設(shè)置最小代價(jià)為4.77，11個(gè)場(chǎng)館只需派出8輛車即可滿足要求，車輛行駛路徑見表3。

表3 車輛行駛路徑與服務(wù)場(chǎng)館

從實(shí)驗(yàn)結(jié)果可以看出，該模型解決了舉辦大型運(yùn)動(dòng)會(huì)在設(shè)置專用道時(shí)既要使得整個(gè)交通網(wǎng)絡(luò)的專用道設(shè)置代價(jià)最小，又只安排最少數(shù)量的服務(wù)車輛的實(shí)際問題。

5 結(jié)語(yǔ)

大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)的專用道設(shè)置問題源于運(yùn)輸實(shí)際需求的一類重要的交通規(guī)劃問題，自吳瀛峰等人提出該問題后，后來(lái)研究者的注意力主要集中于研究和設(shè)計(jì)該問題的優(yōu)化算法，對(duì)產(chǎn)生問題的實(shí)際需求背景和問題本身少有人進(jìn)行探討。本文從舉辦大型運(yùn)動(dòng)會(huì)時(shí)的實(shí)際運(yùn)輸需求出發(fā)，提出了既需要使得整個(gè)交通網(wǎng)絡(luò)專用道設(shè)置代價(jià)最小，還應(yīng)該使用最少的運(yùn)輸車輛提供運(yùn)輸服務(wù)。據(jù)此，建立了大型運(yùn)動(dòng)會(huì)專用道設(shè)置問題的多目標(biāo)模型，并以一個(gè)簡(jiǎn)化的大型運(yùn)動(dòng)會(huì)交通網(wǎng)絡(luò)作為例子，通過數(shù)學(xué)規(guī)劃軟件進(jìn)行求解，驗(yàn)證了本文的模型能夠滿足實(shí)際的需求，是正確有效的。

[1]吳瀛峰,伍乃騏,朱戰(zhàn)國(guó).大型運(yùn)動(dòng)會(huì)專用道設(shè)置的交通規(guī)劃模型[J].工業(yè)工程,2009,12(6):96-100.

[2]吳瀛峰,伍乃騏,朱戰(zhàn)國(guó).求解基于專用道設(shè)置的動(dòng)態(tài)交通規(guī)劃問題的啟發(fā)式算法[J].運(yùn)籌與管理,2009,18(5):38-42.

[3]吳瀛峰.基于專用道設(shè)置的交通規(guī)劃問題的建模與求解[D].廣州:廣東工業(yè)大學(xué)，2010.

[4]Wu Y F,Chu C B,Chu F,et al.Heuristic for lane reservation problem in time constrained transportation[A].Proceedings of the Fifth Annual IEEE International Conference on Automation Science and Engineering[C].Bangalore,India,2009.

[5]李福清,伍乃騏.運(yùn)送任務(wù)合并下專用道設(shè)置問題的建模與求解[J].系統(tǒng)工程理論與實(shí)踐,2014,(6):1 599-1 606.

[6]李湘勇.車輛路徑問題模型及算法研究[D].上海:上海交通大學(xué),2007.

[7]Zhou Z,Chu F,Che A,et al.A multi-objective model for the hazardous material transportation problem based on lane reservation[A].In:Proceedings of IEEE International Conference on Networking,Sensing and Control[C].2012.

[8]Yunfei Fang,Feng Chu,Said Mammar,et al.Iterative Algorithm for Lane Reservation Problem on Transportation Network[A].In:2011 InternationalConference on Networking,Sensing and Control[C].Delft,the Nethelands,2011.

[9]B W Waxman.Routing of multipoint connections[J].IEEE Journal on Selected Areas in Communications,1998,6(9):1 617-1 622.

[10]Fang Y,Chu F,Mammar S,Zhou M.Optimal Lane Reservation in Transportation Network[J].IntelligentTransportation Systems,IEEE Transactions on Intelligent Transportation Systems,2012,13(2):482-491.

[11]郝光,張殿業(yè),馮勛省.多目標(biāo)最短路徑模型及算法[J].西南交通大學(xué)學(xué)報(bào),2007,(5).

[12]張孜,林曉麗.廣州亞運(yùn)會(huì)車輛調(diào)度信息系統(tǒng)設(shè)計(jì)與實(shí)踐[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,(5).

[13]王書靈,陳金川,郭繼孚,李春艷.交通需求管理政策在北京奧運(yùn)會(huì)中的應(yīng)用和評(píng)價(jià)[J].交通運(yùn)輸系統(tǒng)工程與信息,2008,(6).

[14]齊建宇.快速路公交專用道設(shè)置條件研究[J].交通建設(shè)與管理,2015, (10).

[15]王繼強(qiáng).基于LINGO的旅行商問題的建模方法[J].計(jì)算機(jī)工程與科學(xué),2014,(5).

[16]張曉倩.應(yīng)急救援中多目標(biāo)車輛路徑問題研究[J].交通科技與經(jīng)濟(jì), 2015,(1).

Establishment and Solution of Multi-objective Model for Dedicated Lane Setup during Large-scale Sports Meetings

Li Fuqing,Wu Naiqi
(School of Electrical&Mechanical Engineering,Guangdong Institute of Technology,Guangzhou 510006,China)

In this paper,in view of the multi-objective problem in the setup of the dedicated lanes during large-scale sports meetings, we first ranked the priority of the objectives to reduce the multi-objective model into two single-objective models,then through a simulation experiment on the simplified traffic network of a large-scale sports meeting,demonstrated that the model was capable of satisfying the practical transportation demand of the sports meeting.

large-scale sports meeting;dedicated lane setup problem;multi-objective model;simulation experiment

TU245；F224

A

1005-152X(2015)10-0146-03

2015-08-12

李福清（1976-），男，江西玉山人，講師，博士研究生，研究方向：智能交通與物流、組合優(yōu)化模型與算法；伍乃騏（1949-），男，教授，博士生導(dǎo)師，國(guó)務(wù)院特殊津貼專家，研究方向：制造系統(tǒng)及設(shè)計(jì)、智能交通系統(tǒng)、生產(chǎn)計(jì)劃與調(diào)度和控制、離散事件系統(tǒng)及Petri網(wǎng)理論、信息安全和計(jì)算機(jī)網(wǎng)絡(luò)入侵檢測(cè)。

10.3969/j.issn.1005-152X.2015.10.040