外文翻譯--網(wǎng)路控制信號(hào)的優(yōu)化設(shè)計(jì)

1、<p>　　網(wǎng)路控制信號(hào)的優(yōu)化設(shè)計(jì)</p><p><b>　　摘要：</b></p><p>　　考慮到整個(gè)使用信號(hào)的遲滯,網(wǎng)路信號(hào)的優(yōu)選設(shè)計(jì)使平衡流的最小化。這個(gè)問題可以由用戶平衡交通任務(wù)作為限制,對優(yōu)化設(shè)計(jì)進(jìn)行公式化。在本文中, 一個(gè)突出的共軛梯度方法被提出,解決全球集中的網(wǎng)路優(yōu)化設(shè)計(jì)問題。數(shù)例用于研究簡單柵格網(wǎng)路。據(jù)顯示, 在解決網(wǎng)路優(yōu)化設(shè)計(jì)的平衡流

2、,教傳統(tǒng)的方法,被提出的方法更能出色的完成。</p><p>　　關(guān)鍵詞: 共軛梯度;網(wǎng)路信號(hào); 平衡約束; 優(yōu)化</p><p><b>　　1. 介紹</b></p><p>　　當(dāng)考慮到使用者的路線選擇，網(wǎng)路信號(hào)的優(yōu)化設(shè)計(jì)是需要考慮的。這個(gè)問題可以由用戶平衡交通任務(wù)作為限制,對優(yōu)化設(shè)計(jì)進(jìn)行公式化。在過去的幾十年中, 許多研究者通過優(yōu)化技術(shù)

3、研究了這個(gè)問題[ 1,6,9,2 ] 。在本文里, 一個(gè)雙層規(guī)劃設(shè)計(jì)可以用網(wǎng)路控制信號(hào)來闡述。在上層規(guī)劃中, 性能指標(biāo)可定義為遲滯率的有利的線性綜合，以及在整個(gè)交通流中每段時(shí)間停止的數(shù)量,可以用TRANSYT[ 7 ] 交通模擬來評(píng)估。工作性能相應(yīng)的數(shù)學(xué)近似值和在下游匯合處的媒介物的平均延遲，在TRANSYT 模型中已經(jīng)獲得。在底層規(guī)劃中，用戶的平衡交通任務(wù)服從Wardrop第一原則，可以作為最小化問題來闡明。由于用戶的均衡分配約束是非

4、線性的, 導(dǎo)致網(wǎng)路信號(hào)化的設(shè)計(jì)問題是不突出的, 因此創(chuàng)建了唯一最佳方案。</p><p>　　在本文里, 一個(gè)計(jì)劃的共軛梯度(PCG)提議確定優(yōu)選的信號(hào)設(shè)置和全球集中的網(wǎng)絡(luò)流程。柵格網(wǎng)絡(luò)的數(shù)值計(jì)算在明顯的交接處提出的PCG 方法勝過傳統(tǒng)方法在各種各樣的初始需求量。本文的其他章節(jié)安排如下。在下一章,表明網(wǎng)路的信號(hào)化考慮到使用者的路線選擇。在第三章中，提出的共軛梯度方法在全球集中開發(fā)。在第四章, 一個(gè)柵格網(wǎng)絡(luò)以信號(hào)控

5、制的連接點(diǎn)在各種初始環(huán)節(jié)之下被考慮提出的PCG的數(shù)值計(jì)算和傳統(tǒng)方法被提出。第五章是本文的結(jié)論與討論。</p><p><b>　　2. 問題公式化</b></p><p><b>　　2.1. 符號(hào)</b></p><p>　　這篇論文的符號(hào)概述如下：</p><p>　　G(N, l) 表示一個(gè)指

6、定的網(wǎng)路, N 是信號(hào)控制連接并且L 是套鏈接</p><p>　　表示套信號(hào)設(shè)置可變物, 各自地為相互綠色周期、開始和期間, 那里和代表開始傳染媒介綠色的期間為信號(hào)小組j 在連接點(diǎn)m 如同共同的周期的比例</p><p>　　代表有效的綠色的期間為鏈接a</p><p>　　代表極小值綠色為信號(hào)小組j 在連接點(diǎn)m</p><p>　　代表清

