客运段乘务值乘交路计划系统的设计与实现
|
摘要
乘务值乘交路计划的编制是铁路客运系统的重要作业之一,包括列车运行图的获取、乘务任务的分配、乘务工作时间的计算、各车次的乘务员安排、及乘务员工作时间与休息时间的分配。乘务值乘交路计划的编制结果不仅决定着客运段乘务成本的消耗,也影响着乘务员的工作效率,因此编制高质量的乘务值乘交路计划是一个较为复杂的问题。目前,客运段仍普遍采用手工编制的方式编制乘务值乘交路计划,这已不能满足铁路信息化的需求,国内对于该问题的研究多集中于乘务日计划的模型算法优化研究,月度乘务计划的自动编制还有待于进一步的探讨,因此,研究开发一套科学完整的乘务值乘交路计划系统,对于提高客运段的工作水平具有重要的意义。
首先,本论文归纳总结了当前该领域的研究现状,并对实地调研结果进行了详细的分析,针对现状中存在的问题,挖掘出本文研究的创新方向；其次,对核心问题的优化模型和算法进行了研究,将值乘交路计划问题转化为非对称旅行商问题,建立了非对称旅行商问题的数学模型,运用最小生成树算法求解该模型,并通过算例对模型进行了检验；最后,论文完成了对客运段乘务值乘交路计划系统的设计与实现,包括对系统进行范围分析、需求分析及数据分析,设计了目标系统的应用架构,总体结构,系统流程和数据库,并最终实现了值乘交路计划的自动编制。
通过研究,本文提出了较为完整的值乘交路计划编制方法,将乘务值乘交路计划问题转化为非对称的旅行商问题进行研究,该模型的创新点在于能够将乘务日计划与月计划整合为一个问题进行解决,较符合当前客运段的实际情况,并设计了科学的大休日添加方法。最终计算机系统的实现对客运段信息化发展具有重要的意义。
Crew planning making is an important part of passenger transport depot, which needs to get train diagram data, distribute the tasks, compute the working time, arrange the crew members and balance the working time and relaxation time. The amount of crew costs and the working efficiency of crew members depend on the result of crew planning, so how to make a high quality planning is a complex question. At present, the passenger transport depot makes the crew planning mainly by hand, which can't follow the railway's informatization trends. The national research on the crew planning needs further investigation. Therefore, to develop a scientific system to make crew planning will have a good effect on the improvement of working efficiency.
First and foremost, this paper summarizes the present research situation, and makes a specific analysis of field investigation. Depends on the existing problems in the practical situation, the innovation direction is located. Furthermore, the paper investigates the core model and algorithm, the asymmetric traveling salesman problems model is constructed, which is solved by the minimum spanning tree algorithm, and finish the model test with a practical example. At last, the design and enforcement of the crew planning system are completed, including the context analysis, demand analysis and data analysis. The application framework, general structure, system process, and database are designed. And the automatic crew planning making is the big achievement.
Through the research, this paper provides a whole method of making crew planning, transforms the target problem to the asymmetric traveling salesman problem, and designs the scientific adding method of relaxation days. Combining the Crew Scheduling Problem and Crew Rostering Problem is the innovative point of the model, which meets the actual situation reasonably. The final achievement of crew planning system will promote the development of informatization construction in passenger railway depot.
首先,本论文归纳总结了当前该领域的研究现状,并对实地调研结果进行了详细的分析,针对现状中存在的问题,挖掘出本文研究的创新方向；其次,对核心问题的优化模型和算法进行了研究,将值乘交路计划问题转化为非对称旅行商问题,建立了非对称旅行商问题的数学模型,运用最小生成树算法求解该模型,并通过算例对模型进行了检验；最后,论文完成了对客运段乘务值乘交路计划系统的设计与实现,包括对系统进行范围分析、需求分析及数据分析,设计了目标系统的应用架构,总体结构,系统流程和数据库,并最终实现了值乘交路计划的自动编制。
通过研究,本文提出了较为完整的值乘交路计划编制方法,将乘务值乘交路计划问题转化为非对称的旅行商问题进行研究,该模型的创新点在于能够将乘务日计划与月计划整合为一个问题进行解决,较符合当前客运段的实际情况,并设计了科学的大休日添加方法。最终计算机系统的实现对客运段信息化发展具有重要的意义。
Crew planning making is an important part of passenger transport depot, which needs to get train diagram data, distribute the tasks, compute the working time, arrange the crew members and balance the working time and relaxation time. The amount of crew costs and the working efficiency of crew members depend on the result of crew planning, so how to make a high quality planning is a complex question. At present, the passenger transport depot makes the crew planning mainly by hand, which can't follow the railway's informatization trends. The national research on the crew planning needs further investigation. Therefore, to develop a scientific system to make crew planning will have a good effect on the improvement of working efficiency.
First and foremost, this paper summarizes the present research situation, and makes a specific analysis of field investigation. Depends on the existing problems in the practical situation, the innovation direction is located. Furthermore, the paper investigates the core model and algorithm, the asymmetric traveling salesman problems model is constructed, which is solved by the minimum spanning tree algorithm, and finish the model test with a practical example. At last, the design and enforcement of the crew planning system are completed, including the context analysis, demand analysis and data analysis. The application framework, general structure, system process, and database are designed. And the automatic crew planning making is the big achievement.
Through the research, this paper provides a whole method of making crew planning, transforms the target problem to the asymmetric traveling salesman problem, and designs the scientific adding method of relaxation days. Combining the Crew Scheduling Problem and Crew Rostering Problem is the innovative point of the model, which meets the actual situation reasonably. The final achievement of crew planning system will promote the development of informatization construction in passenger railway depot.
引文
[1]于得水.客运专线乘务计划编制系统的设计与实现[D].西南交通大学.2007年4月.
[2]金文龙,程凯,王青松.铁路客运乘务派班系统的设计与实现[J].铁路计算机应用.2011.20(2).
[3]赵鹏.高速铁路动车组和乘务员运用的研究[D].北京交通大学.1998年6月.
[4]夏平.客运专线乘务员运用计划编制研究[D].北京交通大学.2007年12月.
[5]张苏波,吕红霞,刘淑辉.列车乘务派班系统的设计与实现[J].铁道运输与经济.2007.29(8).
[6]银大伟.乘务计划编制系统的研究与设计[D].西南交通大学.2008年6月.
[7]李军.非对称距离的旅行商问题的构造算法[J].运筹与管理.2000.9(1).
[8]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社.2005.
[9]黄友锐.智能优化算法及其应用[M].北京：国防工业出版社.2008.
[10]程岩岩.我国铁路乘务调度计划编制方法的研究与设计[D].北京交通大学.2007年12月.
[11]文永军.旅行商问题的两种智能算法[D].西安电子科技大学.2010年1月.
[12]最小生成树[EB/OL].百度百科,http://baike.baidu.com/view/288214.htm.2012-3-20.
[13]欧拉回路[EB/OL].百度百科,http://baike.baidu.com/view/566040.htm.2012-3-20.
[14]卢开澄,卢华明.组合数学[M].第3版.北京：清华大学出版社.2002.
[15]赵禹骅,任伟民,李可柏.关于汉密尔顿短路径的算法[J].东方电气评论.2004.18(1).
[16]有关汉密尔顿同路的定理[EB/OL].百度文库,http://wenku.baidu.com/view/05ee60b069dc5022aaea0011.html.2012-3-20
[17]图与网络分析[EB/OL].百度文库,http://wenku.baidu.com/view/4c4546eab8f67clcfad6b8b4.html.2012-3-20.
[18]张苏波.客运专线乘务排班系统相关问题研究[D].西南交通大学.2009年4月.
[19]王莹,刘军,苗建瑞.客运专线乘务交路计划编制的优化模型与算法[J].铁道学报.2009.31(1).
[20]张波.轮乘制下的铁路乘务排班系统[J].铁路通信信号工程技术.2008.5(3).
[21]纪殿瑜,王建英,刘新.乘务日计划的编制方法研究[J].中国铁路.2010.(5).
[22]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京交通大学.2009年2月.
[23]赵鹏,胡安洲,杨浩.机车乘务员运用计划的优化编制[J].铁道学报.1998(4).
[24]郑金子,苗建瑞,张君平.蚁群算法在铁路乘务运用计划编制中的应用研究[J].铁路计算机应用.2010.19(10).
[25]王嫒媛,周成晨,倪少权.基于蚁群算法的客运专线乘务交路计划编制方法研究[J].铁路计算机应用.2009.18(7).
[26]夏平,马建军,乘务员运用计划编制模型与计算方法的研究[J].铁道运输与经济.2007.29(11).
[27]阎永光,黄斌,广深线城际列车乘务组排班计划编制方法探讨[J].交通运输工程与信息学报.2010.8(1).
[28]陈旭.基丁乘务员偏好性的机车乘务交路编制研究[D].北京交通大学.2009年6月.
[29]李成兵,鲁工圆,郭倩倩,陈钉均.动车组乘务员运用计划的均衡性研究[J].内燃机车.2009(12).
[30]王莹,刘军,王伟,苗建瑞.客运专线乘务计划优化编制系统研究[J].铁路计算机应用.2009.18(4).
[31]金文龙,程凯,王青松.铁路客运乘务派班系统的设计与实现[J].铁路计算机应用.2011.20(2).
[32]赵鹏,姚凤全,张洪亮.综合调度仿真系统中的机车乘务计划的编制[J].铁道运输与经济.2004.27(3).
[33]朱涛.基于智能Agent的客运专线运营调度系统机车乘务计划自动编制问题研究[D].北京交通大学.2007年6月.
[34]Dennis Huisman,Leo G Kroon,Ramon M Lentink.Operations Research in Passenger Railway Transportation[J].Statistica Neerlandica.2005.59(4).
[35]Alberto Caprara,Matteo Fischetti,Pier Luigi Guida,Paolo Toth,Daniele Vigo.Modeling and Solving the Crew Rostering Problem.Operations Research. 1998.46(6).820-830.
[36]Alberto Caprara,Matteo Fischetti,Pier Luigi Guida,PaoloToth,Daniele Vigo.Solution of Large-Scale Railway Crew Planning Problems:the Italian Experience. Technical Report. 1997.
[37]Alberto Caprara,Michele Monaci,Paolo Toth.A Global Method for Crew Planning in Railway Applications. Computer-Aided Scheduling of Public Transport.Lecture Notes in Economics and Mathematical Systems.2001.
[38]A.T.Ernst,H.Jiang,M.Krishnamoorthy,H.Nott,D.Sier.An Integrated Optimization Model for Train Crew Management. Annals of Operations Research.2001.108.211-224.
[39]哈尔滨铁路局教育处.哈尔滨铁路局客运营销处.列车长列车员[M].北京：中国铁道出版社.2004年.
[40]郑会颂,白玫,刘影.系统分析与设计[M].南京：东南大学出版社.2005.
[41]Jeffrey L.Whitten,Lonnie D.Bentley.肖刚,孙慧等泽.系统分析与设计方法[M].北京：机械工业出版社.2007年.
[2]金文龙,程凯,王青松.铁路客运乘务派班系统的设计与实现[J].铁路计算机应用.2011.20(2).
[3]赵鹏.高速铁路动车组和乘务员运用的研究[D].北京交通大学.1998年6月.
[4]夏平.客运专线乘务员运用计划编制研究[D].北京交通大学.2007年12月.
[5]张苏波,吕红霞,刘淑辉.列车乘务派班系统的设计与实现[J].铁道运输与经济.2007.29(8).
[6]银大伟.乘务计划编制系统的研究与设计[D].西南交通大学.2008年6月.
[7]李军.非对称距离的旅行商问题的构造算法[J].运筹与管理.2000.9(1).
[8]《运筹学》教材编写组.运筹学[M].北京：清华大学出版社.2005.
[9]黄友锐.智能优化算法及其应用[M].北京：国防工业出版社.2008.
[10]程岩岩.我国铁路乘务调度计划编制方法的研究与设计[D].北京交通大学.2007年12月.
[11]文永军.旅行商问题的两种智能算法[D].西安电子科技大学.2010年1月.
[12]最小生成树[EB/OL].百度百科,http://baike.baidu.com/view/288214.htm.2012-3-20.
[13]欧拉回路[EB/OL].百度百科,http://baike.baidu.com/view/566040.htm.2012-3-20.
[14]卢开澄,卢华明.组合数学[M].第3版.北京：清华大学出版社.2002.
[15]赵禹骅,任伟民,李可柏.关于汉密尔顿短路径的算法[J].东方电气评论.2004.18(1).
[16]有关汉密尔顿同路的定理[EB/OL].百度文库,http://wenku.baidu.com/view/05ee60b069dc5022aaea0011.html.2012-3-20
[17]图与网络分析[EB/OL].百度文库,http://wenku.baidu.com/view/4c4546eab8f67clcfad6b8b4.html.2012-3-20.
[18]张苏波.客运专线乘务排班系统相关问题研究[D].西南交通大学.2009年4月.
[19]王莹,刘军,苗建瑞.客运专线乘务交路计划编制的优化模型与算法[J].铁道学报.2009.31(1).
[20]张波.轮乘制下的铁路乘务排班系统[J].铁路通信信号工程技术.2008.5(3).
[21]纪殿瑜,王建英,刘新.乘务日计划的编制方法研究[J].中国铁路.2010.(5).
[22]王莹.动车组运用计划和乘务计划的优化方法研究[D].北京交通大学.2009年2月.
[23]赵鹏,胡安洲,杨浩.机车乘务员运用计划的优化编制[J].铁道学报.1998(4).
[24]郑金子,苗建瑞,张君平.蚁群算法在铁路乘务运用计划编制中的应用研究[J].铁路计算机应用.2010.19(10).
[25]王嫒媛,周成晨,倪少权.基于蚁群算法的客运专线乘务交路计划编制方法研究[J].铁路计算机应用.2009.18(7).
[26]夏平,马建军,乘务员运用计划编制模型与计算方法的研究[J].铁道运输与经济.2007.29(11).
[27]阎永光,黄斌,广深线城际列车乘务组排班计划编制方法探讨[J].交通运输工程与信息学报.2010.8(1).
[28]陈旭.基丁乘务员偏好性的机车乘务交路编制研究[D].北京交通大学.2009年6月.
[29]李成兵,鲁工圆,郭倩倩,陈钉均.动车组乘务员运用计划的均衡性研究[J].内燃机车.2009(12).
[30]王莹,刘军,王伟,苗建瑞.客运专线乘务计划优化编制系统研究[J].铁路计算机应用.2009.18(4).
[31]金文龙,程凯,王青松.铁路客运乘务派班系统的设计与实现[J].铁路计算机应用.2011.20(2).
[32]赵鹏,姚凤全,张洪亮.综合调度仿真系统中的机车乘务计划的编制[J].铁道运输与经济.2004.27(3).
[33]朱涛.基于智能Agent的客运专线运营调度系统机车乘务计划自动编制问题研究[D].北京交通大学.2007年6月.
[34]Dennis Huisman,Leo G Kroon,Ramon M Lentink.Operations Research in Passenger Railway Transportation[J].Statistica Neerlandica.2005.59(4).
[35]Alberto Caprara,Matteo Fischetti,Pier Luigi Guida,Paolo Toth,Daniele Vigo.Modeling and Solving the Crew Rostering Problem.Operations Research. 1998.46(6).820-830.
[36]Alberto Caprara,Matteo Fischetti,Pier Luigi Guida,PaoloToth,Daniele Vigo.Solution of Large-Scale Railway Crew Planning Problems:the Italian Experience. Technical Report. 1997.
[37]Alberto Caprara,Michele Monaci,Paolo Toth.A Global Method for Crew Planning in Railway Applications. Computer-Aided Scheduling of Public Transport.Lecture Notes in Economics and Mathematical Systems.2001.
[38]A.T.Ernst,H.Jiang,M.Krishnamoorthy,H.Nott,D.Sier.An Integrated Optimization Model for Train Crew Management. Annals of Operations Research.2001.108.211-224.
[39]哈尔滨铁路局教育处.哈尔滨铁路局客运营销处.列车长列车员[M].北京：中国铁道出版社.2004年.
[40]郑会颂,白玫,刘影.系统分析与设计[M].南京：东南大学出版社.2005.
[41]Jeffrey L.Whitten,Lonnie D.Bentley.肖刚,孙慧等泽.系统分析与设计方法[M].北京：机械工业出版社.2007年.