The Engine Scheduling Problem In A Railway Network

Abstract

We present the mathematical version of a scheduling problem faced by a railway company that employs several engine types to provide power for its trains. Each train has motive power requirements that are determined by the weight and length of the train, and the route it travels. The operating constraint is to provide a train with sufficient engines to meet its motive power requirements. We give a mathematical formulation of selecting the mix of engine types that gives the lowest capital investment and operating cost and explore a method of solution based on the decomposition method of Benders. The computational results we obtained are satisfactory for medium size problems and unsatisfactory for large size problems. We also discuss the relevance of the model and comment on its utility in practice.

Résumé

Nous présentons une version mathématique d’un probléme d’ordonnancement auquel font face les compagnies de chemin de fer qui se servent de nombreux types d’engins afin de fournir la puissance pour leurs trains. Chaque train a des exigences de puissance motrice qui sont déterminees par le poids et la longueur du train de même que par la route qu’il parcourt. Les contraintes d’opération est à l’effet de pourvoir le train avec suffisamment d’engins de façon à rençontrer ses exigences de puissance motrice. Nous présentons une formulation mathématique pour sélectionner la combinaison des types d’engins qui donne le coût d’operation et l’investissement capital le plus bas et nous explorons la méthode de solution fondée sur la méthode de décomposition de Benders. Les résultats des calculs que nous obtenons sont satisfaisants pour les problémes de taille moyenne et non-satisfaisants pour les problémes d’envergure. Nous discutons de plus de l’importance du modéle et faisons nos commentaires sur son utilité en pratique.

Additional information

Notes on contributors

M. Florian

MICHAEL FLORIAN is Associate Professor in Département d’informatique, Université de Montréal and serves as Director, Centre de recherche sur les transports. He holds a B ENG from McGill University and an M sc and DR ENG SC in Operations Research from Columbia University. His research papers have appeared in INFOR. Management Science, Operations Research, Revue frangaise de Recherche operationnelle, Naval Research Logistics Quarterly, Transportation Science, and Transportation Research. He is a past Editor of INFOR and serves as Associate Editor of Operations Research and Associate Editor of Transportation Science. His current research interests are in modelling transportation systems, applications of mathematical programming and network optimization problems.

G. Bushell

GEORGE BUSHELL is currently a team manager in the Operational Research Branch of the Canada Post Office in Ottawa. His work has involved the routing and scheduling of vehicles and men, plant simulation, and the study of measurement systems. Prior to his present position, he worked in the Operational Research Branch at the Canadian National Railways in Montreal where he did work in pipeline logistics, network analysis, and mathematical programming. He received an Hon. BA (Geography) from the University of Western Ontario and an MA in Geography (specializing in Transportation) from the University of Toronto.

J. Ferland

JACQUES A. FERLAND has been associate professor of Operations Research in the Département d’informatique at the Université de Montréal since 1971. In 1971 he received his PH D in Operations Research from Stanford University. He also obtained an M sc in Statistics from Stanford University in 1971, an M SC in Informatique in 1967 and a B sc in Mathematics in 1966 from the University de Montreal. His main research interests include networks flow theory, large scale mathematical programming, and generalized convexity.

L. Nastansky

PROFESSOR DR LUDWIG NASTANSKY was born in Germany in 1941. He received his Diploma (MA) in Business Management and Management Science and his Doctorate in Operations Research from the Faculty for Business, Economics and Law, University of Saarbruecken, W.- Germany. He was Visiting Professor at the Département d’informatique, Université de Montreal (1971-72), and since 1975 has been Dean of the Faculty for Business and Economics of the University of Paderborn. His current research interests are applications of graph theory in Business Management, and Management and Cost Accounting in Educational Management.