多模式交通条件下合理制定旅客票价的优化模型及算法[1]

文章编号:1003-207(2000)04-0055-08
多模式交通条件下合理制定旅客
票价的优化模型及算法
四兵锋,高自友
(北方交通大学交通运输学院,北京　100044)
收稿日期:2000-01-26;修订日期:2000-08-10
基金项目:国家自然科学基金资助项目(79920014);教育部“跨世纪优秀人才培养计划”基金资助项目
作者简介:四兵锋(1972-),男(汉族),河北邢台人,北方交通大学运输学院,博士研究生,研究方向:计算机、运筹学在交通管
理中的应用.
摘　要:在本文中,充分考虑了旅客和交通管理部门两方面的利益,提出了一个双层规划模型来描述城市间多种交通方式竞争条件下合理制定旅客票价问题。

在此模型中,既保障了旅客使自己的广义出行费用最小,又使得交通管理部门在客运市场的竞争中取得最大的经济效益。

然后给出了求解该模型的基于灵敏度分析的启发式算法(SAB )。

最后用一个实际算例说明了该模型及算法的应用。

关键词:双层规划;灵敏度分析;均衡模型
中图分类号:C931 文献标识码:A
1　引言
从我国近几年交通运输的发展来看,城市间的交通客运市场的竞争日渐激烈。

铁路与公路这两种主要的交通方式在短途客运市场上的竞争更加激烈。

在市场经济条件下,交通运输企业是运输市场的主体,应该最直接把握市场。

而价格是市场的灵魂,市场机制以价格为核心,因此交通运输企业应该合理规范地运用交通价格来参与交通运输市场竞争,近期的北京到天津之间的客运市场的变化则在实际中说明最这一问题。

一般情况下,不同交通方式的客流量受其价格因素的影响很大,如果某种交通方式的旅客票价很高,那么就会使这种交通方式的客流减少,而转移到其它的交通方式上。

对于交通运输部门来说,既消耗了大量运能,也不会产生最大的经济效益;而旅客票价的适当降低则会吸引更多的客流,但是也不一定能产生最大的客运经济效益。

当然有时候客流量的高低并不完全取决于票价的涨落,如运输过程中的时间、方便性、舒适性、安全性等因素也会影响不同交通方式的客运流量。

但就目前我国铁路和公路这两种客运方式来看,在一段相对时间内,各种交通方式在运输过程中的时间、方便性、舒适性、安全性等硬件因素一般来说变化较小。

所以,相对来说旅客票价的变化对客流需求变化的影响是最主要的。

因此,制定合理的交通旅客票价相对于客流导向、有效利用既有设备、提高交通客运部门的经济效益均有很大的帮助。

可以把多模式交通条件下旅客票价的制定问题看作一个Leader -Follower 问题,其中交通管理部门是领导者(Leader ),而旅客的出行行为为跟随者(Follower )。

决策部门只能通过政策和管理
第8卷　第4期2000年 12月 中国管理科学Chinese Journal of Management Science Vol 18,No 14Dec 1,2000
来影响旅客在出行时对于交通方式的选择,但不能控制他们的选择。

旅客根据自己的需要及习惯来选择交通方式。

这种关系可以用双层规划模型(bi-level programming)来进行描述,其基本思想为下面的数学模型:
(P1)　(U1)　max
x
F(x,y(x))(1)
s1t1　G(x,y(x))≤0(2)其中y(x)由下层模型给出
　(L1)　min
y
f(x,y)(3)
s1t1　g(x,y)≤0(4)从上面可以看出,双层规划模型(P1)由两个子模型(U1)和(L1)构成,其中(U1)称为上层规划, (L1)称为下层规划。

F是上层规划所确定的目标函数,x为上层规划的决策变量,关系式(2)是对变量x的约束;f为下层规划所确定的目标函数,y为下层规划的决策变量,关系式(4)是对变量y 的约束;在双层规划模型(P1)中,上层决策部门通过设置x的值影响下层决策者,限制了下层问题的可行约束集,而下层决策者的行为反过来又会通过y影响上层的决策。

