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)。
参考文献