问题的提出 2007 CUMCM B题乘公交,看奥运 给定若干条公交线路,以及在每条公交线 路中任意相邻的两站之间所花费的时间 并且给定乘客在任意站点换乘的耗时 要求给出任意两公汽站点之间线路选择问 题的一般数学模型与算法,求出最佳的公 交线路
问题的提出 • 2007CUMCM B题 乘公交,看奥运 • 给定若干条公交线路,以及在每条公交线 路中任意相邻的两站之间所花费的时间。 • 并且给定乘客在任意站点换乘的耗时 • 要求给出任意两公汽站点之间线路选择问 题的一般数学模型与算法,求出最佳的公 交线路
模型的假设 对”最优”的理解有三个具有代表性的指模 时间最短 花费最少 最方便(换乘次数最少) 不同的人群对最优的理解不同,需要根据实 际定义可以根据需要定义代价函数,三个指 标的权重不同,代价值也不同 以时间最短为例
模型的假设 • 对”最优”的理解有三个具有代表性的指标: • 时间最短 • 花费最少 • 最方便(换乘次数最少) • 不同的人群对最优的理解不同,需要根据实 际定义.可以根据需要定义代价函数,三个指 标的权重不同,代价值也不同。 • 以时间最短为例
模型的建立 G=(V, B 每个车站:G的顶点 每条公交线路相邻两点的连线:G的边 边的权重:耗费时间点的权重:换乘时间 并不是一个简单图,两点间可能有多条边 7 5 b(8)
模型的建立 • G=(V,E) • 每个车站:G的顶点 • 每条公交线路相邻两点的连线:G的边 • 边的权重:耗费时间 点的权重:换乘时间 • 并不是一个简单图,两点间可能有多条边 5 9 3 7 a c b(8)
与经典最短路径问题比较 ·考虑a经过b到c的最短路径 由于有换乘的情况,只记录任意两点间的 最短路径是不够的 ·并非一个标准的图论模型 7 Min(a, b )=5 Min (b, c)=3 5 Min(a,C)=5+6=11 b(8)
• 考虑a经过b到c的最短路径 • 由于有换乘的情况,只记录任意两点间的 最短路径是不够的。 • 并非一个标准的图论模型 与经典最短路径问题比较 5 6 7 a c b(8) Min(a,b)=5 Min(b,c)=3 Min(a,c)=5+6=11 3
转化成标准的图论模型 每条公交线路抽象 为一层 层与层之间相连的 顶点均代表同一个 车站 C2 它们之间的边(虚 线)的权值为换乘 C3 花费的时间 调用MM次 Dijkstra算法才能得到最优解 M为公交线路的总数
转化成标准的图论模型 • 每条公交线路抽象 为一层 • 层与层之间相连的 顶点均代表同一个 车站 • 它们之间的边(虚 线)的权值为换乘 花费的时间 • 调用M*M次Dijkstra算法才能得到最优解 • M为公交线路的总数