Elsevier

Applied Soft Computing

Volume 11, Issue 2, March 2011, Pages 1899-1907
Applied Soft Computing

Using simulated annealing for determination of the capacity of yard stations in a railway industry

https://doi.org/10.1016/j.asoc.2010.06.006Get rights and content

Abstract

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. We 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. To tackle this problem, 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. The proposed approach is applied to an example problem and is shown to be successful, ultimately providing a new managerial tool for planning and analyzing yard capacity more effectively.

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)

  • R. Freling et al.

    Shunting of passenger train units in a railway station

    Transportation Science

    (2005)
  • R.M. Lentink et al.

    Applying operations research techniques to planning of train shunting

    Technical Report ERS-2003-094-LIS

    (2003)
  • N. Tomii et al.

    An algorithm for station shunting scheduling problems combining probabilistic local search and PERT

  • N. Tomii et al.

    Depot shunting scheduling using combined genetic algorithm and PERT

  • A. Cardol, M. Fledderus, Opstellen: prognose op basis van Referentie 2010 (Parking: forecast on the basis of Referentie...
  • A. Marin, J. Salmeron, A heuristic method for the tactical planning in the design problem for railroad freight...
  • Cited by (19)

    • R-GWO: Representative-based grey wolf optimizer for solving engineering problems

      2021, Applied Soft Computing
      Citation 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 Management
      Citation 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 Review
      Citation 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 Technologies
      Citation 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.

    View all citing articles on Scopus
    View full text