Engine Routing and Scheduling at Industrial In-Plant Railroads

Lübbecke, Marco E.; Zimmermann, Uwe T.
May 2003
Transportation Science;May2003, Vol. 37 Issue 2, p183
Academic Journal
In-plant railroad engine scheduling involves routing and scheduling decisions for a heterogeneous fleet of switching engines to serve a set of time-window and capacity-constrained transportation requests. Despite an ever-increasing competition, the current planning is purely by pencil and paper. Our paper describes the mathematical and algorithmic developments for addressing in-plant railroad decision support for scheduling and routing. The problem discussed in our work is related to the multiple-vehicle pickup and delivery problem. Exploiting the structure of admissible schedules of our particular railroad situation, we introduce two formulations of the problem as mixed integer and set partitioning programs. We propose solving the linear programming relaxation of the set partition model by column generation. We focus on the pricing problem stated in the form of a constrained shortest path problem, which is 33 complete in the strong sense. A new exact label correcting algorithm is developed that prunes the search space in a novel manner. Heuristically obtained integer solutions of a practical quality are proposed as well. All the claims are demonstrated by computational experiments on both artificial and real-life data. We discuss implementation details as well.


Related Articles

  • A NON-NUMERICAL APPROACH TO PRODUCTION SCHEDULING PROBLEMS. Akers Jr., Sheldon B.; Friedman, Joyce // Journal of the Operations Research Society of America;Nov55, Vol. 3 Issue 4, p429 

    In a typical production scheduling problem, n parts must be fabricated using m machines, and each part must be fabricated in a given order on the machines. It is desired to schedule the parts so that the program is optimal with respect to some given criteria. In general, (n!)[SUPm] programs must...

  • Tactical Scheduling of Rail Operations: The SCAN I System. Jovanović, Dejan; Harker, Patrick T. // Transportation Science;Feb91, Vol. 25 Issue 1, p46 

    This paper presents an overview of a decision-support model for the tactical scheduling of freight railroad traffic which is designed to support the weekly or monthly scheduling of rail operations. This initial version of the Schedule Analysis (SCAN) system is based upon notions from both...

  • A Variable Trip Time Model for Cyclic Railway Timetabling. Kroon, Leo G.; Peeters, Leon W.P. // Transportation Science;May2003, Vol. 37 Issue 2, p198 

    In this paper we describe how variable trip times can be included into an existing cyclic railway timetabling model based on the well-known periodic event scheduling problem (PESP). Thereby we provide an extension of the existing model because in the existing model it is assumed that the trip...

  • MODELING AND SOLVING THE TRAIN TIMETABLING PROBLEM. Caprara, Alberto; Fischetti, Matteo; Toth, Paolo // Operations Research;Sep/Oct2002, Vol. 50 Issue 5, p851 

    The train timetabling problem aims at determining a periodic timetable for a set of trains that does not violate track capacities and satisfies some operational constraints. In particular, we concentrate on the problem of a single, one-way track linking two major stations, with a number of...

  • Solving Real-Life Locomotive-Scheduling Problems. Ahuja, Ravindra K.; Jian Liu; Orlin, James B.; Sharma, Dushyant; Shughart, Larry A. // Transportation Science;Nov2005, Vol. 39 Issue 4, p503 

    In the locomotive-scheduling problem (or the locomotive-assignment problem), we must assign a consist (a set of locomotives) to each train in a preplanned train schedule so as to provide each train with sufficient locomotive power to pull the train from its origin to its destination....

  • Vehicle Routing and Scheduling with Full Truckloads. Arunapuram, Sundararajan; Mathur, Kamlesh; Solow, Daniel // Transportation Science;May2003, Vol. 37 Issue 2, p170 

    Truckload carriers are constantly faced with the problem of shipping full truckloads of goods at minimum cost between pairs of cities or customers, using a fleet of trucks located at one or more depots. In this paper, a new branch-and-bound algorithm for solving an integer-programming...

  • Energy-aware disk scheduling for soft real-time I/O requests. Youjip Won; Jongmin Kim; Wonmin Jung // Multimedia Systems;Feb2008, Vol. 13 Issue 5/6, p409 

    Abstract  In this work, we develop energy-aware disk scheduling algorithm for soft real-time I/O. Energy consumption is one of the major factors which bar the adoption of hard disk in mobile environment. Heat dissipation of large scale storage system also calls for an...

  • Chapter 5: Programming and Scheduling Process. Sawyer, Thomas H. // Facilities Planning for Health, Fitness, Physical Activity, Recr;2005, p53 

    Discusses program and schedule development in organizations. Role of management personnel in the planning process; Elements that influence program development; Importance of evaluation to the program development process; Patterns of program scheduling.

  • Rescheduling the Railroads. Gallagher, John // Traffic World;5/24/99, Vol. 258 Issue 8, p32 

    Focuses on the implementation of the Precision Execution, a buzz phrase for scheduled rail service in the United States. Assessment on the performance standards of railroads; Difficulties encountered by freight railroads; Enhancement of the efficiency of yard operations.


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics