EFFICIENT MODELS FOR CONTEMPORARY RAILWAY FREIGHT OPERATIONS
AMIT UPADHYAY
DEPARTMENT OF MECHANICAL ENGINEERING INDIAN INSTITUTE OF TECHNOLOGY DELHI
FEBRUARY 2015 APRIL 2016 APRIL 2016 APRIL 2016
©Indian Institute of Technology Delhi (IITD), New Delhi, 2016
EFFICIENT MODELS FOR CONTEMPORARY RAILWAY FREIGHT OPERATIONS
by
AMIT UPADHYAY
Department of Mechanical Engineering
Submitted in fulfilment of requirements for the degree of Doctorate of Philosophy
to the
INDIAN INSTITUTE OF TECHNOLOGY DELHI APRIL 2016
i
CERTIFICATE
This is to certify that the thesis entitled “EFFICIENT MODELS FOR CONTEMPORARY RAILWAY FREIGHT OPERATIONS” submitted by Amit Upadhyay to the Indian Institute of Technology Delhi for the award of the degree of Doctor of Philosophy is a record of original research work carried out by him. He has worked under my supervision and has fulfilled the requirements for submission of this thesis, which to my best knowledge has reached the requisite standard.
The results contained in this thesis have not been submitted, in part or full, to any other university or institute for the award of any degree or diploma.
Dr. Nomesh Bolia Associate Professor
Department of Mechanical Engineering,
Indian Institute of Technology Delhi, New Delhi, India 11-April-2016
ii
ACKNOWLEDGEMENTS
I would like to express my heartfelt thanks to my PhD supervisor Dr. Nomesh Bolia for his guidance, encouragement and support throughout this research work. I am thankful to my ex- supervisor Late Prof. Arun Kanda who guided me not only in the research but also in personal life. I am grateful to my teachers Prof. S. G. Deshmukh, Prof. Kiran Seth, Prof. A.
D. Gupta and Dr. M. S. Kulkarni for their valuable suggestions, research review and personal guidance.
I must thank our industry collaborators for providing all the information and support during my visits to the railway terminals and seaports and for partial funding support.
I am grateful to my teachers Prof. P. L. Dhar, Prof. M. R. Ravi and Prof. Sangeeta Kohli for invaluable motivation, support and guidance, which helped me to get through some difficult times. I am thankful to Prof. S. K. Saha and Prof. P.M.V. Subbarao for their kind support during my stay in IITD.
I express my thanks to my colleagues Vedpal, Avinash Samvedi, Gajanan Panchal, Umang Soni, Sumit Sakhuja, Umesh Khandey, Ashish Purohit and Piyush Shakya for sharing elite moments during my research work. I am thankful to all of my Industrial Engineering friends for making my IIT days a pleasant experience.
My parents and my wife deserve special mention for their love, support and prayers. Finally, I would like to thank everyone, who contributed and supported for the successful realization of this thesis.
iii
ABSTRACT
Rail transport contains a rich set of Operations Research problems with significant potential financial gains. Despite significant research in past few decades, optimization models are rarely used in practice in Indian Railways due to the large network size and complexity of the problems. The motivation for this research comes from the practical problems arising in the rail freight transport on the existing network as well as on the upcoming dedicated freight corridors (DFC) in India.
The aim of this thesis is to study the following three important real-life optimization problems in the rail freight transport. First, an integrated optimization for empty rake distribution and train scheduling on DFC is studied. Second, a novel optimization problem ‘multi-point accompanied combined transport service design’ is introduced and analyzed. Third, an optimization based decision support system is developed for the maximization of double stack container trains loading.
The focus of this thesis is on the mathematical modelling of these independent problems. The solution approaches developed for these problems are based on heuristics, efficient problem formulation and the CPLEX optimizer. For the first two problems, the computational experiments are performed on realistic instances based on the data from Indian Railways, Konkan Railway and Dedicated Freight Corridors Corporation of India Ltd. The model and decision support system developed for the third problem have been tested and validated successfully with real data and scenarios. This optimization based DSS has been accepted and being deployed by a container train operator. The results show that the expected saving due to the optimal container loading through the decision support system will be about INR 200 million per year. The results for the first two
iv
problems also show that the models and solution approaches developed are practically implementable and capable of making rail freight operations more efficient.
v TABLE OF CONTENTS
Certificate i
Acknowledgement ii
Abstract iii
Table of contents v
List of figures ix
List of tables xi
List of abbreviations xii
List of notations xv
Chapter 1: Introduction 1-12
1.1 About Indian Railways 1
1.2 Need for Dedicated Freight Corridors 2
1.3 Motivation 4
1.4 RORO transport 6
1.5 Double stack container trains 8
1.6 Research problem and objectives 9
1.7 Organization of thesis 11
Chapter 2: Literature review 13-28
2.1 Railway Planning Problems 13
2.2 Intermodal Freight Transport Planning Problems 24
2.3 Research gaps 27
2.4 Conclusion 28
Chapter 3: Combined empty and loaded train scheduling for dedicated freight railway corridors
29-79
3.1 Introduction 29
3.2 Learning from the literature review 32
vi
3.3 Problem description 33
3.4 Solution Methodology DIASP 41
3.5 Computational Experiments DIASP 48
3.6 Mathematical Formulation of Multicommodity DIASP 51
3.7 Complexity of the Problem 55
3.8 Solution Methodology for MDIASP 56
3.9 The Decision Support System 60
3.10 Computational Experiments and Analysis 65
3.11 Conclusion 78
Chapter 4: An optimization based approach for roll-on-roll-off combined transport service design with multiple handlings
81-117
4.1 Introduction 81
4.2 Research Gaps 84
4.3 Problem description and analysis 85
4.4 Computational experiments and analysis 106
4.5 Conclusion 117
Chapter 5: Optimization based decision support system for double stack container trains loading
119-154
5.1 Introduction to double stack container operations 119
5.2 Learning from the literature review 120
5.3 Problem Description 121
5.4 Problem analysis and solution approach 134
5.5 Decision support system: A case of an Indian CTO 141
5.6 Computational Experiments 147
5.7 Conclusion 154
Chapter 6: Conclusion and scope for future work 155-162
6.1 Salient contributions of the research 156
6.2 Managerial implications of the research 158
vii
6.3 Limitations and future Scope 160
References 163-178
Appendix A: A sample of optimal train summary report 179
Appendix B: Glossary 183
Appendix C: List of Publication based on this work 187 Appendix D: Biographical Profile of Researcher 188
ix
LIST OF FIGURES
Figure No. Title of the Figure Page No.
1.1 Growth of rail freight traffic in India 2
1.2 Eastern Dedicated Freight Corridors 3
1.3 Western Dedicated Freight Corridors 4
1.4 RORO train service in Konkan Railway 6
1.5 Freight traffic share in India 7
1.6 Global container throughput in million TEU 8
1.7 Double-stack container train 9
3.1 Illustrative network explaining the DIASP 37
3.2 Constructive heuristic for feasible solution 44
3.3 Simulated Annealing Flow Chart 47
3.4 Comparison of operations planning framework for railroads 59
3.5 Overview of the DSS architecture 61
3.6 Effect of number of rakes on performance measures 73
3.7 Effect of time discretization on runtime 77
3.8 Effect of time discretization on optimality gap 78
4.1 LIFO constraints in RORO service design 87
4.2 Train size consideration in RORO service design 91 4.3 Illustrative network defining services and blocks 93
4.3 Illustrative RORO railway network 102
4.4 Illustrative example of rake linking 105
4.5 Operations planning framework for RORO services 106 4.6 Diminishing returns – effects of number of rakes on OFV 112
x
4.7 Effects of number of potential services on OFV 114
4.8 Effects of maximum train size limit on the OFV 116
5.1 Scope of DSLP at a seaport 120
5.2 Double stack container patterns 122
5.3 Container positions in the double stack loading patterns 123 5.4 Illustrative network with single-stack and double-stack
movement feasibility
130
5.5 Double-stack patterns without big constant M1 135
5.6 DSLP DSS architecture 142
5.7 Double Stack Loading Planner (second window) 145
xi
LIST OF TABLES
Table No. Title of the Table Page No.
2.1 Characteristics of rail wagon management models 17
2.2 Survey of Operations Research in intermodal transport 24 3.1 Performance of the heuristic and CPLEX for small instances 50 3.2 Performance of the heuristic for real-life size problem instances 50
3.3 Database for the DSS 63
3.4 MDIASP (line capacity relaxed) computational experiments on CPLEX 70 3.5 Sensitivity analysis of capacity building at a bottleneck yard 75
3.6 Sensitivity analysis of train speed 76
4.1 Computational results for MRSDP 109
5.1 Actual v/s optimal loading (same 180 TEUs assigned to the same train)
150
5.2 Actual loading of trains from PORTX for DESTX on Day 9th 151 5.3 Optimal loading of trains from PORTX for DESTX on Day 9th 151 5.4 Actual loading of trains from PORTX for DESTX on Day 10th 152 5.5 Optimal loading of trains from PORTX for DESTX on Day 10th 152
xiii LIST OF ABBREVIATIONS
ACT Accompanied combined transport CRIS Centre for Railway Information Systems CONCOR Container Corporation of India Ltd CTO Container Train Operator
CTOX The CTO who partially funded this research, but cannot be named here.
DF Deficit Function
DFC Dedicated Freight Corridors
DFCCIL Dedicated Freight Corridors Corporation of India Ltd.
DIASP Dynamic Integrated Empty Allocation and Scheduling Problem DSLP Double Stack Loading Problem (optimization model)
Double Stack Loading Planner (decision support system based on the optimization model). Use of these words is clear from the context.
DSS Decision Support System FEU Forty-foot equivalent unit FIFO First in first out
FOIS Freight Operation Information System HQ High Cube (container with height 9′ 6″) ICD Inland Container Depot
IP Integer Programming
IR Indian Railway
IRCTC Indian Railways Catering and Tourism Corporation
xiv
ISO International Organization for Standardization;
International Standard (container with height 8′6″) LIFO Last in first out
LPP Linear Programming Problem
LRDSS Long Range Decision Support System
MDIASP Multicommodity Dynamic Integrated Empty Allocation and Scheduling Problem
MILP Mixed Integer Linear Program MIS Management Information System NDP Network Design Problem
OCC Operations Control Centre OD Origin Destination (pair) ODR Oldest date of registration OFV Objective Function Value
RDSO Research, Design & Standards Organisation RMG Rail Mounted Gantry
RORO Roll on roll off RTG Rubber Tyred Gantry SA Simulated Annealing TDP Train Dispatching Problem TEU Twenty-foot equivalent unit
xv LIST OF NOTATIONS
The list of notations is organized below separately for each of the three problems studied in this thesis.
Notations used in Chapter 3
Eij transportation cost of an empty rake from yard i to j
Fij profit (revenue minus cost) from moving a loaded rake from yard i to i Gij penalty cost per period per unit of unmet demand from i to j
loading time (in number of periods) for a rake
unloading time (in number of periods) for a rake
ij average travel time (in number of periods) for a train between yards i and j CLi loading capacity at yard iY (in number of rakes per period)
CUi unloading capacity at yard iY (in number of rakes per period) Ca flow capacity of arc a (in number of rakes per period) ya source yard (location) wherefrom the arc a originates ta time period to which the arc a belongs
SEi number of rakes available at yard i initially (at t=0)
a set of all directed paths that traverse the directed arc a
eij(t) number of empty rakes dispatched from yard iY to jY in period t
xvi
fij (t) number of loaded rakes dispatched from yard iY to jY in period t
gij(t) number of demands backordered for transportation from yard i to j in period t Ow set of source yards for wagon type w; Ow Y
Dw set of destination yards for wagon type w; Dw Y ODw tuple set of OD yards for wagon type w; ODw Y Yw set of all relevant yards for wagon type w; Yw = DwOw
Notations used in Chapter 4
b Index for blocks (demands), bB s Index for potential train services, sS a Index for arcs (track sections), aA B Set of blocks {OD}
S Set of all the potential train services {OD}, S B
Bs Set of blocks that can be assigned to the train service sS, Bs B A Set of arcs (track sections) in the railway network
As Set of arcs (path) traversed by the train sS, As A Ba Set of blocks traversing the arc aA
Q Set of all the conflicting block-pairs due to LIFO (iB, jB)
xvii Nb Demand in block bB (in number of wagons) L Minimum number of wagons per train
U Maximum number of wagons per train
Total number of rakes available
Hs Maximum number of handling points allowed for train sS Pbs Profit from a truck in block bB if it is assigned to train sS Fs Fixed cost of running train sS (Rs. per train)
ys Binary design variables, equal to 1 if the train with the first block sS is formed, zero otherwise
xbs Binary assignment variables, equal to 1 if block bBs is assigned to train sS, zero otherwise
zbs integer assignment variables, number of trucks of block bBs assigned to train sS
Notations used in Chapter 5
I set of containers; index i I
I20 , I40 set of 20 ft and 40 ft containers; I20 I, I40 I
|I20| , |I40| number of containers in I20 , I40 respectively K set of DS wagons; index k
xviii
|K| number of wagons in K
20C, 40C
I I sets of compulsory containers that must be railed immediately
S set of shipping bills with a special request to send all the containers together
20s , 40s
I I sets of containers in the shipping bill sS Wi gross weight of the ith container, i I W w tare weight of a DS wagon
H c height of the interbox twist-lock
H P height of the platform of DS wagon from rail surface
HA, HC, HF height of the container lying in the respective position A, C, F as in Figure 5.4 WA, WC, WF Weight of the container lying in the respective position A, C, F as in Figure 5.4
H w center-of-gravity (CG) height of an empty DS wagon from the rail surface P maximum payload limit allowed for a loaded double-stack wagon
H maximum C.G. height limit allowed for a loaded double-stack wagon
Wd maximal allowed weight difference between two 20 ft loaded on the same wagon Ti Time of booking of container, i I
20-40 imbalance factor
L
Pi Profit from assignment of ith container to lower stack
U
Pi Profit from assignment of ith container to upper stack
OD Tuple set of the relevant OD of the containers (used for single-stack train planning) M1, M2 Large value constants
40
NF number of 40s fit for assignment in the position F
xix Binary Decision variables
1
xk if kth wagon is assigned loading pattern-1, x1k=1, else x1k=0; k K
2
xk if kth wagon is assigned loading pattern-2, xk2=1, else xk2=0; k K
3
xk if kth wagon is assigned loading pattern-3, x3k=1, else xk3=0; k K
4
xk if kth wagon is assigned any other pattern, x4k=1, else xk4=0; k K y ik if ith 20 ft container is loaded on the kth wagon, y =1, else ik y =0; ik i I20
A
yik if ith container is loaded on position A of kth wagon, yikA=1, else yikA=0; iI20
B
yik if ith container is loaded on position B of kth wagon, yikB=1, else yikB=0; iI20 C
yik if ith container is loaded on position C of kth wagon, yikC=1, else yikC=0; iI20
D
yik if ith container is loaded on position D of kth wagon, yikD=1, else yikD=0; iI20
z ik if ith 40 ft container is loaded on the kth wagon, z =1, else ik z =0; ik iI40 E
zik if ith container is loaded on position E of kth wagon, zikE=1, else zikE=0; iI40 F
zik if ith container is loaded on position F of kth wagon, zikF =1, else zikF=0; iI40 bs if all the containers Ns are railed together, bs =1, else bs =0 ; sS
blod binary variable for selection of containers in the lower-stack; od OD buod binary variable for selection of containers in the upper-stack; od OD H CG height of a loaded wagon (intermediate decision variable)
