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

王 利，楊青驥

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

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

王 利1，楊青驥2

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

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

多類別；容量約束；通行費用；Wardrop型原理

0 引言

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

第一原理：在交通網(wǎng)絡的每一對起-終點之間，有人走的路徑上的通行時間都是相等的，并且少于沒有人走的路徑上的通行時間；

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

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

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

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

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

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

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

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

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

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

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

或路段流量表示的等價形式

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

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

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

變分不等式(VI)的解等價于優(yōu)化問題

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

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

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

則稱**

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

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

2 Wardrop型原理

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

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

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

成立。

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

證明 設路徑r通過的路段為a1,…,aI。 在?的第r列?·r中,

路徑r上的懲罰費用

或

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

接下來，給出多類別網(wǎng)絡中用實際通行費用描述用戶均衡的結(jié)論。

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

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

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

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

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

定義1.2其實是將經(jīng)典Wardrop原理中的實際通行費用換為廣義通行費用來刻畫容量約束下的多類別用戶均衡。在定理2.1中，仍然用實際費用，只是借助了更接近于現(xiàn)實的概念——飽和性來刻畫多類別用戶均衡，稱之為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－），女，河南洛陽人，講師，碩士，主要研究方向：運籌學應用，電子郵箱wangli@sspu.cn。