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

（2） 路线类型 S1557-S0481 时间 转乘次数 费用 S1557-L363(或时间最短 L084)-S1919-L189-S3186-L317-S0902-L399 3 4 12-S0481 S1557-L363(或费用最小 106 2 3 L084)-S1919-L189-S3186-L460-S0481 时间S1557-L363(或106 2 3 转乘最最短 L084)-S1919-L189-S3186-L460-S0481 少 费用S1557-L363(或106 2 3 最小 L084)-S1919-L189-S3186-L460-S0481 时间S1557-L363(或106 2 3 最多转最短 L084)-S1919-L189-S3186-L460-S0481 乘两次 费用S1557-L363(或106 2 3 最小 L084)-S1919-L189-S3186-L460-S0481 评价说明：推荐选择路线S1557-L363(或L084)-S1919-L189-S3186-L460-S0481，因为费用和专程次数少，同时时间只比时间最短的路线多7%

（3） 转乘费路线类型 S0971-S0481 时间 次用 数 S0971-L013-S1609-L448-S2113-L002-S时间最短 105 3 4 1321-L469-S0485 费用最小 S0971-L013-S2184-L417-S0485 128 1 3 时间S0971-L013-S2184-L417-S0485 128 1 3 最短 转乘最少 费用S0971-L013-S2184-L417-S0485 128 1 3 最小 时间S0971-L013-S1609-L140-S2654-L469-S106 2 3 最多转乘最短 0485 两次 费用S0971-L013-S1609-L140-S2654-L469-S106 2 3 最小 0485 评价说明：推荐选择线路S0971-L013-S1609-L140-S2654-L469-S0485，相对时间最短的线路来说，时间只多了1分钟，而转乘次数和费用都比少。相对转车次数最短的线路，只多转了一次车，却节约了22分钟。

11

（4） 路线类型 时间最短 S0008-S0073 S0008-L198-S1691-L476-S2085-L107-S0483-L328-S0525-L103-S0073 S0008-L159-S0291-L085-S0073 时转乘费间 次数 用 59 4 5 费用最小 83 1 2 时间S0008-L159-S0291-L085-S0073 83 1 2 转乘最最短 少 费用S0008-L159-S0291-L085-S0073 83 1 2 最小 时间S0008-L043-S1383-L296-S2184-L345-S00767 2 3 最多转最短 3 乘两次 费用S0008-L159-S0291-L085-S0073 83 1 2 最小 评价说明：推荐选择线路S0008-L043-S1383-L296-S2184-L345-S0073，因为相对时间最短的线路来说，只增加8分钟，却少转了2次车和节约了2元，和费用最小的相比，多乘了1塘车，却16分钟

（5） 转乘费路线类型 S0148-S0485 时间 次用 数 S0148-L308-S3604-L354-S2361-L156-S时间最短 102 3 4 2210-L417-S0485 S0148-L308-S0036-L156-S2210-L417-S费用最小 106 2 3 0485 时间S0148-L308-S0036-L156-S2210-L417-S106 2 3 最短 0485 转乘最少 费用S0148-L308-S0036-L156-S2210-L417-S106 2 3 最小 0485 时间S0148-L308-S0036-L156-S2210-L417-S106 2 3 作多转乘最短 0485 两次 费用S0148-L308-S0036-L156-S2210-L417-S106 2 3 最小 0485 评价说明：推荐选择线路：S0148-L308-S0036-L156-S2210-L417-S0485，相比时间最短的路线，只多了4分钟，却少转了一次车，方便。

12

（6） 路线类型 时间最短 S0087-S3676 S0087-L021-S0088-L231-S0427-L097-S3676 S0087-L454-S3496-L209-S3676 时间 46 转乘费次数 用 2 3 费用最小 65 1 2 时间最S0087-L454-S3496-L209-S3676 65 1 2 短 转乘最少 费用最S0087-L454-S3496-L209-S3676 65 1 2 小 时间最S0087-L021-S0088-L231-S0427-L046 2 3 97-S3676 最多转乘短 两次 费用最S0087-L021-S0088-L231-S0427-L046 2 3 小 97-S3676 评价说明：推荐选择路线：S0087-L021-S0088-L231-S0427-L097-S3676，相比费用最小的路线，只多转了一次车，多花了1元钱，却节约了19分钟。

（二）问题二：同时考虑公交车站和地铁站的情况

2.1 模型的建立

（1）模型的符号说明

Tr：在公交线上所耗费的时间与在地铁线路上所耗费的时间之和 Tc：所有换乘时间之和 T1：地铁换公交的时间之和

T2：公交换地铁所用的时间之和 T3：地铁换地铁所用的时间之和 T4：公交换公交所用的时间之和

Sm：表示所选择路线中是否包含第i条地铁线路

dn：表示所选择路线中是否包含第j个地铁站点

?i：表示第i条公交线路上的费用

13

?i：表示第i条公交线路上所用的时间

?m：表示第m条地铁线路上的费用 ?m：表示第m条地铁线路上所用的时间

（2）目标函数

当目标函数为所用时间最小：要求路上所花费的总时间Tr与总转车时间Tc之和最小。

minT?Tr?Tc

3957Tr??(aj?1j?1)?3?(?dn?1)?2.5

i?139Tc?T1?T2?T3?T4

当目标函数为所用时间最小：转车次数为公交车转车次数与地铁转车次数之和。

minZ?(?Xi?1)??Sm?1

i?1i?15202当目标为费用最小：即所有选取的公交线路和地铁线路上的费用之和

??i?1520iXi???mSm为最小。目标函数为：

m?12minf?

??i?1520iXi???mTm

m?12??Xii?1520i表示在坐公交车的费用 ??mSm表示坐地铁所的费用

m?12

（3） 约束条件

1当ajXi?1，既aj?Xi?1

表示最优路线同时选取了第i条线路和第j个站点

当ajXi?0，表示最优路线没有同时选取了第i条线路和第j个站点

14

2?aXji?0520i表示最佳路线中经过第j个站点处所选取的路线总数

520i?0当aj?1时，表示选取该站点，这时只能选择继续前进和换乘，当?ajXi?1时表示继续前进，当?ajXi?2时表示在第j个站点换乘。但是只可能有这两种情

i?0520况的存在，得到约束条件为：

1??ajXi?2

i?05203当Xi?1，?aj?Xi表示所选路线中第i条线路所经过的所有站点数。在选

j?13957取的任何一条线路上，都必须坐一站路以上，即必须有两个站点。故约束条件为：

3957j?1?aj?Xi?2

同理，可得地铁站点的两个约束分别为：

当dn＝1时1??Sm?dn?2

m?02?Sn?139m?dn?2

（4）得到最终模型为：

15