7、除時(shí)間在綠色的結(jié)尾為小組j 和綠色之間開始為不相容的小組l 在連接點(diǎn)m</p><p>　　代表飽和流速在鏈接a</p><p>　　代表第號(hào)0 和1 的一件收藏品為各對不相容的信號(hào)小組在連接點(diǎn)m;</p><p>　　如果綠色開始為信號(hào)小組j 進(jìn)行那l 和否則</p><p>　　代表延遲的率在鏈接a</p><p>

8、;　　代表中止的數(shù)量每單位時(shí)間在鏈接a</p><p><b>　　表示套OD 對</b></p><p>　　表示對OD 對的旅行需求</p><p>　　表示套道路在OD 對w 之間</p><p>　　表示道路流程傳染媒介</p><p>　　表示鏈接流程傳染媒介</p>&l

9、t;p>　　表示鏈接道路發(fā)生矩陣, 如果道路p 在OD 對w 之間使用鏈接a 和</p><p>　　c 表示鏈接旅行時(shí)間</p><p>　　2.2. 信號(hào)化的公路網(wǎng)問題</p><p>　　信號(hào)化的公路網(wǎng)設(shè)計(jì)問題可能被公式化至于</p><p><b>　　依于</b></p><p>

10、　　和是各自鏈接具體衡量的因素為延遲的率和數(shù)字中止每單位時(shí)間被使用在TRANSYT 。第一限制在在共同的周期并且constraints(3)-(5) 在在綠色階段、鏈接容量和清除時(shí)間在各個(gè)連接點(diǎn)。并且平衡流程由解決發(fā)現(xiàn)以下交通分配問題。</p><p><b>　　分鐘 </b></p><p><b>　　依于</b></p>&

11、lt;p>　　3. 一個(gè)解答方法為信號(hào)化的公路網(wǎng)設(shè)計(jì)問題</p><p>　　在這個(gè)部分, 一次有效的查尋解決問題(1)-(9) 被開發(fā), 為哪些下降的查尋方向引起并且新重復(fù)被創(chuàng)造。查尋過程將被終止在KKT 點(diǎn)或a 新查尋方向可能引起。在以下, 一個(gè)計(jì)劃的共軛梯度方法提議獲得下降查尋方向。</p><p>　　3.1. 一計(jì)劃的共軛梯度methodIn 以下, 一個(gè)計(jì)劃的共軛梯度方法

12、提議獲得下降查尋方向。</p><p>　　題詞1 (Fletcher & 穿過了共軛梯度方法) ?？紤]一個(gè)連續(xù)能區(qū)分的作用</p><p><b>　　引起序列重復(fù)根據(jù)</b></p><p><b>　　每當(dāng)</b></p><p>　　然后為點(diǎn){xk} 序列由共軛梯度方法引起</

13、p><p>　　方向引起由(11) 為一個(gè)跌宕的非線性問題是嚴(yán)密地的下降方向減少目標(biāo)函數(shù)價(jià)值在對應(yīng)的梯度價(jià)值不是零條件下。</p><p>　　那里優(yōu)先處理的衍生物談到信號(hào)設(shè)置和流程從Chiou [ 3 ] 被獲得并且第二個(gè)項(xiàng)目是從靈敏度分析為網(wǎng)絡(luò)流程在Patriksson [ 5 ] 。讓A 表示系數(shù)恒定的傳染媒介壓抑的矩陣和B (2)-(5) 問題(1)-(9) 可能被重寫</p&g

14、t;<p>　　在追隨者, 我們應(yīng)用Fletcher & 依照被給作為穿過了共軛梯度方法對一個(gè)線性限制被設(shè)置在(14) 和(15) 由介紹一個(gè)矩陣在射出目標(biāo)函數(shù)的梯度活躍限制空空間(2)-(5) 以平等為了有效地尋找implementable 點(diǎn)。</p><p>　　定理1 (計(jì)劃的共軛梯度(PCG) 方法) ?？紤]問題在(14) 和(15) 序列可行重復(fù){星期} 能引起根據(jù)</p&

