最优公交线路选择问题的数学模型及算法.pdf

《最优公交线路选择问题的数学模型及算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第17卷第5期运筹与管理Vo1．17，No．52008年10月OPERATIONSRESEARCHANDMANAGEMENTSCIENCE0ct．2008最优公交线路选择问题的数学模型及算法周文峰，李珍萍，刘洪伟，王吉光(1．北京物资学院教务处，北京101149；2．北京物资学院信息学院，北京101149；3．中国科学院数学与系统科学研究院北京100080)摘要：公交线路选择问题是城市公共交通信息查询的重要内容，本文建立了满足不同公交线路查询者需求的最优线路选择模型并给出了相应的算法。首先通过引入各条公交线路直达最短距离矩阵构造了公交网络直达关系图(直达矩阵)，在直达关系图(直达

2、矩阵)上，利用修改了的最短路算法，即可求得最优换乘路线。根据出行者的不同需求，通过在直达关系图上定义不同的权系数，可以分别求得换乘次数最少的公交出行线路、经过站点最少的公交出行线路；通过修改最短路算法，可以求得出行耗时最少的线路及出行费用最低的线路，另外，本模型还可以综合考虑出行者的需求情况，求得出行者满意度最大的出行路线。关键词：运筹学；最优路线；直达矩阵；换乘；最短路中图分类号：0223文章标识码：A文章编号：1007—3221(2008)05—0080—05MathematicalModelsandAlgorithmsofOptimalPublicTranspOrtatiO

3、nLineChoiceProblemZHOUWen．feng，LIZhen．ping，LIUHong．wei，WANGJi．Guang(1．EducationalAdministrationSection，BeringWuziUniversity，Beng101149，China；2．SchoolofInforma—tion，BeijingWuziUniversity，Beijing101149，China；3．InstituteofMathematicsandSystemsScience，ChineseAcademyofScience，Beng100080，China)Abst

4、ract：Publictransportationlinechoiceproblemisthemostimportantissueinqueryofpublicinformation．Thispapergivesthemathematicalmodelsandalgorithmsofoptimalpublictransportationlinechoiceaccordingtothedifferentrequestofthequesters．First，thedistancematrixofpublictransportationlineisintroduced，thenthed

5、irectedrelationgraphisconstructed．Inthedirectedrelationgraph，wecangivetheoptimallinebyrevisedshortestpathalgorithms．Fordifferentrequests，wecanfindthepublictransportationlineofleastchange，shor—testpathandSOonbyrevisingtheweightcoefficientofedgesinthedirectedrelationgraph．Byrevisingetheal—gorit

6、hmofshortestpath．wecanfindtheoptimallinesoftheshortesttimeorthe1owestfee．Furthermore，themodelcanbeusedtofindthemostsatisfactionlineofdifierenttravelers．Keywords：operationalresearch；optimalline；directedmatrix；transfer；theshortestpath0引言随着城市公交系统的快速发展，各个大城市普遍建立了四通八达的公交网络，例如北京市目前公交线收稿日期：2007．11．O

7、3基金项目：北京市属市管高等学校人才强教项目(2007．2009)和北京物资学院科研基地联合资助。作者简介：周文峰(1966．)，男，经济师，学士(在读硕士研究生)，主要研究方向：供应链管理，计算机算法；李珍萍(1966一)，女，教授，博士，主要研究方向：运筹学理论及应用，生物信息学；刘洪伟(1978．)，男．讲师，博士，主要研究方向：运筹学理论及应用；王吉光(1982一)，男。博士研究生，主要研究方向：运筹学，生物信息学。第5期周文峰，等：最优公交线路选择问题的数学模型及算法8