Dynamic vehicle scheduling based on HTN
Yindong Shen, Zhongyi Zeng, Zhewei Wu · 2017
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 domain-independent 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.