因此下层决策变量y是上层决策变量x的函数,即y=y(x),这个函数一般被称为反应函数。

双层规划在公路交通领域已得到了广泛的应用,尤其在交通网络设计(K im&Suh,1990)、交通需求预测Yang,1995)及城市交通信号控制(Yang&Yagar,1994)等问题上。

本文在充分考虑交通客运管理部门和旅客两方面利益的基础上,提出了一个双层规划模型来描述在多种交通方式竞争条件下的合理制定城市间的旅客票价问题。

上层规划问题可以表示为交通客运管理部门在政府规定的范围内制定最佳的旅客票价以使得企业取得最大的经济效益。

而下层规划问题则描述了城市间的多模式交通条件下,客流量在不同交通方式之间的分配,它的目标是使每个旅客在出行过程中的广义出行费用最低。

这两方面看起来是矛盾的,但事实上这两方面相互作用的结果是取得共同的平衡点,即双层规划问题的最优解,从而为交通客运管理部门在不同时段内制定合理的旅客票价提供定量分析的依据。

2　城市间多模式交通条件下的用户选择模型
城市间的交通配流与城市交通配流不同,由于各种交通方式都有其固定的运行线路,而且在当前激烈的市场竞争条件下,各种交通方式都有足够的运能,因此路径上的拥挤问题并不是旅客在出行过程中所考虑的重要因素,所以在城市之间的交通配流中,一般不存在路径的选择问题,而只有交通方式的选择问题。

一般情况下,旅客总是力图选择从起点到终点之间的总的广义出行费用(包括出行时间、旅客票价、安全、方便舒适等)最低的交通方式,如果所有的出行者都选择某一种交通方式(比如铁路,假定一开始它的出行费用是最低的)。

那么随着该交通方式客流需求的增加,它的总的出行费用就会上升,例如票价上升,出行时间变大,服务质量下降等。

这样就会使得一部分旅客放弃选择这种交通方式,而选择其它交通方式,而别的交通方式的出行费用也会随着客流需求的增加而上升。

最终,在不同的交通方式之间会达到一种客流分配的稳定的均衡状态。

这种均衡状态可以描述为:在城市之间的所有可供选择的交通方式中,旅客所利用的各种交通方式的广义出行费用全部相等,并且不大于未被利用的交通方式的出行费用。

c n =c(min)　如果q n>0
≥c(min)　如果q n=0
,n∈N(5)
・
6
5
・中国管理科学 2000年
其中c n 表示城市间第n (n ∈N )种交通方式的广义出行费用,c (min )表示均衡状态下城市间的广义出行费用,q n 表示城市间第n (n ∈N )种交通方式的客流量,N 为城市间所有交通方式的集合。

本文构造了下面的数学规划模型来描述城市间多模式交通条件下的用户选择行为:
(M )　minZ (q )=
∑n ∈N ∫q n 0f (x )dx (6)
s 1t 1　∑n ∈N q n =Q
(7)
q n ≥0,n ∈N
(8)其中函数f 是交通方式的广义费用函数,在这个函数中不同交通方式的客流量是自变量,即c n =f (q n )(n ∈N )。

f 取不同的形式,便可以得到不同的客流量在交通方式之间的分离模式,在交通研究中,最常用的广义费用函数形式有幂函数形式和对数函数形式;约束(7)表示城市间总的客流需求是已知并且固定的,Q 表示表示城市间总的客流需求;约束(8)为变量的非负约束。

可以证明模型(M )的解等价于用户均衡条件(5)。

对于任意一个数学规划问题,其任意局部极小点或驻点都均满足一阶必要条件,如果模型(M )的一阶必要条件等同于用户均衡条件(5),那么就证明了模型(M )的解与用户均衡条件(5)的等价性。

