2007公共交通系统最佳路径模型与算法

我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：

1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。

(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485

(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676

2、同时考虑公汽与地铁线路，解决以上问题。

3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

公共交通系统最佳路径模型与算法
汤志高, 王继利, 曹莹瑛
指导教师：曹华林
（海军航空工程学院（青岛），青岛266041）

编者按: 这是一篇从各方面看都很不错的论文。用乘客出行时常考虑的四个指标，分别构成字典序来选择出行路线，所建立的两个模型、相应的算法及数据结构都比较恰当。六个实例的计算准确无误，第三问建立的规划模型和算法基本可行，但将一个地铁站周围可以换乘的几个公汽站视为一点的做法欠妥。
摘要: 本文将题中的直行、环行线路信息分别抽象，以MATLAB软件中元胞数组为载体储存直达数据库Q，针对用户不同需求（换乘次数、总耗时、总费用、转站车辆是否始发）构成不同非负有向赋权图和相应的权矩阵，建立多目标线性规划模型求解。为使算法的空间、时间复杂度相对平衡，在求解换乘次数小于等于2次的时候采用线路相交算法[5]来计算可行方案，换乘次数大于2次时采用邻接算法或线性规划法求解。最后把各目标下求得的出行路线方案集以字典序方式输出至用户终端。
关键词: 非负有向赋权图邻接算法字典序
分类号: AMS(2000) 90C11 中图分类号:0221 文献标识码: A

Best-routing algorithm and model for public transportation systems
TANG ZHi-gao, WANG Ji-li, CAO Ying-ying
Advisor: CAO Hua-lin
(Naval Aeronautical Engineering Academy(Qingdao),Qingdao 266041)

Abstract:In this paper, the information of direct and circle lines is abstracted respectively at first, and cellular array in MATLAB software is used as the carrier to establish a database named Q which stores all the relative information of each direct bus. We build di®erent non-negative directed weighted graph and corresponding weighted matrix referring to di®erent needs of users (the times of bus changing, total time, total expenditure and whether it's a starting station of this bus) . Subsequently, we establish multi-objective linear programming models respectively based on all the analysis carried out above. In order to balancing the space and time complexity of algorithm, Line Intersection Algorithm[5] is used to give the feasible solutions when the times of bus changing are less than or equal to two, while Adjacency Algorithm and linear programming method can be adopted when the times are more than two.Finally,integrated solutions are displayed in dictionary sort to the user terminal.
Keywords:Directed weighted graph ,Adjacency algorithm ,Dictionary sort

下载题目： 【Download】

下载原稿(适合学习，但请务必自己先练习后看本文，否则将事倍功半)： 【Download】

下载出版论文*： 【Download】

附2007全国大学生赛获奖名单： 【Download】

注：作者保留一切权利，转帖请注明出处，不得用于商业用途。*已出版论文禁止转载。