15、gt;<p>　　那里 是共軛梯度方向由(11) 確定和 是步長度使減到最小 是在可行的區(qū)域之內(nèi)的定義了(2)-(5) 。假設(shè), 有充分的等級(jí)在星期, 是活躍限制梯度以平等(2)-(5) 并且投射矩陣 是以下形式:</p><p>　　一個(gè)修改過的查尋方向sk+1 可能被確定以以下形式:</p><p>　　然后可行的點(diǎn) 序列由計(jì)劃的共軛梯度方法單調(diào)地引起減少表現(xiàn)價(jià)值,&l

16、t;/p><p>　　每當(dāng) 和是從(13) 。</p><p>　　證明。在題詞以后1 的結(jié)果, 我們有</p><p>　　倍增Eq 。(20) 由投射矩陣 它成為</p><p>　　因而為充足地小 我們有</p><p>　　由于由定義使 減到最小沿 從的 是步長度, 它暗示</p><p>

17、<b>　　哪些完成這證明。</b></p><p>　　定理2 () 。在定理1, 當(dāng), 如果所有拉格朗日乘算器對應(yīng)于活躍限制梯度以平等(2)-(5) 是正面或零,它暗示當(dāng)前的是KKT 點(diǎn)。否則選擇一個(gè)消極拉格朗日乘算器, 說, 和修建新活躍限制梯度由刪除列, 對應(yīng)于消極組分, 并且做投射矩陣以下形式:</p><p>　　查尋方向由(18) 和定理1 舉行的結(jié)果

18、然后確定。</p><p>　　證明。讓是拉格朗日乘算器的一個(gè)消極組分并且 被定義(17), 我們顯示。由矛盾, 假設(shè)</p><p><b>　　并且讓 </b></p><p>　　然后(25) 可能被重寫 </p><p>　　為任何, 那里存在對應(yīng)的列, , 活躍限制(2)-(5) 并且這樣</p>

19、<p>　　我們減去(27) 從(26) 并且它隨后而來:</p><p>　　自從抗辯假定的有充分的等級(jí)。因而。</p><p>　　推論1 (停止?fàn)顟B(tài)) 。 </p><p>　　如果是KKT 點(diǎn)為問題在(14) 并且(15) 查尋過程然后可以中止; 否則一個(gè)新下降方向在能引起根據(jù)定理1 和2 。</p><p>　　3.2.

20、 PCG 解答計(jì)劃</p><p>　　認(rèn)為信號(hào)化的公路網(wǎng)優(yōu)選設(shè)計(jì)問題(1)-(9), PCG 解答計(jì)劃被給如下:</p><p>　　步驟1: 開始時(shí),設(shè)置索引k =0 。</p><p>　　步驟2: 解決有信號(hào)設(shè)置的交通分配問題,發(fā)現(xiàn)優(yōu)先處理的衍生物(13) 。</p><p>　　步驟3: 使用計(jì)劃的共軛梯度方法確定查尋方向(18)

21、。進(jìn)入步驟4 。</p><p>　　步驟4: 如果發(fā)現(xiàn)一新在(16) 和讓進(jìn)入步驟2 。如果和所有拉格朗日乘算器對應(yīng)于活躍限制梯度non-negative, 是KKT 點(diǎn)和中止。否則, 發(fā)現(xiàn)最消極的拉格朗日乘算器和取消對應(yīng)限制和發(fā)現(xiàn)一個(gè)新投射矩陣和進(jìn)入步驟3。</p><p>　　4. 數(shù)字例子和計(jì)算比較</p><p>　　在這個(gè)部分, 數(shù)字試驗(yàn)做兩重。首先,

