一、问题的提出某区域道路网络如图所示，每条道路等级完全相同，某时间段内，有N 辆车要从节点1出发，目的地是节点0（假设该时间段内，路网中没有其它车辆）。

在该时间段内，道路截面经过的车辆数越多，车辆在该路段行驶的速度就越慢。

（1）确定有效的行驶路径及其算法；（2）确定每条路径上的通过的车辆数，使N 辆车从节点1到节点0的总行驶时间最小；（3）N=10000，请给出具体的计算结果。

注：横向路段长度是纵向路段长度的2倍。

16599328074二、问题的分析问题一：确定有效的行驶路径及算法题目中要求的有效地行驶路径就是可达路径，从节点1出发经过一系列节点最终到达节点0，在11个节点中我们可以任意选择若干个相邻的节点使车辆从节点1出发，到达节点0。

其中要求不可以走已经走过的路径，也不可以走闭合回路。

在计算有效路径时，我们可以利用可达矩阵和Lingo 程序来实现。

问题二：确定每条路径上的通过的车辆数，使N 辆车从节点1到节点0的总行驶时间最小引入各条路径车辆数比例变量M i ，可以得到各路段内动态变化的车流量，假设一个速度与车流量关系的函数，再利用速度与路程的关系可以求出时间矩阵。

运用Lingo 程序求解出最小的总行驶时间。

问题三：N=10000，请给出具体的计算结果。

根据引入的各条路经车辆数比例变量以及最小的总行驶时间，带入N=10000算出最小的总行驶时间。

三、问题的假设1.所有车辆同时出发，不考虑出发时的先后顺序；2.所有道路无红绿灯，在结点处车辆不存在等待现象；3.无交通事故；4.不走回头路，也不走闭合回路；5.各路段内的车辆都匀速行驶。

四、定义符号说明N:表示车辆总数；W:可达矩阵，W ij表示车辆可以从i节点到达j节点;X:有效路径矩阵;M i:各条有效路径内截面车辆数的比例变量；B:第i条有效路径上车辆数的比例；i：表示所有有效路径上从i节点到达j节点车辆和的比例Cij表示从i节点到j节点车辆的速度Vij：K:表示V与M的比例系数，是常数；i: 表示从i节点到j节点路段的权值；Sij: 表示从i节点到j节点车辆的行驶时间;TijminT:表示N辆车从节点1到节点n(节点0)的最小总行驶时间五．模型的建立和求解问题一：设n=11 ，节点n就是目的地节点0，以下约束针对任一有效路径。

1，节点i与节点j连通x ij=0，节点i与节点j不连通目标函数为有效路径，即从节点1出发到达节点11所经过的路段和最多为10条，故目标函数为约束条件：(1)任一有效路径均从起始节点1开始出发，且恰有一条路径出去，表达为（2）任一有效路径均到终止节点n(节点0)结束，且恰有一条路径到达，有（3）对除起始节点1和目标节点n（节点0）之外，其他点进入和出去的路径一样多（也可以都为0），车辆从k节点进入到i节点有多少辆就要从i节点出去到其他节点j多少辆，表示的是车辆在节点处不存在等待，进来多少就要出去多少，并且有一条路径，表达为(4)对于不通的路径不取，约束为x ij≤w ij, i,j=2,3,…,n(5) 要求不出现圈，就是车辆在行驶过程中不走一个闭合的回路，从某一个节点出发不回到该节点处，约束为【1】u i-u j+nx ij≤n-1， i,j=2,3,…,n该约束的解释为：①i与j不会构成回路，若构成回路有x ij=1,x ji=1,则u i-u j ≤-1,u j-u i≤-1，从而有0≤-2，导致矛盾；②i，j与k不会构成回路，有x ij=1,x jk=1,x ki=1,则u i-u j≤-1,u j-u k≤-1,u k-u i≤-1,从而有0≤-3，导致矛盾。

其他情况以此类推。

总模型为u i-u j+nx ij≤n-1， i,j=2,3,…,nx ij≤w ij, i,j=2,3,…,nx ij=o或1该问题求解用Lingo9程序实现，具体算法及结果详见第八页的算法的设计和实现中问题一的计算.问题二：(1)引入比例变量Mi,Mi表示第i条有效路径上通过的车辆数比例，并且满足：(2)Ai是由问题一得出的各个有效路径，Ai乘以通过的车辆数比例我们可以得到各个有效路径上的车辆数比例Bi= Mi*Ai ，i=1,2 (23)(3)对Bi求和得C矩阵，C ij表示各有效路径从节点i到节点j路段的车流量比例之和由于矩阵C中元素过长，无法用矩阵形式表示，现将元素表示为C(1,2)= M1+M2+M3+M4+M5+M6+M7+M8+M9+M10+M11+M12C(1,8)=M13+M14+M15+M16+M17+M18+M19+M20+M21+M22+M23C(2,3)=M1+M2+M3+M4+M13+M14+M15+M16+M21C(2,5)=M7+M8+M9+M10+M11+M12C(3,4)=M1+M2+M3+M7+M13+M14+M17+M21+M22C(3,6)= M4+M5+M6+M15+M16C(4,7)= M1+M2+M3+M7+M10+M13+M14+M17+M21+M22C(5,2)=M13+M14+M15+M16+M21C(5,6)=M7+M8+M9+M17+M18+M19C(5,9)=M1+M2+M4+M10+M11+M12C(6,3)=M7+M10+M17+M22C(6,5)=M4+M10+M21C(6,7)=M5+M8+M11+M15+M18+M23C(6,10)=M26+M6+M9+M13+M16+M19C(7,6)=M1+M2+M13C(7,11)=M3+M5+M7+M8+M11+M14+M15+M17+M18+M21+M22+M23C(8,9)= M13+M14+M15+M16+M17+M18+M19+M20+M21+M22+M23C(9,5)= M13+M14+M15+M16+M17+M18+M19C(9,10)=M1+M4+M10+M11+M12+M20+M21+M22+M23C(10,6)= M10+M11+M21+M22+M23C(10,11)=M1+M2+M4+M6+M9+M12+M13+M16+M19+M20其余元素均为零(4)引入车辆行驶速度与截面经过的车辆数的关系：V ij=K / (C ij*N)注：为了计算方便我们在此引入了简单的反比关系，但是标准正太分布函数的模型更适合描述这种关系，详解见第14页的模型的优缺点及改进。