在此限于篇幅,不再做详细证明。

一般情况下,不同交通方式的广义费用是随着客流量的增加而递增的,也就是说函数f 是一个递增函数,它对q n 的导数是大于0的,因此模型(M )的目标函数的Hessian 矩阵是正定的,即目标函数是凸的,而约束集也是凸的。

所以模型(M )是一个凸规划问题,有唯一解。

模型(M )可以用Frank -Wolfe 方法来求解(Sheffi ,1985)。

3　多模式交通条件下的合理制定旅客票价的双层规划模型
模型(M )描述了城市间多模式交通条件下的客流量在不同交通方式之间的分配问题,是从出行者(即旅客)的角度出发的,即对于旅客来说,他们总是选择广义出行费用最小的交通方式。

所得到的解是在一定条件下,比如客票价格、出行时间、舒适程度等因素固定,城市间的总的客运需求在不同的交通方式之间的分配模式,即城市间各种交通方式的客流量。

在此基础上,可以构造出一个双层规划模型来描述合理制定交通票价的问题。

下层问题就是上面所提出的城市间多模式交通条件下的用户选择模型(M ),而下层问题可以根据交通决策部门所制定的目标的不同而有不同的形式。

如果交通管理部门只关心其客运收入情况,假定某种交通方式的客票价格为u n ,那么客运的总收入可以表示为:
F 1=q n u n ,n ∈N (9)
如果交通管理部门关心的是客运的经济效益,即客运盈利情况,那么第n 种交通方式的客运收益可以表示为:
F 2=q n (u n -c n ),n ∈N (10)
其中c n 表示第n 种交通方式的客运成本。

在市场经济条件下,政府对旅客票价具有指导作用。

如果国家旅客运输政策没有大的变动,各种交通方式的旅客票价的基本框架必将限定在上限为政府最高限价和下限为此交通方式的客运成本之间。

即
c n ≤u n ≤u n (m ax ),n ∈N (11)
其中u n (m ax )表示城市间的第n 种交通方式的旅客票价最高限。

・75・第4期 四兵锋等:多模式交通条件下合理制定旅客票价的优化模型及算法
在本文中,我们构造了如下的双层规划模型,来描述城市间多模式交通条件下的旅客票价制定的优化问题:
(P2)　(U2)　max F 2=q n (u n )・(u n -c n )
s 1t 1　c n ≤u n ≤u n (m ax )
其中q (u )由下模型得出:
(L2)　min Z (q )=
∑n ∈N ∫ln 0f (x )dx s 1t 1∑n ∈N
q n =Q
q n ≥0,n ∈N
在上层模型(U2)中,目标函数表示使第n 种交通方式的客运收益最大,约束表示第n 种交通方式的旅客票价的范围。

下层模型(L2)表示在旅客票价确定的条件下,旅客的方式选择行为。

当然,如果交通管理部门只关心其客运收入情况,那么上层模型的目标函数可以采用式子(9)的形式。

也可以根据决策部门制定目标的不同而采用不同的上层规划模型。

通过求解上述双层规划问题,就可以找到合理制定交通旅客票价的策略以达到决策部门的目标。

需要注意的是,双层规划问题都是非凸的,所以很难得到模型的全局最优解。

并且根据Ben -Ayed 和Blair 等人的研究,双层规划是一个N P -hard 问题,不存在多项式求解算法。

在实际应用中,为了使计算简便易行,求解双层规划的算法一般都是启发式算法。

4　基于灵敏度分析方法的启发式算法
求解双层规划问题的关键在于找到反应函数q (u )的具体形式,这是很难做到的。

不过,我们可以通过灵敏度分析方法得出多模式交通条件下的某种交通方式的客流量对其旅客票价的导数关系,这样就可以利用泰勒展开式对反应函数进行线性的近似,从而简化反应函数以求解双层规划问题,这就是基于灵敏度分析方法的启发式算法SAB (Sensitivity Analysis Based Alogrithm )。

