Using simulated annealing for determination of the capacity of yard stations in a railway industry
Introduction
Railway is the most environmentally friendly and fuel efficient mode of freight transportation. Rail yards serve as reservoirs for the main lines absorbing and redistributing rail cars to their final destinations. Yards are owned by the railroads and are used to build outbound trains, break down inbound trains, and classify inbound cars for assignment to outbound trains for through traffic. Yards can offer refueling, crew change, storage, and maintenance functions. Given these key roles in the rail network, a significant amount of rail system capacity is determined by the capacity of the yards that connect the mainline corridors. Capacity of a rail yard station is the ability of a yard to receive, process, and dispatch the freight cars. The number of operations on the railcars that can occur simultaneously within a yard is directly related to the rail capacity of the yard. The estimation of a rail yard's capacity is a key task in the overall yard design process. Any improvement in the operations done in a rail yard can lead in a considerable improvement in the railways planning.
This paper is organized as follows. Section 2 provides a brief literature review summarizing the current state of the art and highlighting deficiencies that the proposed work responds to. The mathematical model for the problems is detailed in Section 3, in the form of an optimization formulation. This includes a thorough discussion of the design variables, the objective functions, and the constraints. In Section 4 a simulated annealing (SA) algorithm is proposed to solve the model. Section 5 provides an example problem with extensive discussion of the results. In Section 6 describes some experiments designed to test the convergence behavior of the solution procedure. Finally, Section 7 summarizes the primary contributions, discussion broader implications of the work, and itemizes potential areas for future work.
Section snippets
Literature review
Due to the complexity of yard operations and management, a rail-yard operations planning and management tool to support yard capacity and improvement studies is needed. A yard capacity study is to assess how many cars, blocks and trains can be handled with the existing infrastructure and resources. Rail yard improvement studies may include infrastructure improvement (e.g., adding a new track or crossover), resource requirements (e.g., number of yard engine and crews), and capability to handle
The mathematical model
We assume that the planning horizon (T) has been divided into discrete “decision periods” and use t to denote one such period. A set of the network locations is denotes by N which is divided to two subsets of N1 and N2 with respect to the origin and destination points in the network.
Solution procedure
A simulated annealing (SA) algorithm is proposed to solve the model which works efficiently on a neighborhood search within solution space, acceptance probability, and inferior solutions to escape from trap. Simulated annealing was first introduced as an intriguing technique for optimizing functions of many variables [31]. Simulated annealing is a heuristic strategy that provides a means for optimization of NP complete problems: those for which an exponentially increasing number of steps are
Problem description
In this section, we demonstrate the use of the approach in Section 4 to solve the problem in Section 3. This example includes three rail-yard origins and three rail-yard destinations (N1 = 2 and N2 = 2) on a 6-day planning horizon. Therefore, the proposed mathematical model was solved using the SA algorithm on a hypothetical network with four origins, four destinations over a 6-day planning horizon with starting temperature equal to 1000 (see formula (15)), final temperature 0.05, cooling rate 0.99(
Results
In this section we report on experiments designed to test the convergence behavior of our solution procedure. Therefore, to test the efficiency and validity of the SA algorithm in comparison with optimal ones, we solved nine small-size instances with LINDO 8 software using branch-and-bound (B&B) according to Table 4. We find out that large-sized problems (say, i > 6, j > 6, t > 8) cannot be optimally solved within a reasonable computational time (say, less than 2 h). Table 5 presents the computational
Conclusion
This paper has presented a multi-periodic optimization formulation and a solution procedure for yard capacity problems. This approach is novel in that it incorporates the following capabilities into one analysis tool: (1) the newly developed model provides network information, such as yard capacity, unmet demands, and number of loaded and empty rail car at any given time and location. Consequently, the model provides a tool for helping managers with planning and decision-making. (2) Simulated
References (32)
- et al.
A simulated annealing approach for the multi-periodic rail-car fleet sizing problem
Computers and Operations Research
(June 2009) - et al.
Solving a multi periodic stochastic model of the rail-car fleet sizing by two-stage optimization formulation
Applied Mathematical Modeling
(2010) - et al.
Multi commodity, multimode freight transportation: a general modeling and algorithmic framework for the service network design problem
Transportation Research Part B
(1986) A general system theory approach to rail freight car fleet size
European Journal of Operational Research
(2002)- et al.
Optimal empty vehicle repositioning and fleet-sizing for two-depot service systems
European Journal of Operational Research
(2008) - et al.
Hierarchical mixed initiative planning support
- et al.
Does task follow structure domain representations and task execution of human planners at the Dutch railroads
Technical Report
(2003) - W.M.C. Van wezel, R.J.J.M. Jorna, Tracing cognition, tasks and support: shunting support in the Netherlands Railways...
- et al.
Train shunting: a practical heuristic inspired by dynamic programming
Technical Report
(2005) - et al.
Optimal train scheduling in presence of track circuits
Shunting of passenger train units in a railway station
Transportation Science
Applying operations research techniques to planning of train shunting
Technical Report ERS-2003-094-LIS
An algorithm for station shunting scheduling problems combining probabilistic local search and PERT
Depot shunting scheduling using combined genetic algorithm and PERT
Cited by (19)
Optimization of fleet size and determining the optimal allocation of wagons in minerals transport network: A case study of Iran's railway system
2023, Journal of Rail Transport Planning and ManagementDesigning intelligent public parking locations for autonomous vehicles
2023, Expert Systems with ApplicationsR-GWO: Representative-based grey wolf optimizer for solving engineering problems
2021, Applied Soft ComputingCitation Excerpt :The nature-inspired algorithms imitate the biological concepts and physics rules by which a wide variety of effective algorithms has been introduced such as genetic algorithm (GA) [2], differential evolution (DE) [3], particle swarm optimization (PSO) [4], ant colony optimization (ACO) [5], gravitational search algorithm (GSA) [6], and charged system search (CSS) [7]. The nature-inspired algorithms are popular because they are simple to implement but still powerful to solve different problems [8–12]. In contrast to these advantages, they may suffer from low ability of exploration and exploitation, imbalance between them and low diversity [13,14].
An intelligent social-based method for rail-car fleet sizing problem
2021, Journal of Rail Transport Planning and ManagementCitation Excerpt :Numerous models for rail-car fleet management have been assumed that parameters are deterministic. Javadian et al. (2011) introduced a static optimization problem to consider the capacity of rail-yard stations regarding the optimal number of shunting yard nodes and re-classification rail freight cars operation. However, stochastic rail-car allocation problems are fundamentally different from deterministic problems.
A stochastic model predictive control to heterogeneous rail freight car fleet sizing problem
2015, Transportation Research Part E: Logistics and Transportation ReviewCitation Excerpt :The Pareto optimal set is depicted and used for a trade-off analysis. Javadian et al. (2011) developed an optimization formulation and a solution procedure for the determination of the capacity of rail yard stations with respect to the optimal number of shunting and reclassification operations at the nodes of the rail network. The model was analyzed with respect to one type of rail cars.
A fuzzy random model for rail freight car fleet sizing problem
2013, Transportation Research Part C: Emerging TechnologiesCitation Excerpt :The Pareto optimal set is depicted and used for a trade-off analysis. Javadian et al. (2011) develop an optimization formulation and a solution procedure for the determination of the capacity of rail yard stations with respect to the optimal number of shunting and reclassification operations at the nodes of the rail network. The model has been analyzed with respect to one type of rail cars.