公交查询系统开发中数学模型的建立及其算法实现

《公交查询系统开发中数学模型的建立及其算法实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn公交查询系统开发中数学模型的建立及其算法实现12133蒋洪旭，赵有益，韩晶茹，罗智恒，左伟宏1甘肃农业大学资源与环境系，兰州（730070）2甘肃农业大学理学系，兰州（730070）3甘肃农业大学工学系，兰州（730070）E-mail：lanzhoumeng.jhx@163.com摘要：本文以“乘车次数少”，“乘车时间短”为递减优先级，以正反两方向同时逼近搜索比较的算法，在乘车次数尽可能少的基础上，建立了仅考虑公汽换乘公汽、考虑公汽与地铁换乘、考虑任意两点（公汽、地铁、步行结合

2、）之间线路选择三个数学模型，给出了公交线路查询系统的详细算法，为开发一种“公交系统查询软件”提供理论（算法）支持.关键词：公交查询系统，最优路线，数学模型，算法中图分类号：U116.21.引言随着城市人口的不断膨胀，城市公交系统的日益发展，其地位也在不断上升.如何让出行者获得及时、全面、准确的公交信息，尽可能减少换乘次数，利用最少时间到达目的地便成了迫在眉睫的事.目前，对于公交系统查询中数学模型的建立基本没有人提出，本文以“乘车次数少”，“乘车时间短”为递减优先级，考虑了人的心理因素（建立了模型三）、公交系统的现实状况建立了

3、公交查询系统中的数学模型；而对于公交最短路径算法的研究已有很多，【1,4】【5，6】【7】如Dijkstra算法及其改进算法，数据库应用算法，加权最佳换乘算法等，本文利用并改进了已有的研究成果，利用已建立的数学模型,提出了新的公交查询系统的算法.为建立适合于公交线路查询特点的数据模型，开发操作方便、简捷的城市公交查询系统提供了依据.2.研究的相关理论为了解决公交线路选择的优化问题，应该首先明确下面的一些问题：2.1最佳路线问题【2】有人对乘客的心理研究结果表明，“换乘次数”是大部分公交乘客在选择出行路线时首先考虑的因素，其次

4、是“时间最短”.一般来说，对于“换乘次数”，首选直达车，然后选择转乘1次，万不得已才选择转乘2次.如果需要3次转车才能到达目的地，一方面乘客不愿意做这种选择，另一方面，表明城市交通系统严重不畅，会给人们出行带来诸多不便.在“换乘次数少”的基础上，考虑乘车“时间最短”，因为城市生活节奏快，时间才是人们宝贵的财富，而对于“出行耗费”在给定起始站点的情况下，无论何种计价方式（单一计价、分段计价）其“出行耗费”相差不大.因此，本文不考虑“出行耗费”因素对乘车影响，最佳路线的优先级由高到低可确定为“换乘次数→时间最短”.2.2公交网络

5、图问题如果将所有公交线路和公交站点进行抽象，把空间上相近的异线站点合理抽象成图上相应的节点，将公交站点抽象成网络节点后，具有以下特点：1）连通性：道路网络中的道路交叉点连接就称为连通，而两条公交线路的连通性在该-1-http://www.paper.edu.cn点或该点附近可以转乘车就称为连通，若多条公交路线相交于一点，且没有公交停靠站点，【3】认为公交线路是不连通的.2）最短路径：道路网路上的最佳路径是要求两点之间距离最短，而公交网络中除了考虑两点之间路径距离最短外，还要考虑公交线路中换车活动的时间消耗，这也可以看成是一【

6、4】种距离成本.2.3换车实现问题公交车只能按既定的顺序停靠站点，每条公交线路都有规定的方向，分上行线和下行线、单行线、环形线，换乘必须在公交站点进行，不同公交线的站点在空间上并不一定完全相同，乘客在换乘时，有时候需要步行一段距离到附近的站点去转车，才能完成换乘.3.数学模型的建立本文以“换乘次数→时间最短”为递减优先级，实现算法时以“换乘次数”为第一优先级，在此基础上实现“时间最短”，因此建立的数学模型是以“换乘次数”为基础的“时间最短”数学模型.为了建立合理的数学模型现做以下假设：假设同一线路上某种交通工具（公汽或地铁）

7、通过相邻站点的时间保持恒定，且不存在乘客乘车排队、交通堵塞等情况.令：相邻公汽站平均行驶时间(包括停站时间)为t；相邻地1铁站平均行驶时间(包括停站时间)为t.2假设交通工具（公汽或地铁）之间的换乘时间分别为定值w，其中w表示i交通工具ijij转乘j交通工具所花费的时间，i=1,2;j=1,2；1：表示公汽，2:表示地铁.3.1仅考虑公汽线路选择的数学模型在实际生活中，如果出行只考虑公汽换乘的情况，建模的基本思想是在换车次数尽可能少的前提下，从起始站点A出发，寻求直达路线或换乘路线，追索A到B的可能路径，然后比较各可能路径的

8、方便性（换乘次数、时间），确定最优路线和可供参考的较优路线.设从起始站点A到终点B，某一条线路L经过k个站点，所用时间为T(包括停站时间)，z1换车用时为T,则全程中所用时间T′为3z′模型一T=T+T,z=1,2,?N（1）z13k+1m其中T=t,T=w,m为换车次数，t为相邻公汽站点