SAB 算法已经成功地应用在城市交通信号控制的最优设计(Yang &Yagar ,1994),以及拥挤条件下的OD 矩阵估计(Nang ,1995)等问题上。

灵敏度分析方法主要应用在变分不等式中,通过这种方法,可以求出变分不等式的解对于其中的扰动参数的导数。

在本文中,假定这个扰动参数为旅客票价,并且假定影响客流变化的其它因素如时间、舒适性和安全性等因素均保持不变。

首先,用户均衡配流模型(M )可以用下面的变分不等式来表示(Tobin &Fiacco ,1986):
f (q 3)T (q -q 3)≥0(12)
其中q ∈{q |Q =ΛT q ,q ≥0},q 3表示模型(M )的均衡解。

注意这里的变量是用列矢量来表示的,其中:
q 3=(q 13,q 23,…,q N 3)T
q =(q 1,q 2,…,q N )T
f (q 3)=(f (q 13),f (q 23),…,f (q N 3))
T Λ=(1,…,1)T ∈E N ,表示维数为N ,元素全为1的列向量。

再来考虑f (q )中存在旅客票价扰动参数u 的一般情况,即f (q ,u ),那么上面的变分不等式将变为如下形式:
・85・中国管理科学 2000年
f (q 3(u ),u )T (q -q 3(u ))≥0
(13)其中所有的q ∈{q (u )|Q =ΛT q (u ),q (u )≥0}。

假定已经知道变分不等式(13)在u =u (0)时的解q 3(u (0)),并且这个解是唯一的。

根据文献
〔7〕,此问题在u =u (0)时解的必要条件为:
f (q 3(u ),u )-μ=0
(14)Q =ΛT q 3(u )
(15)其中μ是一个有N 个相同元素的拉格朗日乘子向量。

设:y (u )=[q (u ),μ(u )]T ,用J y (u )表示(14)和(15)对于[q ,μ]的雅克比矩阵,用J u (u )表示(14)和(15)对于u 的雅克比矩阵,那么有如下结果:
y u (u )=J -1y (u )[-J u (u )](16)
假定u (0)n 为城市间的第n 种交通方式旅客票价的初始值,那么,在这个价格条件下,并且假定其它交通方式的旅客票价都保持不变,那么就可以通过求解下层问题得到城市间第n 种交通方式
的客流量q *n (u (0)n )。

并且通过灵敏度分析方法可以得出多模式交通条件下城市间的第n 种交通方
式的客流量对其旅客票价的导数关系9q n /9u n ,那么反应函数可以用泰勒展开式近似为:
q n (u n )=q 3n (u (0)n )+9q n 9u n
(u n -u (0)n )(17) 将(17)式代入到上层目标函数中,则上层问题就变成一个普通的非线性优化问题,可以用已有的方法求解。

对于从上层问题求出的最优解(即新的旅客票价的最优价格),再一次求解下层问题,就可以得到新的多模式交通条件下的客流量,重复上面的基本思路,又可以得到一组新的旅客票价。

如此重复计算,最后有望收敛于双层规划模型的最优解。

算法的具体操作步骤如下:
第一步:初始化。

设置第n 种交通方式的旅客票价的初始值为{u (0)n },并且置i =0。

第二步:在{u (i )n }条件下,求解下层客流分配问题,得到均衡解{q (i )n }。

第三步:利用灵敏度分析方法找到多模式交通条件下的第n 种交通方式的客流量对其旅客票价的导数,并根据(17)得出反应函数的线性近似形式。

第四步:将反应函数的线性近似代入到上层规划目标函数中,求解上层问题得到一组新的旅客票价{y (i )n }。

第五步:迭代。

计算u (i +1)n =u (i )n +h (i )(y (i )n -u (i )n ),其中h (i )为迭代步长,可以用一维搜索法得出。

第六步:收剑判断。

