关于公交路线选择问题的数学模型及其优化算法
第17卷 第5期
2008年10月
运 筹 与 管 理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEVol.17,No.5Oct.2008
最优公交线路选择问题的数学模型及算法
周文峰, 李珍萍, 刘洪伟, 王吉光
北京100080)1223(1.北京物资学院教务处,北京101149;2.北京物资学院信息学院,北京101149;3.中国科学院数学与系统科学研究院,
摘 要:公交线路选择问题是城市公共交通信息查询的重要内容,本文建立了满足不同公交线路查询者需求的最优线路选择模型并给出了相应的算法。首先通过引入各条公交线路直达最短距离矩阵构造了公交网络直达关系图(直达矩阵),在直达关系图(直达矩阵)上,利用修改了的最短路算法,即可求得最优换乘路线。根据出行者的不同需求,通过在直达关系图上定义不同的权系数,可以分别求得换乘次数最少的公交出行线路、经过站点最少的公交出行线路;通过修改最短路算法,可以求得出行耗时最少的线路及出行费用最低的线路,另外,本模型还可以综合考虑出行者的需求情况,求得出行者满意度最大的出行路线。
关键词:运筹学;最优路线;直达矩阵;换乘;最短路
中图分类号:O223 文章标识码:A 文章编号:100723221()0520080205
MathematicalMc
aProblem
ZHOUWen2feng,LIZhen2ping,LIUHong2wei,WANGJi2Guang
(1.EducationalAdministrationSection,BeijingWuziUniversity,Beijing101149,China;2.SchoolofInforma2tion,BeijingWuziUniversity,Beijing101149,China;3.InstituteofMathematicsandSystemsScience,ChineseAcademyofScience,Beijing100080,China)
Abstract:Publictransportationlinechoiceproblemisthemostimportantissueinqueryofpublicinformation.Thispapergivesthemathematicalmodelsandalgorithmsofoptimalpublictransportationlinechoiceaccordingtothedifferentrequestofthequesters.First,thedistancematrixofpublictransportationlineisintroduced,thenthedirectedrelationgraphisconstructed.Inthedirectedrelationgraph,wecangivetheoptimallinebyrevisedshortestpathalgorithms.Fordifferentrequests,wecanfindthepublictransportationlineofleastchange,shor2testpathandsoonbyrevisingtheweightcoefficientofedgesinthedirectedrelationgraph.Byrevisingetheal2gorithmofshortestpath,wecanfindtheoptimallinesoftheshortesttimeorthelowestfee.Furthermore,themodelcanbeusedtofindthemostsatisfactionlineofdifferenttravelers.
Keywords:operationalresearch;optimalline;directedmatrix;transfer;theshortestpath1223
0 引言
随着城市公交系统的快速发展,各个大城市普遍建立了四通八达的公交网络,例如北京市目前公交线收稿日期:2007211203
基金项目:北京市属市管高等学校人才强教项目(200722009)和北京物资学院科研基地联合资助。
作者简介:周文峰(19662),男,经济师,学士(在读硕士研究生),主要研究方向:供应链管理,计算机算法;李珍萍(19662),女,教授,博士,主要研究方向:运筹学理论及应用,生物信息学;刘洪伟(19782),男,讲师,博士,主要研究方向:运筹学理论及应用;王吉光(19822),男,博士研究生,主要研究方向:运筹学,生物信息学。
本文主要考虑公交出行者的换乘次数、出行时间、出行费用等因 素,建立最优公交线路查询问题的数学模型,并设计算法寻找最优公交出行路线。1 最优公交出行线路选择模型...
最优公交线路选择问题的数学模型及算法_数学_自然科学_专业资料 暂无评价0人阅读0次下载举报文档 最优公交线路选择问题的数学模型及算法_数学_自然科学_专业...
小换乘次数为第一目标,最小途经站点为第二目标的公交出行最优路径模型.同时,设计了一种算法以确定最优公交线路序列,分析了线路相交的几种情况,给出了换乘点选择...
公交线路选择问题的数学模型与算法_理学_高等教育_教育专区。公交线路选择问题的...有直达车 时.在商达的线路里分别求出时间最优线路和票价最优线 路;若无,则...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 公交最优路径选择的数学模型及算法 公交线路优化设计公交线路优化设计...
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入阅读会员!获取下载券 最优公交线路选择问题的数学模型及算法 公交...
公交线路选择系统与算法 3页 5财富值喜欢此文档的还喜欢 定位球模型 28页 10财富值 最优公交线路选择问题的数... 5页 2财富值 优公交线路选择问题的数学.....
公交线路选择问题的数学模型与算法侯晓利,薛伟坡,张军委(河南师范大学计算机与...有直达车 时.在商达的线路里分别求出时间最优线路和票价最优线 路;若无,则...
设计最佳路径的目标,利用数据结构和图论思想,建立了选择最佳公交线路的数学模型....对于最优 路径问题,国内外学者提出了许多算法包括迪杰斯特拉(Dijkstra)算法、费...
热门文档