王 利，楊青驥

(1. 上海第二工業(yè)大學(xué)，上海 201209；2. 上海金融學(xué)院應(yīng)用數(shù)學(xué)系，上海 201209)

多類別交通網(wǎng)絡(luò)的Wardrop型原理

王 利1，楊青驥2

(1. 上海第二工業(yè)大學(xué)，上海 201209；2. 上海金融學(xué)院應(yīng)用數(shù)學(xué)系，上海 201209)

研究了有容量約束的網(wǎng)絡(luò)中有限多類別用戶形成的均衡。在考慮容量約束的網(wǎng)絡(luò)中，結(jié)合用戶的異質(zhì)性來(lái)分析廣義通行費(fèi)用、實(shí)際通行費(fèi)用；結(jié)合路徑的飽和性，將經(jīng)典的Wardrop原理推廣到有容量約束的多類別的Wardrop型原理。

多類別；容量約束；通行費(fèi)用；Wardrop型原理

0 引言

1952年，英國(guó)交通工程師J. G. Wardrop 提出了兩個(gè)基本原理[1]。

第一原理：在交通網(wǎng)絡(luò)的每一對(duì)起-終點(diǎn)之間，有人走的路徑上的通行時(shí)間都是相等的，并且少于沒(méi)有人走的路徑上的通行時(shí)間；

第二原理：對(duì)于給定的交通網(wǎng)絡(luò)，管理者的目標(biāo)是最小化平均的通行時(shí)間。第一原理基于用戶的理性假設(shè)：網(wǎng)絡(luò)中的用戶總是盡可能地最小化自己的通行時(shí)間。所有的用戶都如此選擇的結(jié)果形成了用戶均衡 (user equilibrium)。第二原理假設(shè)用戶是合作的，從而保證總的通行時(shí)間最少。

然而，由于容量約束的引入，Wardrop第一原理不再適用。在研究容量約束下的交通網(wǎng)絡(luò)均衡的文獻(xiàn)中，有一些研究工作者著手于推廣網(wǎng)絡(luò)均衡的定義并分析相應(yīng)的均衡性質(zhì)。比如，1994、1997年，Maugeri等給出了考慮路徑上容量約束的廣義用戶均衡（Generalized User Equilibrium）[2]、擴(kuò)展Wardrop均衡 ( Extended Wardrop Equilibrium)[3]；1994～1999年，Larsson和Patriksson定義了在廣義通行費(fèi)用下的Wardrop均衡（Generalized Wardrop Equilibrium），研究了有附加限制（side constraints）的交通均衡模型，給出了均衡解的性質(zhì)、廣義費(fèi)用的性質(zhì)等[4-6]。但是這些研究并未考慮到網(wǎng)絡(luò)中用戶的異質(zhì)性。

在交通問(wèn)題的研究中，有很多學(xué)者關(guān)注網(wǎng)絡(luò)中用戶的異質(zhì)性。1972年，Dafermos 研究了多類別的交通問(wèn)題，認(rèn)為不同類別的用戶有不同的成本函數(shù)[7]。用戶在選擇最佳出行路徑時(shí)可能面對(duì)著多種準(zhǔn)則的考慮，如通行時(shí)間、通行費(fèi)用等。一些學(xué)者引入時(shí)間價(jià)值（value of time, VOT）參數(shù)作為一種權(quán)重因子，它將通行時(shí)間轉(zhuǎn)化為貨幣單位。VOT參數(shù)取值為離散數(shù)值，意味著網(wǎng)絡(luò)中所有用戶被分成有限個(gè)類別，每一類用戶有一個(gè)相同的時(shí)間價(jià)值。近些年來(lái)，很多學(xué)者對(duì)多類別、多準(zhǔn)則的交通網(wǎng)絡(luò)均衡問(wèn)題及應(yīng)用進(jìn)行了研究，如參考文獻(xiàn)[8-10]等。

本文試圖在考慮容量約束的網(wǎng)絡(luò)中，結(jié)合用戶的異質(zhì)性來(lái)分析廣義通行費(fèi)用、實(shí)際通行費(fèi)用；結(jié)合路徑的飽和性將經(jīng)典的Wardrop原理敘述推廣到有容量約束的多類別的Wardrop型原理。在第一節(jié)中，將介紹多類別的交通網(wǎng)絡(luò)及廣義Wardrop均衡的相關(guān)結(jié)論；第二節(jié)中，給出了在有容量約束的網(wǎng)絡(luò)中，刻畫多類別用戶均衡的Wardrop型原理。

1 多類別的交通網(wǎng)絡(luò)

這里的pv表示路徑p上的流量，pc表示路徑p上的通行時(shí)間，wπ表示路徑p所連接的OD對(duì)w之間的最短通行時(shí)間。

現(xiàn)在考慮用戶依據(jù)兩種準(zhǔn)則——通行時(shí)間和通行費(fèi)用（收費(fèi)），來(lái)選擇自己的出行路徑。設(shè)是第m類用戶的時(shí)間價(jià)值，相應(yīng)的交通需求被分為M類，對(duì)每是網(wǎng)絡(luò)中第m類用戶的用戶需求構(gòu)成的向量。假設(shè)d(m)是給定的。

其中?是路段-路徑之間的關(guān)聯(lián)矩陣，當(dāng)路段a在路徑p上時(shí)，其元素路徑、路段上所有類別的用戶構(gòu)成的可行流向量集合分別為

路段上的流量受到的約束為

其中每一kg()x都是連續(xù)可微的凸函數(shù)，這K個(gè)函數(shù)構(gòu)成向量()gx。這些約束可以轉(zhuǎn)化成路徑上的限制，

在路徑p、路段a上的通行時(shí)間函數(shù)分別記為cp(v), ta(x)，根據(jù)可加性，有或向量-矩陣形式構(gòu)成的向量。設(shè)及相應(yīng)的滿足下列變分不等式(Variational Inequality，簡(jiǎn)記為VI)

或路段流量表示的等價(jià)形式

為方便起見(jiàn)，不加區(qū)別地用S (VI) 表示 (VI) 路徑流量形式的解集或者等價(jià)的路段流量形式的解集，記其中的解為

引理1.1 變分不等式(VI)的解存在。

其中u屬于某個(gè)緊集合，F(xiàn)是一個(gè)連續(xù)的向量函數(shù)。由變分不等式理論(見(jiàn)參考文獻(xiàn)[11]等)得到(1)式的解存在，也即(VI)的解存在。 證畢

變分不等式(VI)的解等價(jià)于優(yōu)化問(wèn)題

的解。下文中提到的(VI)的約束

的乘子總是指在優(yōu)化問(wèn)題(2)式～(7)式中的相應(yīng)乘子。

為方便起見(jiàn)，統(tǒng)一記為()gx?。

則稱**

(,)xv是多類別交通網(wǎng)絡(luò)的廣義Wardrop均衡(MGWE)。

因而對(duì)于任意的OD對(duì)w∈W，由條件(11)式～ (13)式得到是OD對(duì)w之間第m類用戶的最低廣義通行費(fèi)用；并且在OD對(duì)w之間所有第m類用戶通過(guò)的道路上，此類用戶的廣義通行費(fèi)用是相等的。因此，條件(9)式、(10)式成立，即定理結(jié)論成立。

2 Wardrop型原理

這一節(jié)中，首先給出不飽和的定義及相關(guān)的假設(shè)；然后得到不飽和路徑上懲罰費(fèi)用的性質(zhì)；最后證明用實(shí)際費(fèi)用描述的Wardrop型原理。

則稱路段a∈A是不飽和的。如果在路徑r上的全部路段都是不飽和的, 則稱該路徑是不飽和的。

顯然，由這個(gè)定義可以得到：在x∈?x∩Dx處，如果路徑r飽和，則存在其上的某個(gè)路段a及某個(gè)k, 有

成立。

對(duì)于不飽和的路徑，有如下結(jié)論：

證明 設(shè)路徑r通過(guò)的路段為a1,…,aI。 在?的第r列?·r中,

路徑r上的懲罰費(fèi)用

或

成立，從而可以得到結(jié)論成立。 證畢

接下來(lái)，給出多類別網(wǎng)絡(luò)中用實(shí)際通行費(fèi)用描述用戶均衡的結(jié)論。

