大型運動會專用道設置問題的多目標模型及其求解

李福清，伍乃騏

（廣東工業大學 機電工程學院，廣東 廣州 510006）

大型運動會專用道設置問題的多目標模型及其求解

李福清，伍乃騏

（廣東工業大學 機電工程學院，廣東 廣州 510006）

建立了大型運動會專用道設置問題的多目標模型。針對該多目標問題，劃分目標的優先次序，將其降解為兩個單目標模型。然后以一個簡化的大型運動會交通網絡進行仿真實驗，實驗結果表明，該模型更符合大型運動會的實際運輸需求。

大型運動會；專用道設置問題；多目標模型；仿真實驗

1 引言

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

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

2 問題描述

2.1 專用道設置問題中交通網絡的構成

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

據此，可用如圖1所示的網絡圖表示大型運動會的交通網絡。其中（如V0）表示源點即運動員村，?（如g1，…，g11）表示終點即各比賽場館，○（如n1，…，n11）表示中間節點，并假設各路段來往雙向的道路屬性是相同的而使用雙向箭頭線來表示路段。

圖1 大型運動會交通網絡的網絡圖表示

2.2 求解目標

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

2.3 改進后的LRPTNLS定義

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

3 建立問題的數學規劃模型

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

表1 變量符號含義

LRPTNLS問題的多目標線性整數規劃模型如下：

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

4 分階段求解與仿真實驗

在大型運動會專用道設置問題上，最小化專用道設置代價這一目標是最重要和關鍵的，在此基礎上，追求最少化運送車輛數目。因此，求解時，可將此多目標數學規劃問題分成兩階段的單目標規劃問題進行求解。

4.1 最小化專用道設置代價目標的模型

此時，每個場館由一輛車來提供服務，因此公式（2）轉化為一個約束條件：

同時，公式（6）也相應更改為：

由公式（1）構成目標函數，約束條件（3）-（5），（7）-（16）構成該單目標的數學規劃模型。

4.2 最少化運送車輛數目目標的模型

在前一步完成的基礎上，建立目標是最少化運送車輛數目模型，然后進行求解。

完成最小化專用道設置代價目標求解后，不能再增設或更改專用道設置，此時交通網絡各路段只用一個屬性即行車時間 tij來描述（未設置專用道路段取，設置了專用道的路段取），約束條件仍是從起點到比賽場館的總行車時間不得超過ψ，其公式為：

因此，由目標函數公式（2）、約束條件公式（3）-（7）、（13）和（17）就構成了第二階段的數學規劃模型。

4.3 仿真實驗與分析

表2 大型運動會交通網絡及路段參數

假設ψ＝20，通過數學規劃軟件Lingo進行求解，結果表明只需在（v0,n1）、（v0,n3）、（n1,n4）、（n1,n5）、（n4,g6）、（n4, g3）、（n5,n9）、（g3,n11）、（n11,g8）、（g7,g9）、（g6,g11）這幾個路段上設置專用道即可，得到整個交通網絡專用道設置最小代價為4.77，11個場館只需派出8輛車即可滿足要求，車輛行駛路徑見表3。

表3 車輛行駛路徑與服務場館

從實驗結果可以看出，該模型解決了舉辦大型運動會在設置專用道時既要使得整個交通網絡的專用道設置代價最小，又只安排最少數量的服務車輛的實際問題。

5 結語

大型運動會交通網絡的專用道設置問題源于運輸實際需求的一類重要的交通規劃問題，自吳瀛峰等人提出該問題后，后來研究者的注意力主要集中于研究和設計該問題的優化算法，對產生問題的實際需求背景和問題本身少有人進行探討。本文從舉辦大型運動會時的實際運輸需求出發，提出了既需要使得整個交通網絡專用道設置代價最小，還應該使用最少的運輸車輛提供運輸服務。據此，建立了大型運動會專用道設置問題的多目標模型，并以一個簡化的大型運動會交通網絡作為例子，通過數學規劃軟件進行求解，驗證了本文的模型能夠滿足實際的需求，是正確有效的。

[1]吳瀛峰,伍乃騏,朱戰國.大型運動會專用道設置的交通規劃模型[J].工業工程,2009,12(6):96-100.

[2]吳瀛峰,伍乃騏,朱戰國.求解基于專用道設置的動態交通規劃問題的啟發式算法[J].運籌與管理,2009,18(5):38-42.

[3]吳瀛峰.基于專用道設置的交通規劃問題的建模與求解[D].廣州:廣東工業大學，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]李福清,伍乃騏.運送任務合并下專用道設置問題的建模與求解[J].系統工程理論與實踐,2014,(6):1 599-1 606.

[6]李湘勇.車輛路徑問題模型及算法研究[D].上海:上海交通大學,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]郝光,張殿業,馮勛省.多目標最短路徑模型及算法[J].西南交通大學學報,2007,(5).

[12]張孜,林曉麗.廣州亞運會車輛調度信息系統設計與實踐[J].交通運輸系統工程與信息,2011,(5).

[13]王書靈,陳金川,郭繼孚,李春艷.交通需求管理政策在北京奧運會中的應用和評價[J].交通運輸系統工程與信息,2008,(6).

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

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

[16]張曉倩.應急救援中多目標車輛路徑問題研究[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-），男，江西玉山人，講師，博士研究生，研究方向：智能交通與物流、組合優化模型與算法；伍乃騏（1949-），男，教授，博士生導師，國務院特殊津貼專家，研究方向：制造系統及設計、智能交通系統、生產計劃與調度和控制、離散事件系統及Petri網理論、信息安全和計算機網絡入侵檢測。

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