Advances in Applied Mathematics
Vol.05 No.03(2016), Article ID:18266,9 pages
10.12677/AAM.2016.53041

On Application of Wu’s Method in Solving the Beckmann Traffic Assignment Model

Qiuyan Zhan1, Lu Chao1, Xianpeng Wei2

1College of Art and Science, Shanghai Maritime University, Shanghai

2College of Transportation, Shanghai Maritime University, Shanghai

Received: Jul. 21st, 2016; accepted: Aug. 13th, 2016; published: Aug. 16th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

The Beckmann optimization model of traffic equilibrium assignment has drawn more and more attention of researchers because of its wide application in transportation science and engineering. The model is usually solved by W-F algorithm. In the present paper, the Beckmann Traffic equilibrium assignment model is investigated by Wu’s Method. Using Mathematics-Mechanization ideal and symbolic computation, we equivalently transform the model to finding the zero set problem of the characteristic sets of a multivariable polynomials and realize the algorithm on computer by computer algebra system. As an application of Wu’s Method, we use it to solve the specific Beckmann optimization model. As a result, we prove the efficiency of Wu’s method and provide a new research idea for such kind of the transportation problems.

Keywords:Beckmann Model, Wu’s Method, Mathematics-Mechanization, Characteristic Set

吴方法在求解Beckmann交通平衡分配模型中的应用

战秋艳1,朝鲁1,魏贤鹏2

1上海海事大学文理学院,上海

2上海海事大学交通运输学院,上海

收稿日期:2016年7月21日;录用日期:2016年8月13日;发布日期:2016年8月16日

摘 要

交通流分配中的Beckmann优化模型的广泛适用性越来越受到人们的关注。在通常解Beckmann模型时往往采用W-F算法,该算法得到的解为近似解,并非理想的精确解。本文采用吴方法对Beckmann交通平衡分配优化模型的求解方法进行了研究。首先,把问题等价的转化为求解多元多项式组特征列集零点集的问题。其次,对后者用吴方法处理获得零点集,进而获得优化问题的解。作为方法的应用,我们用该方法求解了具体的Beckmann优化模型的解,说明了提出方法的有效性。该方法也提供了用吴方法探索交通问题的一个新的思路。

关键词 :Beckmann模型,吴方法,数学机械化,特征列

1. 引言

交通流分配是交通需求四阶段预测的最后阶段,是实现交通规划设计的关键一步。然而要实现交通量符合实际地分配到道路网络中并非易事,目前许多交通分配模型是建立在Wardrop第一原理概念上的,最具代表性的模型是1956年著名学者Beckmann提出了描述Wardrop第一原理的数学规划模型 [1] 。Beckmann模型涉及维数多,且是一个非线性规划模型,在许多交通分配问题中都有广泛的应用 [2] - [4] ,因此求解该模型具有重要的理论和实际意义。

1975年LeBlanc等学者将Frank-Wolfe算法用于求解Beckmann模型,简称W-F算法,该方法是用线性规划逐步逼近非线性的方法,重复迭代直到找到最优解为止 [5] 。但是该算法具有一定的局限性,如在一定的精度下得不到较理想的最优解。

本文中我们运用数学机械化的思想把Beckmann优化模型等价地转化为求解多项式组零点集问题 [6] - [10] 。对后者用吴方法处理获得特征列集的零点集。然后由特征列集的三角化特点,得到其零点集,进而获得最全局最优解。

吴方法是由我国著名数学家吴文俊在20世纪70年代末提出,其在处理多项式系统的结构和零点方面有着很大的优势,在几何定理的机器证明、代数方程组的求解、有理参数曲线和曲面的隐式化等有非常广泛的应用。本文是吴方法在交通问题中的首次应用尝试。

2. 理论与方法

2.1. 问题描述与转化

记自变量,设是多项式函数,并记多项式组,用中某开域。本模板仅针对采用A4纸型的论文版式。

本文讨论如下一般优化问题:

问题Q:求在限制条件下在开域上的最优值(最大或最小),并记所有极值点集合为

为了应用吴方法,下面把上述优化问题转化为多项式零点集的问题。为此引进新的变量,并令,记多项式组、开域。在以上记号下,把上述问题 转化为求解如下问题:

问题:求在限制条件下在上的最优值(最大或最小),并记所有极值点集为

2.2. 两个问题的等价性

由文献 [2] 中的引理5.5.22可知,即若问题有最优值,则问题也有最优值,且两最优值相同,反之亦然。

问题的优点在于目标函数进入多项式组中,从而在基本代数序下可以消元,直至用尽可能少的变量表示,从而易于分析求解其最优解。因此,本文下面集中讨论问题

2.3. 求解问题Q+的特征列集方法

由文献 [6] 中的零点分解定理知,用吴方法在有限步内可得的有限个特征列集,使得

(*)

其中Zero(PS)表示多项式组PS的零点集,中多项式的初式与隔离子的乘积。

由文 [2] 中开区域上的有限核定理(定理5.5.23)可得有限核使得,其中由如下步骤确定:

的第一多项式的主变元不是,则空集。

(b) 若的第一多项式的主变元是,但无实数解,则空集。

(c) 若的第一多项式的主变元是有实数解,但不能扩充到上的实解,则空集。

(d) 若的第一多项式的主变元是有实数解,且可扩充到上的实解,则的这些实解的集合。

称为的有限分核。根据有限核定理 [2] 知,若问题有最优值(最大或最小),则这一最优值等于的最优值。

由以上讨论,我们获得求解优化问题的一个基于吴方法的特征列集算法(见(*)):

输入:优化问题Q。

输出:优化问题Q的最优解。

Step 1:构造,并计算的特征列的解(*);

Step 2:用上面的(a)-(d)确定

Step 3:计算的最优值。

3. 基于吴方法的求解Beckmann模型算法及其应用

3.1. Beckmann均衡分配模型 [1]

Beckmann均衡分配模型是Wardrop第一原理的数学描述,是研究交通分配问题的基础,具体的模型表达式如下

表示路段a上的交通量,它组成的向量为表示路段a的交通阻抗;表示路a的以流量为自变量的阻抗函数;表示点对间的第k条路径的交通量,其向量为是路段-径路相关变量,即0-1变量,如果路段a属于从出发地r目的地为s的OD间第k条径路,则,否则表示点对之间的所有径路集合;表示点对之间的交通量。

3.2. 算法步骤

基于第2节的理论,下面具体给出本文中基于吴方法求解交通中Beckmann模型零点的算法步骤:

Step 1:将模型转化为具体的多项式方程组

模型中变量为,常量为,因此可具体写为如下的形式:

具体问题中函数为包含所有变量的函数,且都为非线性函数。

Step 2:添加极值变量构造约束条件的多项式组为如下:

Step 3:给定序

运用计算机代数软件Mathematica求出的特征列,并运用以上(a)~(d)各情形对特征列集分析,并求出其有限核。经分析比较所有得到的零点即可得到和相应的变元的解。

例1

考虑文献 [5] 中的算例。如下图1所示实例中有两个起点①②和一个终点⑤,各路段阻抗函数为:。PA流量为:

本算例中每一个OD对中有两条路径,共有四条路径,所有路径对应的路段见表1

Figure 1. Schematic diagram of calculation example

图1. 算例示意图

Table 1. Path link correspondence

表1. 路径-路段对应关系

将各个路径的流量转换为路段流量,并带入Beckmann模型,整理得到下式

添加变量r0,并令,设给定序为,由上节算法的step3,并用Mathematica软件可求得多项式集的升列为:

分析第一个式子,符合2.2中的第(d)中情形,可变形为

知当时,可取得最小值,最小值为29.45。

,可得一组自由解,知方程有无穷多组解

时,令,可得方程的一组解为:

,可得方程的一组解为:

,可得方程的一组解为:

将上述得到的几种径流量转换为各个路段的流量,均可得到;计算各个OD对之间的行驶时间见表2

表2可知网络达到平衡时,每一个OD对之间的行驶时间最小且相等,即验证了该方法的有效性。

例2

本文以文献 [11] 中西安湘子庙历史街区慢行网络为例说明该算法的有效性。网络的拓扑结构见图2。各个路段属性数据见表3

算例中有四个OD对,每个OD对的流量分别为;其中OD对1-5有四条路径,其他OD对只有一条路径,所有路径对应的路段见表4

将各个路径的流量转换为路段流量,结合表2中路段费用函数带入2.1中Beckmann模型,整理得到下式:

Table 2. Balance state each path travel schedule

表2. 平衡状态各路径行驶时间表

Table 3. Link attribute

表3. 路段属性表

Table 4. Path link correspondence

表4. 路径-路段对应关系

Figure 2. Schematic diagram of road network

图2. 路网示意图

添加变量r0,设r0即为要求的最小值,令,设给定序为,由step3用Mathematica软件可求得多项式集的升列为:

分析以上升列可得方程的一组解为:

其中,

所以平衡后各个路段的流量为:。可见用吴方法可以有效求解Beckmann模型。

4. 结论

多项式方程见之于许多基础和应用学科,因而处理多项式系统的结构和零点的特征列方法有着非常广泛的应用。本文将吴方法应用在求解Beckmann交通平衡分配模型中,采用的是符号计算,依据计算机代数与代数几何的理论,相比于传统的W-F方法和智能优化方法,该方法可以得到模型的精确解,并在具体实例中得到了验证,从而给出了用符号计算和吴方法探索交通问题的一个新的思路。

基金项目

国家自然科学基金委员会资助项目(11571008)。

文章引用

战秋艳,朝鲁,魏贤鹏. 吴方法在求解Beckmann交通平衡分配模型中的应用
On Application of Wu’s Method in Solving the Beckmann Traffic Assignment Model[J]. 应用数学进展, 2016, 05(03): 327-335. http://dx.doi.org/10.12677/AAM.2016.53041

参考文献 (References)

  1. 1. 刘灿齐. 现代交通规划学[M]. 北京: 人民交通出版社, 2001, 206-244.

  2. 2. 陆化普, 孙煦, 吴娟. 公交专用道优化设计的双层规划模型[J]. 中国路学报, 2015, 28(2): 88-93.

  3. 3. 刘强, 陆化普, 王庆云.区域综合交通枢纽布局双层规划模型[J]. 东南大学学报(自然科学版), 2010,40(6): 1358- 1363.

  4. 4. 杨明, 宫熙桢. 常规公交线网的低碳双层优化模型[J]. 公路交通科技, 2015, 32(11): 143-147.

  5. 5. 邵春福. 交通规划原理[M]. 北京: 中国铁道出版社, 2006, 172-180.

  6. 6. 吴文俊. 数学机械化[M]. 北京: 科学出版社, 2002, 210-218.

  7. 7. 吴天娇. 关于吴方法在双层规划中的一个应用[J]. 数学物理学报, 2007, 27(A)1: 176-183.

  8. 8. Wu, W. (1994) A Finiteness Theorem about Problems about Problems Involving Inequalities. Sys Sci Math Scis, 7, 193-200.

  9. 9. 王东明, 夏壁灿, 李子明. 计算机代数[M]. 北京: 清华大学出版社, 2007: 133-150.

  10. 10. 王东明, 牟晨琪, 李晓亮, 杨静, 金萌, 黄艳丽. 多项式代数[M]. 北京: 高等教育出版社, 2010, 66-87.

  11. 11. 王秋平, 刘星明, 魏华. 历史街区慢行交通连续网络设计鲁棒优化模型[J]. 长安大学学报(自然科学版), 2015, 35(5): 112-116.

期刊菜单