如果|u (i +1)n -u (i )n |≤δ,那么算法停止。

否则令i =i +1,转到第二步。

其
中δ为迭代精度。

5　算例
在这一节中,我们用一个实际例子来说明双层规划模型及求解算法在多模式交通条件下的应用。

算例中的数据均来自《京津唐客运市场调查报告》,
所用到的参数值是通过统计方法估计得到的。

图1　算例
・95・第4期 四兵锋等:多模式交通条件下合理制定旅客票价的优化模型及算法
从北京到天津之间的客运市场中主要有两种交通方式,即铁路(1)和公路(2)。

不同交通方式的广义费用函数采如下幂函数形式:
f (q n )=a (q n )b -V n ,n =1,2
(18)其中V n 表示不同交通方式的效用,a ,b 为待定参数。

不同交通方式的效用函数可以用下面的式子来表示:
V n =-α1t n -α2u n +α3c n ,n =1,2
(19)其中t n 为出行时间因素,u n 表示票价因素,c n 为方便、舒适和安全等综合因素;αi (i =1,2,3)为待定参数。

假定铁路和公路在运营过程中旅行时间以及方便舒适性等综合因素均保持不变,北京到天津之间总的OD 量已知,分别为:
表1　已知数据
交通方式
t n (小时)u n (元)c n 铁路
117(2103,40)61053公路
1152551933
总的OD 量25000在算例中所要用的参数值由下表给出:
表2　参　数　值
参数
α1α2α3a b 取值31003175210031000140
第一步:初始化。

北京到天津之间铁路客运的旅客票价初始值为20元,并置i =0。

第二步:在铁路及公路的旅客票价、旅行时间以及方便舒适性因素固定的条件下,求解下层客
流分配问题,得到均衡条件下铁路客运的客流量q (0)1=1492210312。

第三步:利用灵敏度分析方法得到多模式交通条件下铁路客流量对其旅客票价的导数,
9q (0)
1/9u (0)1=-44813374,根据(17)式得到反应函数的近似线性关系,即:q 1=2388817792-44813374・u 1
第四步:将第三步中得出的近似线性关系代入上层规划的目标函数中,并求解上层规划问题得
到y (0)1=2619340元。

第五步:用一维搜索法得到迭代步长h (0)=019605,进行更新,得出新的铁路旅客票价q (1)1=
2616604元。

第六步:收剑判断。

假定迭代精度δ=0101,显然q (1)1-q (0)1=616604>0101,令i =i +1,
转到第二步。

最后,经过2次迭代得到北京到天津之间铁路客运的旅客票价的合理值为2616574元,此时铁路的客流量为1194917871,铁路的客运收入为31854917863元。

我们选取不同的初始值,计算结果如下表:
・06・中国管理科学 2000年
表3　计算结果
初始值
(单位:元)
迭代步数最优旅客票价(单位:元)铁路客流量(单位:人次)客运收入(单位:元)5
2261661195017131854917910
2261651195118831854917715
2261661195012631854918020
2261661194917931854917925
2261651195217331854917830
2261661194712931854917635
326166119481673185491794032616611949137318549177
从以上结果可以看出,不同的初始铁路旅客票价所得到的最优解是非常接近的,这表明了:尽管双层规划一般都是非凸的,利用启发式的基于灵敏度分析算法在理论上很难得到其全局最优解,不过将这种方法应用在合理制定城市间交通价格问题上是可行的。

6　结论
对于交通价格的制定问题,传统的研究方法一般都是定性的,或者采用简单的统计推断方法。

并没有考虑交通运输市场中的不同交通方式之间的竞争,也很少考虑出行者的模式选择行为,这显然是不合理的。

在本文中,我们利用双层规划方法来研究旅客票价的制定问题,充分考虑了客运部门和出行者两方面的利益以及票价对不同交通方式的客流量的影响。

并提出了求解这种双层规划模型的基于灵敏度分析的启发式算法,通过一个实际例子可以看出,本文所提出的模型及算法是可行的。