22、數(shù)字計(jì)算被執(zhí)行為顯示提出的PCG 的有效率和強(qiáng)壯與那些傳統(tǒng)方法, 即LCA [ 4 ] 并且SAB [ 8 比較] 在一個(gè)信號(hào)控制的柵格網(wǎng)絡(luò)以分明套最初。第二,數(shù)字比較用各種各樣的壅塞連續(xù)做由單調(diào)地增加旅行需求標(biāo)量。</p><p>　　4.1. 柵格網(wǎng)絡(luò)以信號(hào)控制的連接點(diǎn)</p><p>　　一個(gè)5x5 柵格大小網(wǎng)絡(luò)被顯示在無花果。1 被考慮為說明提出的PCG 方法的有效率在4 對OD

23、旅行和9 個(gè)信號(hào)化的連接點(diǎn)是信號(hào)化的網(wǎng)絡(luò)的優(yōu)選設(shè)計(jì)考慮到。旅行率被設(shè)置在100 veh/h 并且鏈接容量被設(shè)置1800 veh/h 。數(shù)字結(jié)果以二套分明最初被總結(jié)在表1 。如同它被看見在表1, 提出的PCG 方法達(dá)到在是短的為系統(tǒng)優(yōu)化的全球性最宜40 veh 附近在2.6% 如此之內(nèi)。提議 PCG 方法極大勝過傳統(tǒng)方法LCA 按表現(xiàn)給定值(PI) 近似地根據(jù)39% 和31% 和根據(jù)11% 和9% SAB 方法。關(guān)于計(jì)算時(shí)代由提出的PCG

24、 方法需要作為它明顯地看從表1, 它要求較不計(jì)算努力或在CPU 時(shí)間或在解決對應(yīng)的交通任務(wù)如同它做為LCA 或SAB 。</p><p>　　4.2. 柵格信號(hào)化了網(wǎng)絡(luò)隨著壅塞的增加</p><p>　　第二次調(diào)查將測試提出的PCG 方法的強(qiáng)壯在越來越被充塞的柵格信號(hào)化的網(wǎng)絡(luò)當(dāng)與常規(guī)方法比較。增長的交通壅塞導(dǎo)致連續(xù)增長的標(biāo)量對基本的旅行要求。計(jì)算結(jié)果為提出的PCG 方法被總結(jié)在表2, 結(jié)果

25、用相對區(qū)別百分比被表達(dá)對因此在二集合ofdistinct 最初的地方。</p><p>　　如同它被顯示在表2, 提出的PCG 方法達(dá)到了系統(tǒng)最宜在3% 之內(nèi)一致地產(chǎn)生最少相對區(qū)別百分比在20 套旅行要求。另一方面, 常規(guī)方法, 象LCA 和SAB, 達(dá)到了系統(tǒng)最宜以上限值的相對區(qū)別百分比比那些做了提出的PCG 方法。此外, 采取LCA 方法例如, 相對區(qū)別百分比的價(jià)值是更大雖然交通壅塞變得嚴(yán)厲和價(jià)值平均是一樣高

26、的象72 和63 為二套最初?？紤]表現(xiàn) SAB, 它達(dá)到了系統(tǒng)最宜與19%, 比那些做了LCA 似乎相對地好但仍然較不健壯比那些做了提出的PCG 方法。</p><p>　　實(shí)施為執(zhí)行計(jì)算努力在LCA 、SAB 和PCG 方法有被舉辦在SUN SPARC 超II 工作站根據(jù)操作系統(tǒng)Unix SunOS 5.5.1 使用 C++ 編譯器。停著的標(biāo)準(zhǔn)為這些解答被設(shè)置當(dāng)在表現(xiàn)上的相對區(qū)別給定值在連貫疊代少于0.05%

27、之間。</p><p><b>　　5. 結(jié)論和討論</b></p><p>　　在本文里, 我們提出了一個(gè)最近計(jì)劃的共軛投射方法(PCG) 以全球性匯合有效地解決信號(hào)化的公路網(wǎng)問題。一個(gè)5 個(gè)* 5 個(gè)柵格公路網(wǎng)與信號(hào)控制連接點(diǎn)被使用給常規(guī)數(shù)字上展示提出的方法的強(qiáng)壯和優(yōu)勢方法在解決信號(hào)化的公路網(wǎng)優(yōu)選設(shè)計(jì)。如同它報(bào)告了從數(shù)字比較在交通壅塞之下在各種各樣的套最初, 提出

