07年B题最优公交线路问题(8)

时间的函数要考虑步行对时间的影响

T??(aj?1)?3?(?dn?1)?2.5??kY?T1?T2?T3?T4

j?1i?1395739由于改变一种交通方式，换乘方式就是包括了步行，地铁，汽车三种方式

Z??Xi??Sm??Yi?1

i?1i?15202 其余约束条件均与上题类似

minM???f???T???Z5202??f???iXi???mSmi?1m?1?395739??T??(aj?1)?3?(?dn?1)?2.5??kY?T1?T2?T3?T4j?1i?1?5202??4Z??Xi??Sm??Yi?1i?1i?1?520?520?当?ajXi?1时1??ajXi?2i?0?i?0?3957?a?X?2ji??j?1?2??当dn＝1时1??Sm?dn?2m?0??39??Sm?dn?2?n?1??kY?A? ?Z?B?f?C?

（3）算法的实现

由于经典的最短路算法在考虑进步行情况后，运算复杂程度太高。我们考虑到人们在选择出行路线时，最像蚂蚁选择食物路线，并不知道自己确切的选择，只能大致选择一个路线，为此我们引入启发式算法－蚁群算法，求出近似最优解。 求解算法设计。

在一个城市中，所有站点是通过公交线路联结在一起的，可以将整个城市的所有站点视作是一个连通图上的点。从任一站点出发，经过有限次转车一定可以到达另一个站点。