运筹学课程设计.doc

交通流均衡问题一 题目分析1.1问题某地有如图1所示的一个公路网，每天上班时间有6千辆小汽车要从居民区A前往居民区D，经过长期观察，我们得到了图中5条道路上每辆汽车的品均行驶时间和汽车流量之间的关系，如表1-1所示，那么，长期来看，这些汽车将如何在每条道路上分布？B DA C 居民区 工作区 图1 一个公路网示意图 表1-1 平均行驶时间和汽车流量之间的关系道路ABACBCBDCD行驶时间/min流量220521252202流量330531353303流量440541454401.2问题分析 这个问题我们可以想象有一个协调组，实际上所谓的协调者可以认为是交通流规律，交通流规律就是每辆汽车都将选择使自己从A到D运行时间最少的路线，其必然结果是无论走那条路线从A到D，最终花费的时间应该是一样的（否则，花费时间较长的那条线路上的部分汽车就会改变自己的路线，以缩短自己的行驶时间）. 也就是说，长期来看，这些汽车在每条道路上的分布将达到均衡状态（所谓均衡状态，这里的含义就是每辆汽车都不能仅仅通过自身独自改变道路节省其行驶时间），在这种想法下，我们来建立线性规划模型。二 总体设计 交通流的规律要求所有道路上的流量达到均衡，如果车流量是一辆车一辆车增加的，那么在每条道路上车流量少于2时，车流量会有一个分布规律；当某路道路上流量正好超过2时，新加入的一辆车需要选择使自己堵塞时间最短的道路，这就提示我们吧同一条道路上的流量分布分解成不同性质的三个部分，也就是说，我们用Y(AB)表示道路AB上的总的流量，并进一步吧他分解成三个部分；(1) 道路AB上的流量不超过2时的流量，用X(2,AB)表示；(2) 道路AB上的流量超过2但不超过3时，超过2的流量部分用X(3,AB)表示；(3) 道路AB上的流量超过3但不超过4时，超过3的流量部分用X(4,AB)表示；依此类推，对道路AC,BC,BD,CD上同理可以定义类似的决策变量。因此，问题中总共有20个决策变量Y(j)和X(i,j)（I=2,3,4; j=AB,AC,BC,BD,CD）。问题的目标应当是使总的堵塞时间最少。用T(i,j)表示流量X(i,j)对应的堵塞时间（即表1-1的数据，是对每辆车而言的），我们看看用 T(i,j)X(i,j)作为总堵塞时间是否合适，很容易理解；后面加入道路的车辆可能又会造成前面进入道路的车辆的进一步堵塞，如流量为3时，原先流量为2的车辆实际上也只能按T(3,j)的时间通过，而不是T(2,j)，也就是说，T(i,j)X(i,j)并不是总的堵塞时间，但是我们也可以发现，T(i,j)关于I单调增加的，即不断增加的车流只会使以前的堵塞加剧而不可能使以前的堵塞减缓，所以，关于决策变量X(i,j)而言，T(i,j)X(i,j)与我们希望优化的目标的单调性是一致的。因此，可以用T(i,j)X(i,j)作为目标函数进行优化。约束条件有三类：(1) 每条道路上的总流量Y等于该道路上的分流量X的和；(2) 道路交汇初A,B,C,D(一般称为节点)的流量守恒（即流入量等于流出量）；(3) 决策变量的上限限制，如X(2,AB)2,X(3,AB)1,X(4,AB)1等。三 程序这个问题可以用LINDO软件求解，不过这里用LINGO软件求解更方便些，LINGO模型如下：SETS:ROAD/AB,AC,BC,BD,CD/:Y;CAR/2,3,4/;LINK(CAR,ROAD):T,X;ENDSETSDATA:!行驶时间;T=20,52,12,52,20 30,53,13,53,30 40,54,14,54,40;ENDDATAOBJMIN=SUM(LINK:T*X);!目标函数;!四个节点的流量守恒条件;NODE_AY(INDEX(AB)+Y(INDEX(AC)=6;NODE_BY(INDEX(AB)=Y(INDEX(BC)+Y(INDEX(BD);NODE_CY(INDEX(AC)+Y(INDEX(BC)=Y(INDEX(CD);NODE_DY(INDEX(BD)+Y(INDEX(CD)=6;!每条道路上的总流量Y等于该道路上的分流量X的和;FOR(ROAD(I): ROAD_LIMSUM(CAR(J):X(J,I)=Y(I);!每条道路的分流量X的上下界设定;FOR(LINK(I,J)|I#EQ#1:BND(0,X(I,J),2);FOR(LINK(I,J)|I#GT#1:BND(0,X(I,J),1);END可以指出的是，上面四个节点的流量守恒条件条件中，其实只有3个是独立的（也就是说，第四个总可以从其他3个方程推导出来），因此从中去掉任何一个都不会影响到计算结果。求解这个模型，得到如下解答（其中略去已知参数T的显示结果）：Global optimal solution found. Objective value: 452.0000 Total solver iterations: 7 Model Title: 交通流均衡 Variable Value Reduced Cost Y( AB) 4.000000 0.000000 Y( AC) 2.000000 0.000000 Y( BC) 2.000000 0.000000 Y( BD) 2.000000 0.000000 Y( CD) 4.000000 0.000000 T( 2, AB) 20.00000 0.000000 T( 2, AC) 52.00000 0.000000 T( 2, BC) 12.00000 0.000000 T( 2, BD) 52.00000 0.000000 T( 2, CD) 20.00000 0.000000 T( 3, AB) 30.00000 0.000000 T( 3, AC) 53.00000 0.000000 T( 3, BC) 13.00000 0.000000 T( 3, BD) 53.00000 0.000000 T( 3, CD) 30.00000 0.000000 T( 4, AB) 40.00000 0.000000 T( 4, AC) 54.00000 0.000000 T( 4, BC) 14.00000 0.000000 T( 4, BD) 54.00000 0.000000 T( 4, CD) 40.00000 0.000000 X( 2, AB) 2.000000 -20.00000 X( 2, AC) 2.000000 0.000000 X( 2, BC) 2.000000 0.000000 X( 2, BD) 2.000000 0.000000 X( 2, CD) 2.000000 -20.00000 X( 3, AB) 1.000000 -10.00000 X( 3, AC) 0.000000 1.000000 X( 3, BC) 0.000000 1.000000 X( 3, BD) 0.000000 1.000000 X( 3, CD) 1.000000 -10.00000 X( 4, AB) 1.000000 0.000000 X( 4, AC) 0.000000 2.000000 X( 4, BC) 0.000000 2.000000 X( 4, BD) 0.000000 2.000000 X( 4, CD) 1.000000 0.000000 Row Slack or Surplus Dual Price OBJ 452.0000 -1.000000 NODE_A 0.000000 -40.00000 NODE_B 0.000000 0.000000 NODE_C 0.000000 -12.00000 NODE_D 0.000000 -52.00000 ROAD_LIM( AB) 0.000000 -40.00000 ROAD_LIM( AC) 0.000000 -52.00000 ROAD_LIM( BC) 0.000000 -12.00000 ROAD_LIM( BD) 0.000000 -52.00000 ROAD_LIM( CD) 0.000000 -40.00000四 结果分析 上面的结果表明，均衡时道路AB,AC,BC,BD,CD的流量分别是4，2，2，2，4（千辆）车，但是要注意，正如我们建立目标函数时所讨论过的，这时得到的目标函数值452并不是真正的总运行和堵塞时间，而是一个用来表示目标函数去世的虚拟的量，没有太多实际物理意义。事实上，可以求出这时的真正运行时间是：每辆车通过AB,AC,BC,BD,CD道路分别需要40，52，12，52，40（min），也就是在图中三条路线ABD,ACD,ABCD上都需要92min，所以这也说明交通流确实达到了均衡。于是，均衡时真正的总运行时间应该是6*92=552（千辆车*min）。五 模型讨论不过，仔细想想就会发现，上面的解并不是最优解，即均衡解并不一定是最优的流量分配方案。为了求出使所有汽车的总运行时间最小的交通流，应该如何做呢？也就是说，这相当于假设有一个权威的机构来统筹安排，最优地分配这些交通流，而不是像求均衡解时那样认为每个个体（每辆车）都可以自己选择道路，自然达到平衡状态。为了进行统筹规划，我们需要吧新增的流量X(i,j)(i=2,3,4;j=AB,AC,BC,BD,CD)造成的实际堵塞时间计算出来（仍按每辆车计算），而不是像上面那样不考虑对原有车流造成的堵塞效应。以道路AB为例：（1） 当流量为2千辆时，每辆车的通过时间为20min，所以总通过实践是40（千辆车*min）；（2） 当流量增加一个单位（本题中一个单位就是1千辆）达到3千辆时，每辆车的通过时间为30min，所以总通过时间是90（千辆车*min）；（3） 当流量再增加一个单位达到4千辆时，每辆车的通过时间为40min，所以总通过时间是160（千辆车*min）；由此可见，流量超过2而不超过3时，单位流量的增加导致的总通过时间的变化为90-40=50（千辆车*min）；流量超过3而不超过4时，单位流量的增加导致的总通过时间的变化为160-90=70（千辆车*min）；类似地，对所有的道路，都可以得到单位流量的增加导致总行驶时间的增量和汽车流量之间的关系（参见表1-2）。表1-2 平均行驶时间和汽车流量之间的关系道路ABACBCBDCD总行驶时间的增量/（千辆车*min）流量220521252202流量350531555503流量47057175770用表1-2中的总行驶时间的增量数据代替前面模型的每辆车的行驶时间市局T(i,j)，模型的其他部分完全不用不变，重新求解LINGO模型，可以得到如下结果（其中略去了已知参数T的显示结果）： Global optimal solution found. Objective value: 498.0000 Total solver iterations: 10 Model Title: 交通流均衡 Variable Value Reduced Cost Y( AB) 3.000000 0.000000 Y( AC) 3.000000 0.000000 Y( BC) 0.000000 0.000000 Y( BD) 3.000000 0.000000 Y( CD) 3.000000 0.000000 T( 2, AB) 20.00000 0.000000 T( 2, AC) 52.00000 0.000000 T( 2, BC) 12.00000 0.000000 T( 2, BD) 52.00000 0.000000 T( 2, CD) 20.00000 0.000000 T( 3, AB) 50.00000 0.000000 T( 3, AC) 55.00000 0.000000 T( 3, BC) 15.00000 0.000000 T( 3, BD) 55.00000 0.000000 T( 3, CD) 50.00000 0.000000 T( 4, AB) 70.00000 0.000000 T( 4, AC) 57.00000 0.000000 T( 4, BC) 17.00000 0.000000 T( 4, BD) 57.00000 0.000000 T( 4, CD) 70.00000 0.000000 X( 2, AB) 2.000000 -48.00000 X( 2, AC) 2.000000 -3.000000 X( 2, BC) 0.000000 25.00000 X( 2, BD) 2.000000 -5.000000 X( 2, CD) 2.000000 -50.00000 X( 3, AB) 1.000000 -18.00000 X( 3, AC) 1.000000 0.000000 X( 3, BC) 0.000000 28.00000 X( 3, BD) 1.000000 -2.000000 X( 3, CD) 1.000000 -20.00000 X( 4, AB) 0.000000 2.000000 X( 4, AC) 0.000000 2.000000 X( 4, BC) 0.000000 30.00000 X( 4, BD) 0.000000 0.000000 X( 4, CD) 0.000000 0.000000 也就是说，最优的车流分配方式是：道路AB,AC,BD,CD的流量都是3千辆车，而道路BC上没有车流；总（加权）运行时间为498（千辆车*min），优于均衡时的结果552（千辆车*min）。此时，每辆车的运行时间=498/6=83（min），少于均衡时的92min。当然，这个最优解必须强