28、的PCG 方法一致地勝過了其它常規(guī)方法以明顯的意義和較不計(jì)算努力被采取了。</p><p>　　它被想象測試提出的PCG 方法在大范圍一般路信號(hào)化的網(wǎng)絡(luò)。更加進(jìn)一步調(diào)查將被做為有鏈接容量擴(kuò)展的信號(hào)化的公路網(wǎng)設(shè)計(jì)問題并且有彈性旅行要求。</p><p><b>　　鳴謝</b></p><p>　　作者對支持是感恩的從臺(tái)灣全國科學(xué)委員會(huì)通過津貼N

29、SC 95-2416-H-259- 014.</p><p><b>　　參考文獻(xiàn):</b></p><p>　　[ 1 ] M. Abdulaal, L.J. LeBlanc, 連續(xù)平衡網(wǎng)絡(luò)設(shè)計(jì)模型,運(yùn)輸研究B 13 (1979) 19-32 。</p><p>　　[ 2 ] H. Ceylan, M.G.H. Bell, 根據(jù)交通信號(hào)時(shí)間

30、優(yōu)化基因算法方法, 包括司機(jī)的發(fā)送, 運(yùn)輸研究B 38 (2004) 329-342 。</p><p>　　[ 3 ] S-W 。Chiou, TRANSYT 衍生物為區(qū)域交通控制優(yōu)化以網(wǎng)絡(luò)平衡流程, 運(yùn)輸研究B 37 (2003) 263-290 。</p><p>　　[ 4 ] B.G 。Heydecker, T.K. Khoo, 平衡網(wǎng)絡(luò)設(shè)計(jì)問題, 在: AIRO'90

31、關(guān)于模型的會(huì)議記錄和方法為決策支持, Sorrento 1990 年, 頁587-602 。</p><p>　　[ 5 ] M. Patriksson, 靈敏度分析交通平衡, 運(yùn)輸科學(xué)38 (2004) 258-281 。</p><p>　　[ 6 ] S. Suh, T.J. 金, 解決平衡網(wǎng)絡(luò)設(shè)計(jì)問題的非線性bilevel 編程的模型: 比較回顧, 史冊運(yùn)籌學(xué)34 (1992) 2

32、03-218 。</p><p>　　[ 7 ] R.A. Vincent, A.I. Mitchell, D.I. Robertson, 對TRANSYT 的用戶指南, 版本8 。TRRL 報(bào)告、LR888 、運(yùn)輸和路研究實(shí)驗(yàn)室, Crowthorne 1980 年。</p><p>　　[ 8 ] H. 楊, S. Yagar, 交通任務(wù)和信號(hào)控制在飽和的公路網(wǎng), 運(yùn)輸研究A 29 (

33、1995) 125-139 。</p><p>　　[ 9 ] H. 楊, M.G.H. Bell, 模型和算法為公路網(wǎng)設(shè)計(jì): 回顧和一些新發(fā)展, 運(yùn)輸回顧18 (1998) 257-278 。</p><p>　　Optimal design of signal-controlled road network</p><p><b>　　Abstract

34、：</b></p><p>　　An optimal design of signalized road network is considered where total travelers’ delay is minimized subject to user equilibrium flow. This problem can be formulated as an optimization

35、problem by taking the user equilibrium traffic assignment as a constraint. In this paper, a projected conjugate gradient method is presented to solve the signalized road network problem with global convergence. Numerical

36、 examples are investigated on simple grid road network. As it shows, the proposed method achie</p><p>　　Keywords: Conjugate gradient; Signalized road network; Equilibrium constraints; Optimization</p>

