%0 Journal Article
%T An Algorithm for Train-set Scheduling on Weekday Based on Probabilistic Local Search<br>基于概率局域搜索的动车组平日运用计划编制算法
%A ZHAO Peng
%A Norio Tomii
%A <br>赵鹏
%J 系统工程理论与实践
%D 2004
%I 
%X The Train-Set Scheduling(TSS) is one of the most important tasks in railway field. In fact, it is constrained by many maintenance conditions, station capacity and other factors, and is a NP-hard problem. This paper focuses on algorithm to quickly work out an approximate optimal schedule. The TSS work is divided into two sub-problems: Train-Set Regular Inspection(TSRI) and Train-Set Connecting(TSC). The TSC is transformed into a Traveling Salesperson Problem (TSP) on a network called TSS network, nodes respond to trains and arcs respond to connections of trains in the network, and weight for arcs are assigned. In our algorithm, first, a regular inspection plan is made, and then, a Hamilton tour is found. If a Hamilton tour satisfies the constraints concerning daily inspection too, it could represent a train-set schedule. Therefore, when finding a new Hamilton tour based on local search, the algorithm is not only considered the connection of nodes, but also the inspection regulations. Based on the design, we developed an approximation algorithm based on the probabilistic local search method, and proved that it can be obtained train-set schedule quickly.
%K train-set
%K scheduling
%K traveling salesperson problem
%K probabilistic local search
%K meta-heuristics<br>动车组
%K 运用计划
%K 旅行商问题
%K 概率局域搜索
%K 启发式算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=962324E222C1AC1D&jid=1D057D9E7CAD6BEE9FA97306E08E48D3&aid=8A89E96A6B3923F7&yid=D0E58B75BFD8E51C&vid=B91E8C6D6FE990DB&iid=0B39A22176CE99FB&sid=AE09EACBCD1B2A13&eid=28F8B56DB6BEE30E&journal_id=1000-6788&journal_name=系统工程理论与实践&referenced_num=9&reference_num=8