Dynamic vehicle scheduling based on HTN
详细信息 查看官网全文
- 英文论文题名：Dynamic vehicle scheduling based on HTN
- 论文作者：Yindong Shen ; Zhongyi Zeng ; Zhewei Wu
- 英文论文作者：Yindong Shen ; Zhongyi Zeng ; Zhewei Wu ; School of Automation ; Huazhong University of Science and Technology ; Key Laboratory of Image Processing and Intelligent Control (Huazhong University of Science and Technology) ; Ministry of Education
- 年：2017
- 作者机构：School of Automation,Huazhong University of Science and Technology;Key Laboratory of Image Processing and Intelligent Control (Huazhong University of Science and Technology),Ministry of Education;
- 英文论文关键词：public transit ; dynamic vehicle scheduling ; scheduling strategies ; HTN planning ; SHOP2
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：U492.22
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：6
- 文件大小：232k
- 原文格式：D
- 会议级别：全国
摘要
Vehicle scheduling plays a crucial role in public transport bus companies. An efficient schedule can help bus companies reduce operating costs while being an essential guide to daily operations. However, the precompiled schedule is usually hard to be adhered to in practice due to the diversity of traffic and driving conditions. Therefore, dynamic vehicle scheduling becomes an important supplement to the daily operations. In this paper, a dynamic vehicle scheduling approach based on Hierarchical Task Network(HTN) is proposed. In the approach, two dynamic vehicle scheduling strategies are devised according to the practical scheduling philosophy. The first is to reschedule for individual vehicle independently, the objective is to maximize the execution of the precompiled schedule. The second is to reschedule for multiple vehicles simultaneously, which aims to maintain the scheduled headways. The two strategies are achieved in the HTN planning through different task decomposition processes, which are constrained by vehicle resources currently available. To verify the feasibility, this approach is implemented based on the Simple Hierarchical Ordered Planner 2(SHOP2), which is a domainindependent and state-based forward HTN planner. Experimental results show that the approach has good adaptability to solve dynamic vehicle schedule problem, meanwhile, it can be helpful to deal with the abnormal services agilely and hence to increase the service quality of public transit.
Vehicle scheduling plays a crucial role in public transport bus companies. An efficient schedule can help bus companies reduce operating costs while being an essential guide to daily operations. However, the precompiled schedule is usually hard to be adhered to in practice due to the diversity of traffic and driving conditions. Therefore, dynamic vehicle scheduling becomes an important supplement to the daily operations. In this paper, a dynamic vehicle scheduling approach based on Hierarchical Task Network(HTN) is proposed. In the approach, two dynamic vehicle scheduling strategies are devised according to the practical scheduling philosophy. The first is to reschedule for individual vehicle independently, the objective is to maximize the execution of the precompiled schedule. The second is to reschedule for multiple vehicles simultaneously, which aims to maintain the scheduled headways. The two strategies are achieved in the HTN planning through different task decomposition processes, which are constrained by vehicle resources currently available. To verify the feasibility, this approach is implemented based on the Simple Hierarchical Ordered Planner 2(SHOP2), which is a domainindependent and state-based forward HTN planner. Experimental results show that the approach has good adaptability to solve dynamic vehicle schedule problem, meanwhile, it can be helpful to deal with the abnormal services agilely and hence to increase the service quality of public transit.
Vehicle scheduling plays a crucial role in public transport bus companies. An efficient schedule can help bus companies reduce operating costs while being an essential guide to daily operations. However, the precompiled schedule is usually hard to be adhered to in practice due to the diversity of traffic and driving conditions. Therefore, dynamic vehicle scheduling becomes an important supplement to the daily operations. In this paper, a dynamic vehicle scheduling approach based on Hierarchical Task Network(HTN) is proposed. In the approach, two dynamic vehicle scheduling strategies are devised according to the practical scheduling philosophy. The first is to reschedule for individual vehicle independently, the objective is to maximize the execution of the precompiled schedule. The second is to reschedule for multiple vehicles simultaneously, which aims to maintain the scheduled headways. The two strategies are achieved in the HTN planning through different task decomposition processes, which are constrained by vehicle resources currently available. To verify the feasibility, this approach is implemented based on the Simple Hierarchical Ordered Planner 2(SHOP2), which is a domainindependent and state-based forward HTN planner. Experimental results show that the approach has good adaptability to solve dynamic vehicle schedule problem, meanwhile, it can be helpful to deal with the abnormal services agilely and hence to increase the service quality of public transit.
引文
[1]Acuna-Agost,R.,Michelon,P.,Feillet,D.and Gueye,S.(2011),"A MIP-based local search method for the railway rescheduling problem".Networks,Vol.57,No.1,pp.69-86.
[2]Bunte,S.,and Kliewer,N.(2009),"An overview on vehicle scheduling models".Public Transport,Vol.1,No.4,pp.299-317.
[3]Clausen,J.,Larsen,A.,Larsen,J.and Rezanova,N.J.(2010),"Disruption management in the airline industry-Concepts,models and methods".Computers&Operations Research,Vol.37,No.5,pp.809-821.
[4]Freling,R.,Huisman,D.and Wagelmans,A.P.M.(2003),"Models and algorithms for integration of vehicle and crew scheduling".Journal of scheduling,Vol.6,No.1,pp.63-85
[5]Hassold,S.,and Ceder,A.A.(2014),"Public transport vehicle scheduling featuring multiple vehicle types".Transportation Research Part B,Vol.67,pp.129-143.
[6]Huisman,D.,and Wagelmans,A.P.M.(2006),"A solution approach for dynamic vehicle and crew scheduling".European Journal of Operational Research,Vol.172,No.2,pp.453-471.
[7]Li,J.Q.,Mirchandani P.B.and Borenstein,D.(2009),"ALagrangian heuristic for the real-time vehicle rescheduling problem".Transportation Research Part E:Logistics and Transportation Review,Vol.45,No.3,pp.419-433.
[8]Li,J.Q.,Borenstein,D.and Mirchandani,P.B.(2007),"Adecision support system for the single-depot vehicle rescheduling problem".Computers&Operations Research,Vol.34,No.4,pp.1008-1032.
[9]Nau,D.,Au,T.C.,Ilghami,O.,Kuter,U.,Murdock,J.M.,Wu,D.,and Yaman,F.(2003),SHOP2:"An HTN planning system".Journal of Artificial and Intelligence Research,Vol.20,pp.379-404.
[10]Nau,D.,Au,T.C.,Ilghami,O.,Kuter,U.,Munoz-Avila,H.,Murdock,J.M.,Wu,D.,and Yaman,F.(2005),"Applications of SHOP and SHOP2".IEEE Intelligent Systems,Vol.20,No.2,pp.34-41.
[11]Shen,Y.D.,Peng,K.K.,Chen,K.and Li,J.P.(2013),"Evolutionary crew scheduling with adaptive chromosomes".Transportation Research Part B:Methodological,Vol.56pp.174-185
[12]Shen,Y.D.,Xu,J.,Li,J.P.(2016),"A probabilistic model for vehicle scheduling based on stochastic trip times".Transportation Research Part B:Methodological,Vol.85,No.1,pp.19-31.
[13]Shen,Y.D.,Xu,J.,Wu X.Y.(2017),"Vehicle scheduling based on variable trip times with expected on-time performance".International Transactions in Operational Research,Vol.24,No.1,pp.99-113.
[14]Shen,Y.D.,Xu,J.,Zeng,Z.Y.(2016a),"Public transit planning and scheduling based on AVL data in China".International Transactions in Operational Research,Vol.23,No.6,pp.1089-1111.
[15]Steinzen,I.,Gintner,V.,Suhl,L.,and Kliewer,N.(2010),"A time-space network approach for the integrated vehicleand crew-scheduling problem with multiple depots".Transportation Science,Vol.44,No.3,pp.367-382.
[16]Tang,P.,Wang,H.W.,Qi,C.and Wang,J.(2012),"Anytime heuristic search in temporal HTN planning for developing incident action plans".AI Communications,Vol.38,No.4,pp.321-342.
[17]Wang,Z.,Wang,H.W.,Qi,C.,and Wang,J.(2013),"Aresource enhanced HTN planning approach for emergency decision-making".Applied intelligence,Vol.38,No.2,pp.226-238.
[18]Xu,J.,and Shen,Y.D.(2012),"Setting Scheduled Trip Time Based on AVL Data".Journal of Transportation Systems Engineering and Information Technology,Vol.12,No.5,pp.39-45.
[2]Bunte,S.,and Kliewer,N.(2009),"An overview on vehicle scheduling models".Public Transport,Vol.1,No.4,pp.299-317.
[3]Clausen,J.,Larsen,A.,Larsen,J.and Rezanova,N.J.(2010),"Disruption management in the airline industry-Concepts,models and methods".Computers&Operations Research,Vol.37,No.5,pp.809-821.
[4]Freling,R.,Huisman,D.and Wagelmans,A.P.M.(2003),"Models and algorithms for integration of vehicle and crew scheduling".Journal of scheduling,Vol.6,No.1,pp.63-85
[5]Hassold,S.,and Ceder,A.A.(2014),"Public transport vehicle scheduling featuring multiple vehicle types".Transportation Research Part B,Vol.67,pp.129-143.
[6]Huisman,D.,and Wagelmans,A.P.M.(2006),"A solution approach for dynamic vehicle and crew scheduling".European Journal of Operational Research,Vol.172,No.2,pp.453-471.
[7]Li,J.Q.,Mirchandani P.B.and Borenstein,D.(2009),"ALagrangian heuristic for the real-time vehicle rescheduling problem".Transportation Research Part E:Logistics and Transportation Review,Vol.45,No.3,pp.419-433.
[8]Li,J.Q.,Borenstein,D.and Mirchandani,P.B.(2007),"Adecision support system for the single-depot vehicle rescheduling problem".Computers&Operations Research,Vol.34,No.4,pp.1008-1032.
[9]Nau,D.,Au,T.C.,Ilghami,O.,Kuter,U.,Murdock,J.M.,Wu,D.,and Yaman,F.(2003),SHOP2:"An HTN planning system".Journal of Artificial and Intelligence Research,Vol.20,pp.379-404.
[10]Nau,D.,Au,T.C.,Ilghami,O.,Kuter,U.,Munoz-Avila,H.,Murdock,J.M.,Wu,D.,and Yaman,F.(2005),"Applications of SHOP and SHOP2".IEEE Intelligent Systems,Vol.20,No.2,pp.34-41.
[11]Shen,Y.D.,Peng,K.K.,Chen,K.and Li,J.P.(2013),"Evolutionary crew scheduling with adaptive chromosomes".Transportation Research Part B:Methodological,Vol.56pp.174-185
[12]Shen,Y.D.,Xu,J.,Li,J.P.(2016),"A probabilistic model for vehicle scheduling based on stochastic trip times".Transportation Research Part B:Methodological,Vol.85,No.1,pp.19-31.
[13]Shen,Y.D.,Xu,J.,Wu X.Y.(2017),"Vehicle scheduling based on variable trip times with expected on-time performance".International Transactions in Operational Research,Vol.24,No.1,pp.99-113.
[14]Shen,Y.D.,Xu,J.,Zeng,Z.Y.(2016a),"Public transit planning and scheduling based on AVL data in China".International Transactions in Operational Research,Vol.23,No.6,pp.1089-1111.
[15]Steinzen,I.,Gintner,V.,Suhl,L.,and Kliewer,N.(2010),"A time-space network approach for the integrated vehicleand crew-scheduling problem with multiple depots".Transportation Science,Vol.44,No.3,pp.367-382.
[16]Tang,P.,Wang,H.W.,Qi,C.and Wang,J.(2012),"Anytime heuristic search in temporal HTN planning for developing incident action plans".AI Communications,Vol.38,No.4,pp.321-342.
[17]Wang,Z.,Wang,H.W.,Qi,C.,and Wang,J.(2013),"Aresource enhanced HTN planning approach for emergency decision-making".Applied intelligence,Vol.38,No.2,pp.226-238.
[18]Xu,J.,and Shen,Y.D.(2012),"Setting Scheduled Trip Time Based on AVL Data".Journal of Transportation Systems Engineering and Information Technology,Vol.12,No.5,pp.39-45.