37、<p>　　1. Introduction</p><p>　　An optimal design of signalized road network is considered while the route choice of users is taken into account. This problem can be formulated as an optimization proble

38、m by taking the user equilibrium traffic assignment as a constraint. In the past decades, many researchers via the techniques of optimization have investigated this problem [1,6,9,2]. In this paper, a bilevel programming

39、 program is considered to formulate an optimal design of signal-controlled road network. In the upper level pr</p><p>　　In this paper, a projected conjugate gradient (PCG) approach is proposed to determine t

40、he optimal signal settings and network flows with global convergence. Numerical computations are conducted on a grid network with signalized junctions where the proposed PCG method outperforms traditional methods on vari

41、oussets of initials and sets of demand scalars. The rest of the paper is organized as follows. In the next section, a signalized road network is formulated where users’ route choice is taken in</p><p>　　2. P

42、roblem formulation</p><p>　　2.1. Notation</p><p>　　Notation used throughout this paper is summarized below.</p><p>　　G(N, l) denotes a directed road network, where N is the set of s

43、ignal controlled junctions and L is the set of links</p><p>　　denotes the set of signal setting variables, respectively for the reciprocal of cycle time, start and duration of greens, whereandrepresents the

44、vector of startsand durations of greenfor signal group j at junction m as proportions of common cycle time</p><p>　　represents the duration of effective green for link a</p><p>　　represents the

45、minimum green for signal group j at junction m</p><p>　　represents the clearance time between the end of green for group j and the start of green for incompatible group l at junction m</p><p>　　

46、represents saturation flow rate on link a</p><p>　　represents a collection of numbers 0 and 1 for each pair of incompatible signal groups at junction m; whereif the start of green for signal group j proceeds

47、 that of l andotherwise</p><p>　　represents the rate of delay on link a</p><p>　　represents the number of stops per unit time on link a</p><p>　　denotes the set of OD pairs</p>

48、;<p>　　denotes the travel demands for OD pairs</p><p>　　denotes the set of paths between OD pair w</p><p>　　denotes vector of path flow</p><p>　　denotes vector of link flow&l

49、t;/p><p>　　denotes the link-path incidence matrix, whereif path p between OD pair w uses link a andotherwise</p><p>　　C denotes the link travel times</p><p>　　2.2. Signalized road n

50、etwork problem</p><p>　　The signalized road network design problem can be formulated as to</p><p>　　subject to</p><p>　　whereandare respectively link-specific weighting factors for

51、the rate of delay and the number of stops per unit time used in TRANSYT. The first constraint is for the common cycle time and the constraints (3)–(5) are for the green phase, link capacity and clearance time at each jun

52、ction. Also the equilibrium flowsare found by solving the following traffic assignment problem.</p><p>　　3. A solution method for signalized road network design problem</p><p>　　In this section,

53、 an effective search for solving problems (1)–(9) is developed, for which a search direction of descent is generated and a new iterate is created. The search process will be terminated at a KKT point or a new search dire

54、ction can be generated. In the following, a projected conjugate gradient method is proposed to obtain a descent search direction.</p><p>　　3.1. A projected conjugate gradient method</p><p>　　Lem

55、ma 1 (Fletcher & Reeves’ conjugate gradient method). Consider a continuously differentiable function</p><p>　　to generate a sequence of iterates according to</p><p>　　Then for the sequence o

56、f pointsgenerated by the conjugate gradient method</p><p><b>　　whenever</b></p><p>　　The direction generated by (11) for an unconstrained nonlinear problem is a descent direction whi

57、ch strictly decreases the objective function value provided that the corresponding gradient value is not zero. Suppose that the first-order partial derivatives for the objective function in problems (1)–(9) evaluated ate

58、xist,</p><p>　　which can be expressed as</p><p>　　where the first-order derivatives with respect to signal settings and flows are derived from Chiou [3] and the second item are from the sensitiv

59、ity analysis for network flows in Patriksson [5]. Let A denote the coefficient matrix and B the constant vector in constrains (2)–(5) the problems (1)–(9) can be rewritten as</p><p>　　In the followings, we a

