动态车辆调度系统的滚动时域调度算法英文.pdfVIP

J ou rnal of Sou theast U n iversity (Eng lish Ed ition) 　V o l. 2 1, N o. 1, pp. 92 96　M ar. 2005 ISSN 1003—7985 Rolling hor izon scheduling a lgor ithm for dynam ic veh icle scheduling sy stem J ia Yongj i　 Gu H anyu　 X i Yugeng ( In stitu te of A u tom ation, Shanghai J iaotong U n iversity, Shanghai 200030, Ch ina) Ab stract: D ynam ic exclusive p ickup and delivery p rob lem w ith tim e w indow s (D E PD PTW ) , a sp ec ia l dynam ic veh ic le schedu ling p rob lem , is p rop osed. Its m athem atical descrip tion is g iven and its static p rop erties are analyzed, and then the p rob lem is sim p lified as the asymm etrical traveling salesm an p rob lem w ith tim e w indow s. The ro lling horizon schedu ling algorithm (RHSA ) to so lve th is dynam ic p rob lem is p rop osed. B y the ro lling of tim e horizon, the RHSA can adap t to the p rob lem s dynam ic change and reduce the com p u tation tim e by dealing w ith on ly p art of the custom ers in each ro lling tim e horizon. Then, its th ree factors, the cu rren t custom er w indow , the schedu ling of the cu rren t custom er w indow and the ro lling strategy, are analyzed. The test resu lts dem onstrate the effectiveness of the RHSA to so lve the dynam ic veh icle schedu ling p rob lem. Key words: dynam ic veh ic le schedu ling; ro lling horizon schedu ling algorithm ; exc lusive; p ickup and delivery p rob lem w ith tim