参考文献:
[1]Bard J F.An Algorithm for Solving the G eneral Bi -Level Programming Problem [J ].Mathematics of Operations Research ,1983,8:260-272.
[2]Ferrari P.Road pricing and Network Equilibrium [J ].Transportation Research ,1995,29(3):357-372.
[3]Friesz T L ,Harker P T.Multicriteria Spatial Price Equilibirium Network Design :Theory and Computational Results [J ].Trans 2portation Research ,1983,17B (5):411-426.
[4]G ao Z Y ,Si B F.An Equilibrium Assignment Model for Mixed Network [C].Proceedings of ICTTS ’98.The American Society of Civil Engineers ,1998,391-398.
[5]Norbert O.Urban Travel Demand Modeling :From Individual Choice to G eneral Equilibrium [M ].A Wiley -Interscience Publica 2tion ,John Wiley &Sons ,INC ,1994,112-203.
[6]Sheffi Y.Urban Transportation Networks :Equilibrium Analysis with Mathematical Programming Methods [M ].Prentice -Hall ,Englewood Cliffs ,New Jersey ,1985,56-131.
[7]Tobin R L ,Fiacco A V.Sensitivity Analysis for Variational Inequalities [J ].Journal of Optimization Theory and Application ,1986,48(1):191-204.
[8]Y ang H ,Y agar.Traffic Assignment and Traffic Control in G eneral Freeway -arterial Corridor Systems [J ].Transportation Re 2search ,1994,28:463-486.
[9]Y ang H.Sensitivity Analysis for Queuing Equilibrium Network Flow and Its Application to Traffic Control [J ]p.Mod 2eling ,1995,22:223-235.
[10]Y ang H ,Lam W H K.Optimal Road Tolls under Conditions of Queuing and Congestion [J ].Transportation Research ,1996,30
(5):319-331.
・16・第4期 四兵锋等:多模式交通条件下合理制定旅客票价的优化模型及算法
[11]Y ang H.Sensitivity Analysis for the Elastic -Demand Network Equilibrium Problem with Applications [J ].Transportation Re 2search ,1997,31(1):55-70.
[12]Y ang H ,Michael G H B.Traffic Restraint ,Road Pricing and Network Equilibrium [J ].Transportation Research ,1997,31(4):303-314.
[13]四兵锋,高自友1铁路客票价格与客流量之间的灵敏度分析[J ]1铁道学报,1999,(4):13-161
[14]四兵锋,高自友1城市间公路客运的客票票价与其客流量之间的灵敏分析[J ]1中国公路学报,2000,(2):91-951
[15]高自友,宋一凡,四兵锋1城市交通连续平衡网络设计理论与方法[M ]1北京:中国铁道出版社,2000.49-1061
[16]安梅,高自友,杨璐.A Non -monotone Algorithm for Solving the User Equilibrium Assignment Optimal Model [C].Proceedings of 99’International Conference on Management Science and Engineering ,1999.
Optimal Model and Solution Algorithm for Passenger -Ticket Pricing
under the Condition of Multimodal T ransportation
SI Bing 2feng ,G AO Zi 2you
(Northern Jiaotong University ,Beijing 100044,China )
Abstract :In this paper ,the benefits of passengers and transportation management departments are both considered and a bi -level programming model is presented in order to seek the optimal passenger -ticket price under the competition be 2tween different inter -city traffic modes.The lower -level problem represents an equilibrium model that describes passen 2gers ’mode -choice behavior under the condition of multimodal trans portation.The upper -level problem is to determine passenger -ticket price to maximize the revenue of trans portation management departments while considering passengers ’mode -choice behavior.A heuristic algorithm for the bi -level problem is also proposed.Finally the applications of the model and its algorithm are illustrated with a practical example.
K ey w ords :bi -level programming ;sensitivity analysis ;equilibrium model
・26・中国管理科学 2000年。