60、pply Fletcher & Reeves’ conjugate gradient method to a linear constraint set as given in (14) and (15) by introducing a matrix in projecting the gradient of the objective function onto a null space of active constrai

61、nts as in (2)–(5) with equality in order to effectively search for implementable points.</p><p>　　Theorem 1 (Projected conjugate gradient (PCG) method). Consider the problem in (14) and (15) a sequence of fe

62、asible iteratescan be generated according to</p><p>　　whereis the conjugate gradient direction determined by (11) andis the step length minimizing</p><p>　　along for whichis within the feasible

63、region defined by (2)–(5). Suppose thathas full rank atwhich is the gradient of active constraints with equalities in (2)–(5) and the projection matrixis of the following form:</p><p>　　A modified search dir

64、ectioncan be determined in the following form:</p><p>　　Then the sequence of feasible pointsgenerated by the projected conjugate gradient method monotonically decreases the performance value,</p><

65、p><b>　　whenever</b></p><p>　　Proof. Following the results of Lemma 1, we have</p><p>　　Multiply Eq. (20) by projection matrixit becomes</p><p>　　Thus for sufficiently

66、 smallwe have</p><p>　　Because by definitionis the step length which minimize Z1 alongfrom</p><p>　　it implies</p><p>　　which completes this proof.</p><p>　　Theorem 2 (

67、PCG method asIn Theorem 1, when</p><p>　　if all the Lagrange multipliers corresponding to the active constraint gradients with equalities in (2)–(5) are positive or zeros, it implies the currentis a KKT poin

68、t. Otherwise choose one negative Lagrange multiplier, sayand construct a newof the active constraint gradients by deleting the jth row of</p><p>　　which corresponds to the negative componentand make the proj

69、ection matrix of the following form:</p><p>　　The search direction then is determined by (18) and the results of Theorem 1 hold.</p><p>　　Proof. Letbe a negative component of the Lagrange multip

70、lier anddefined in (17), we showBy contradiction, suppose</p><p>　　and letthen (25) can be rewritten as</p><p>　　For anythere exists a corresponding jth row, , of the active constraint in (2)–(5

71、) andsuch that</p><p>　　We subtract (27) from (26) and it follows:</p><p>　　sincewhich contradicts the assumption thathas full rank. Thus</p><p>　　Corollary 1 (Stopping condition).

72、Ifis a KKT point for problem in (14) and (15) then the search process may stop; otherwise a new descent direction atcan be generated according to Theorems 1 and 2.</p><p>　　3.2. PCG solution scheme</p>

73、<p>　　Consider the signalized road network optimal design problem in (1)–(9), a PCG solution scheme is given below:</p><p>　　Step 1: Start withset index k=0.</p><p>　　Step 2: Solve a traf

74、fic assignment problem with signal settingsfind the first-order derivatives by (13).</p><p>　　Step 3: Use the projected conjugate gradient method to determine a search direction by (18). Go to Step 4.</p&

75、gt;<p>　　Step 4: Iffind a newin (16) and letGo to Step 2. If</p><p>　　and all the Lagrange multipliers corresponding to the active constraint gradients are non-negative, is the KKT point and stop. Oth

76、erwise, find the most negative Lagrange multiplier and cancel the corresponding constraint and find a new projection matrix and go to Step 3.</p><p>　　4. Numerical example and computational comparisons</p

77、><p>　　In this section, numerical experiments are conducted twofold. Firstly, numerical computations are carried out for showing the effectiveness and robustness of the proposed PCG as compared to those of trad

78、itional methods, e.g. LCA [4] and SAB [8] in a signal-controlled grid network with distinct sets of initials. Secondly, numerical comparisons are made continuously with various congestions by monotonically increasing tra

79、vel demand scalars.</p><p>　　4.1. Grid network with signal-controlled junctions</p><p>　　A 5* 5 grid-size network shown in Fig. 1 is considered for illustrating the effectiveness of the proposed

80、 PCG method in optimal design of signalized network where 4-pair OD trips and 9 signalized junctions are taken into account. Trip rates are set at 100 veh/h and link capacity is set 1800 veh/h. Numerical results with two

81、 sets of distinct initials are summarized in Table 1. As it seen in Table 1, the proposed PCG method achieved near global optimum of 40 veh within 2.6% of SO which is short fo</p><p>　　4.2. Grid signalized n

82、etwork with increasing congestions</p><p>　　The second investigation is to test robustness of the proposed PCG method on increasingly congested grid signalized networks when compared to conventional methods.

83、 The increasing traffic congestion is caused by continuously increasing scalars to base travel demands. Computational results for the proposed PCG method are summarized in Table 2, where results are expressed in the rela

84、tive difference percentage to SO at two sets of</p><p>　　distinct initials. As it shown in Table 2, the proposed PCG method achieved the system optimum within 3% by consistently yielding the least relative d

85、ifference percentages at 20 sets of travel demands. On the other hand, the conventional methods, like LCA and SAB, achieved the system optimum with much higher values of the relative difference percentages than those did

86、 the proposed PCG method. Furthermore, taking the LCA method for example, the values of the relative difference percentages were l</p><p>　　The implementations for carrying out the computational efforts on L

87、CA, SAB and PCG methods have been conducted on SUN SPARC Ultra II workstation under operating system Unix SunOS 5.5.1 using C++ compiler. The stopping criterion for these solutions is set when the relative difference in

88、the performance index value between the consecutive iterations less than 0.05%.</p><p>　　5. Conclusions and discussions</p><p>　　In this paper, we presented a newly projected conjugate projectio

89、n method (PCG) with global convergence to effectively solve the signalized road network problem. A 5 * 5 grid road network with signal-controlled junctions is used to numerically demonstrate the robustness and superiorit

90、y of the proposed method to conventional approaches in solving optimal design of signalized road network. As it reported from numerical comparisons under traffic congestion at various sets of initials, the proposed </

91、p><p>　　It is envisaged to test the proposed PCG method on a wide range of general road signalized networks. Further investigations will be made for the signalized road network design problem with link capacity

92、 expansions and elastic travel demands.</p><p>　　Acknowledgement</p><p>　　The author is grateful for support from Taiwan National Science Council via grant NSC 95-2416-H-259-014.</p><

93、p>　　References</p><p>　　[1] M. Abdulaal, L.J. LeBlanc, Continuous equilibrium network design models, Transportation Research B 13 (1979) 19–32.</p><p>　　[2] H. Ceylan, M.G.H. Bell, Traffic si

94、gnal timing optimisation based on genetic algorithm approach, including drivers’ routing,</p><p>　　Transportation Research B 38 (2004) 329–342.</p><p>　　[3] S-W. Chiou, TRANSYT derivatives for a

95、rea traffic control optimization with network equilibrium flows, Transportation Research B 37 (2003) 263–290.</p><p>　　[4] B.G. Heydecker, T.K. Khoo, The equilibrium network design problem, in: Proceedings o

96、f AIRO’90 Conference on Models and</p><p>　　Methods for Decision Support, Sorrento, 1990, pp. 587–602.</p><p>　　[5] M. Patriksson, Sensitivity analysis of traffic equilibria, Transportation Scie

97、nce 38 (2004) 258–281.</p><p>　　[6] S. Suh, T.J. Kim, Solving nonlinear bilevel programming models of the equilibrium network design problem: a comparative review,</p><p>　　Annals of Operations

98、Research 34 (1992) 203–218.</p><p>　　[7] R.A. Vincent, A.I. Mitchell, D.I. Robertson, User guide to TRANSYT, version 8. TRRL Report, LR888, Transport and Road</p><p>　　Research Laboratory, Crowt

99、horne, 1980.</p><p>　　[8] H. Yang, S. Yagar, Traffic assignment and signal control in saturated road networks, Transportation Research A 29 (1995) 125–139.</p><p>　　[9] H. Yang, M.G.H. Bell, Mod