1) 在OD對(duì)w之間，有第m類用戶通過(guò)的路徑上該類用戶的廣義通行費(fèi)用相等且為最低；

2) 假設(shè)在OD對(duì)w之間的某ml條路徑（不妨設(shè)為前ml條）上有第m類用戶通過(guò)，而且其中的ms條路徑是不飽和的，則這些路徑可以如下排序

證明 1) 根據(jù)定理1.1可以得到結(jié)論。

2) 由(1)式可以得到有第m類用戶通過(guò)的ml條路徑（其中，前ms條路徑不飽和）上，該類用戶的廣義通行費(fèi)用相等, 即

根據(jù)假設(shè)2.1、定義2.1及引理2.1，在不飽和的路徑上，有。 所以，

定義1.2其實(shí)是將經(jīng)典Wardrop原理中的實(shí)際通行費(fèi)用換為廣義通行費(fèi)用來(lái)刻畫容量約束下的多類別用戶均衡。在定理2.1中，仍然用實(shí)際費(fèi)用，只是借助了更接近于現(xiàn)實(shí)的概念——飽和性來(lái)刻畫多類別用戶均衡，稱之為Wardrop型原理。

[1] WARDROP J G. Some theoretical aspects of road traffic research[J]. ICE Proceedings: Engineering Divisions, 1952, 1(3): 325-362.

[2] MUGERI A. Optimization problems with side constraints and generalized equilibrium principles[J]. Le Matematiche, 1994, 49(2): 305-312.

[3] MUGERI A, OETTLI W, SCHLAGER D. A flexible form of wardrop's principle for traffic equilibria with side constraints[J]. Rendiconti del Circolo Matematico di Palermo, Serie 2, Supplement, 1997, 48: 185-193.

[4] LARSSON T, PATRIKSSON M. Equilibrium characterizations of solutions to side constrained asymmetric traffic assignment models[J]. Le Matematiche, 1994, 49(2): 249-280.

[5] LARSSON T, PATRIKSSON M. An augmented Lagrangean dual algorithm for link capacity side constrained traffic assignment problems[J]. Transportation Research Part B: Methodological, 1955, 29(6): 433-455.

[6] LARSSON T, PATRIKSSON M. Side constrained traffic equilibrium models—analysis, computation and applications[J]. Transportation Research Part B: Methodological, 1999, 33(4): 233-264.

[7] DAFERMOS S C. The traffic assignment problem for multiclass-user transportation networks[J]. Transportation Science, 1972, 6(1): 73-87.

[8] YANG H, HUANG H J. The multi-class, multi-criteria traffic network equilibrium and systems optimum problem[J]. ransportation Research Part B: Methodological, 2004, 38(1): 1-15.

[9] HUANG H J, LI Z C. A multiclass, multicriteria logit-based traffic equilibrium assignment model under ATIS[J]. European Journal of Operational Research, 2007, 176(3): 1464-1477.

[10] ZHANG X, YANG H, HUANG H J. Multiclass multicriteria mixed equilibrium on networks and uniform link tolls for system optimum[J]. European Journal of Operational Research, 2008, 189(1): 146-158.

[11] KINDERLEHRER D, STAMPACCHIA G. An Introduction to Variational Inequalities and Their Applications[M]. New York: Academic Press, 1980.

Wardrop-Type Principle in Finite Multiclass Traffic Network

WAN G Li1, YANG Qing-ji2
(1. Shanghai Second Polytechnic University, Shanghai 201209, P.R.China；2. Department of Applied Mathematics, Shanghai Finance University, Shanghai 201209, P.R.China)

Equilibrium of finite multiclass customers in traffic network with capacity constraints is considered. For the network, generalized and actual travel cost are analyzed by combining with heterogeneity of customers. The classical Wardrop principle is reformulated as Wardrop-type principle in finite multiclass traffic network by introducing the saturation of path flow.

finite multiclass; capacity constraint; travel cost; Wardrop-type principle

O22

A

1001-4543(2011)04-0325-06

2011-09-12;

2011-12-19

王利（1977－），女，河南洛陽(yáng)人，講師，碩士，主要研究方向：運(yùn)籌學(xué)應(yīng)用，電子郵箱wangli@sspu.cn。