رویکرد مبتنی بر نسل ستون برای مشکل بهینه سازی طراحی شبکه قطار
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|5737||2013||17 صفحه PDF||سفارش دهید||محاسبه نشده|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Transportation Research Part E: Logistics and Transportation Review, Volume 50, February 2013, Pages 1–17
This paper investigates the Train Network Design Optimization problem arising from railroad industry which involves the integration of three inter-related decision sub-problems: train routing which is to identify origin, destination and itinerary for individual trains; block-to-train assignment detailing the block movements with trains and swaps between trains; and crew-to-train assignment specifying the crew services for train routes. A column generation based hierarchical approach with two stages is designed: the first stage generates a pool of promising train routes iteratively based on the crew segments by the column generation technique; and the second stage develops an integer linear programming model for the subsequent decisions including train route selection and block-to-train assignment. Numerical experiments with realistic test instances are conducted and the outcome demonstrates the capability of the proposed approach in solving the Train Network Design Optimization problem competently.
Being an important logistic system supporting global and regional economy, railroad freight transportation handles the movement of millions of cargo shipments on a 24/7/365 service. Behind the scene there exist a broad spectrum of complex and challenging railroad operations. Various decision problems emerge in the railroad planning and operation stages. This makes railroad freight transportation an ideal area for applying operations research techniques to support the planning and operation processes and also to advance the efficiency and reliability. Decision problems of railroad operations can be organized into strategic, tactical and operational levels (Assad, 1980). At the strategic planning level, resource acquisition and the construction of the railroad infrastructure in the long-term should be determined. With the given physical railroad network, tactical planning is conducted to construct a service network based on the freight transportation demand from a medium-term planning perspective (monthly or weekly). The output of the tactical planning problems is used as the guideline for the scheduling of daily activities at the operational level. Given a physical network consisting of rail stations and tracks with restricted capacity and shipments with various origins and destinations, a common planning method is firstly to consolidate shipments into blocks based on cargo attributes, subsequently to combine blocks into trains, and finally to assign locomotives and crews to the created trains. Although straightforward, this planning method for railroad freight transportation has been widely adopted and is still well employed currently by railroad practitioners. Typical decision problems involved in the tactical level of railroad freight transportation generally include railroad blocking problem, train routing problem, block-to-train assignment problem, locomotive assignment problem and crew assignment problem. Readers may refer to Cordeau et al., 1998, Ahuja et al., 2005, Harrod and Gorman, 2010 and Nemani and Ahuja, 2010 for comprehensive surveys. In this study, we investigate the combined train routing, block-to-train assignment and crew-to-train assignment problem which is also referred as Train Network Design Optimization problem in the railroad freight transportation area. Actually, Train Network Design Optimization problem plays an essential role in the service network design at the tactical decision level of railroad freight transportation. However, due to the increased difficulty from the integration of various decisions, this problem, to the best of our knowledge, has not been explored in the research community until the INFORMS Railway Application Section organized a problem solving competition in 2011 (INFORMS, 2011). This study is the first attempt to address the Train Network Design Optimization problem integrating the train routing, block-to-train assignment and crew-to-train assignment decisions. State-of-the-art mathematical optimization techniques are utilized to build a unified framework for the integrated problem. To address the integrated problem, we design a column generation based approach with two stages. The train routing and crew-to-train assignment is integrated in the first stage to generate a pool of promising train routes with the aid of column generation technique. In the second stage, we model the train route selection and the block-to-train assignment problem as an integer program. Several operational costs and constraints (train work event, block swap operation, crew and train imbalance) that were not considered in previous literature are specifically included in the model formulation. Numerical experiments with realistic test instances are conducted and the outcome demonstrates that the proposed approach is able to generate good train plans competently. The remaining paper is organized as follows. A brief literature review of relevant studies is presented in Section 2. In Section 3, we provide a detailed description and formal definition for the Train Network Design Optimization problem. Section 4 presents the implementation procedures of the two-stage solution approach based on column generation strategy. Two realistic instances are used to test the effectiveness and efficiency of the proposed approach in Section 5. Finally, Section 6 concludes this paper.
نتیجه گیری انگلیسی
To conclude, we have modeled and solved in this paper the Train Network Design Optimization problem in railroad freight transportation industry with consideration of three decision sub-problems: train routing, block-to-train assignment and crew-to-train assignment. We contribute to the literature by proposing a two-stage hierarchical approach with application of column generation technique and integer programming model. In the first stage, train route candidates are explicitly generated by column generation based on crew segment information. With the pool of generated train routes, the second stage models simultaneously the train route selection and block-to-train assignment. The developed solution approach has been validated by realistic test instances and has shown the capability of producing high quality solutions within a reasonable time.