谌永荣

(中南民族大学 数学与统计学学院，武汉 430074)

一般路网中通常假定各路段的行驶费用只与本路段的流量有关，且关于路段流量是连续可微的，这在很多情况下是合理的，称该网络为对称网络. 此时，网络设计问题可建成一个二层规划模型[1].如果各路段的行驶费用不仅与自身的流量有关，还与其他路段上的流量有关，而且路段费用向量关于路段流量变量的雅克比矩阵是非对称的，称该网络为非对称网络.由于社会经济快速发展，车流量与日俱增，造成城市交通越来越拥挤，车辆的行驶费用不仅与自身的行驶路段流量有关，且与网络的其他路段流量有关，因而实际的交通网络多为非对称.这时网络设计问题中下层的用户平衡就不能写成一个数学规划模型，大部分用变分不等式和非线性互补问题来描述[2].本文研究带容量限制的非对称网络设计问题[3]，上层同时考虑了增加车道后对交通状况的改善情况和投资费用问题[4],下层问题则是一个变分不等式.

1 容量限制网络设计模型

网络设计模型：

上层

下层

求向量(x*,q*)∈Ω，满足对任意的(x,q)∈Ω都有：

t(x*)T(x-x*)-D-1(q*)T(q-q*)≥0,

此时Ω={(x,q)|x=Δf,Λf=q,x≤c,f≥0,q≥0}.

2 模型的求解算法

2.1 求解下层问题的算法

本文的下层是一个带容量限制的变分不等式问题，采用仿真算法[5]求解.

2.2 整体算法的迭代步骤

模型中上层问题采用遗传算法[6]求解.

整体算法迭代如下.

步骤1：确定遗传算法的编码及解码方法，随机产生一个由M个染色体构成的初始群体P(0)，置t:=0;

步骤2: 将当前群体P(t)中每个染色体转换为对应的Y，对每个Y用上述仿真算法求解下层的最优解;

步骤3：将步骤2中得到的最优解计算上层问题的目标函数值并将它作为各个染色体的适应度值来评价所有染色体;

步骤5：对当前群体P(t)以交叉概率pc进行单点交叉运算;

步骤6：对当前群体P(t)以变异概率pm进行均匀变异运算，并在交叉和变异过程中采用保留最佳个体策略，P(t)经过3种遗传操作运算后得到下一代群体P(t+1);

步骤7：若t≤T，则t:=t+1，转步骤2；否则算法停止，输出最优解.

3 计算实例

图1为一个9节点的道路网，其中(2，5)和(5，8)是对原有路段改造扩容.

各备选路段对应的扩容量和投资额用下列矩阵表示(单位：103元)：

图1 道路网络 Fig.1 Road network

路段a1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16t0a 2 2 3 3 1 1 2 2 21212122ca4545 0 03530303536 40 35 35 35 30 40 40

表2 算法结果Tab.2 Results of the algorithm

4 结束语

本文讨论了带容量限制的非对称路网设计问题，给出了问题的模型和算法，并用一个小型的路网来检验算法的可行性，从结果可知，θ越大，表明决策者越看重投资费用，路网投资费用随着θ的增大而减小，与表2计算结果是一致的，表明该算法有效.