This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Lübbecke, M. E. Articles by Zimmermann, U. T. Search for Related Content

Engine Routing and Scheduling at Industrial In-Plant Railroads

Department of Mathematical Optimization, Braunschweig University of Technology, Pockelsstra ß e 14, D-38106 Braunschweig, Germany
Department of Mathematical Optimization, Braunschweig University of Technology, Pockelsstraße 14, D-38106 Braunschweig, Germany
m.luebbecke{at}tu-bs.de
u.zimmermann{at}tu-bs.de

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 NP 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.

This article has been cited by other articles:

				A. Cohn, S. Root, A. Wang, and D. Mohr Integration of the Load-Matching and Routing Problem with Equipment Balancing for Small Package Carriers Transportation Science, May 1, 2007; 41(2): 238 - 252. [Abstract] [PDF]

				M. E. Lubbecke and J. Desrosiers Selected Topics in Column Generation Operations Research, November 1, 2005; 53(6): 1007 - 1023. [Abstract] [PDF]