由于矩阵V中元素过长，无法用矩阵形式表示，现将元素表示为V(1,2)=K / [( M1+M2+M3+M4+M5+M6+M7+M8+M9+M10+M11+M12)*N]V(1,8)=K / [ (M13+M14+M15+M16+M17+M18+M19+M20+M21+M22+M23) *N]V(2,3)= K / [ (M1+M2+M3+M4+M13+M14+M15+M16+M21) *N]V(2,5)= K / [ (M7+M8+M9+M10+M11+M12) *N]V(3,4)= K / [ (M1+M2+M3+M7+M13+M14+M17+M21+M22) *N]V(3,6)= K / [ (M4+M5+M6+M15+M16) *N]V(4,7)= K / [ (M1+M2+M3+M7+M10+M13+M14+M17+M21+M22) *N]V(5,2)= K / [ (M13+M14+M15+M16+M21) *N]V(5,6)= K / [ (M7+M8+M9+M17+M18+M19) *N]V(5,9)= K / [ (M1+M2+M4+M10+M11+M12) *N]V(6,3)= K / [ (M7+M10+M17+M22) *N]V(6,5)= K / [ (M4+M10+M21) *N]V(6,7)= K / [ (M5+M8+M11+M15+M18+M23) *N]V(6,10)= K / [ (M26+M6+M9+M13+M16+M19) *N]V(7,6)= K / [ (M1+M2+M13) *N]V(7,11)= K / [ (M3+M5+M7+M8+M11+M14+M15+M17+M18+M21+M22+M23) *N]V(8,9)= K / [ (M13+M14+M15+M16+M17+M18+M19+M20+M21+M22+M23) *N]V(9,5)= K / [ (M13+M14+M15+M16+M17+M18+M19) *N]V(9,10)= K / [ (M1+M4+M10+M11+M12+M20+M21+M22+M23) *N]V(10,6)= K / [ (M10+M11+M21+M22+M23) *N]V(10,11)= K / [ (M1+M2+M4+M6+M9+M12+M13+M16+M19+M20) *N]其余元素均为零(5)可以得到时间矩阵T，T ij表示从节点i到节点j所需的时间变量T ij=S ij / V ij其中S矩阵如下：根据已知条件，取纵向路段长度为S，则横向路段长度为2S。

由于矩阵T中元素过长，无法用矩阵形式表示，现将元素表示为T(1,2)=2* S[( M1+M2+M3+M4+M5+M6+M7+M8+M9+M10+M11+M12)*N]/KT(1,8)=2*S[ (M13+M14+M15+M16+M17+M18+M19+M20+M21+M22+M23) *N]/KT(2,3)=2* S[ (M1+M2+M3+M4+M13+M14+M15+M16+M21) *N]/KT(2,5)= S[ (M7+M8+M9+M10+M11+M12) *N]/KT(3,4)= 2*S[ (M1+M2+M3+M7+M13+M14+M17+M21+M22) *N]/KT(3,6)= S[ (M4+M5+M6+M15+M16) *N]/KT(4,7)= S[ (M1+M2+M3+M7+M10+M13+M14+M17+M21+M22) *N]/KT(5,2)= S[ (M13+M14+M15+M16+M21) *N]/KT(5,6)=2* S[ (M7+M8+M9+M17+M18+M19) *N]/KT(5,9)= S[ (M1+M2+M4+M10+M11+M12) *N]/KT(6,3)= S[ (M7+M10+M17+M22) *N]/KT(6,5)= 2*S[ (M4+M10+M21) *N]/KT(6,7)=2* S[ (M5+M8+M11+M15+M18+M23) *N]/KT(6,10)= S[ (M26+M6+M9+M13+M16+M19) *N]/KT(7,6)=2* S[ (M1+M2+M13) *N]/KT(7,11)= S[ (M3+M5+M7+M8+M11+M14+M15+M17+M18+M21+M22+M23) *N]/KT(8,9)= 2*S[ (M13+M14+M15+M16+M17+M18+M19+M20+M21+M22+M23) *N]/KT(9,5)= S[ (M13+M14+M15+M16+M17+M18+M19) *N]/KT(9,10)=2* S[ (M1+M4+M10+M11+M12+M20+M21+M22+M23) *N]/KT(10,6)= S[ (M10+M11+M21+M22+M23) *N]/KT(10,11)= 2*S[ (M1+M2+M4+M6+M9+M12+M13+M16+M19+M20) *N]/K其余元素均为零目标函数是总车辆数为N时的最小的总行驶时间约束条件为总模型为该问题求解用Lingo9程序实现，具体算法及结果详见第八页的算法的设计和实现中问题二的计算。