|
Article Excerpt
Each major US railroad ships millions of cars over its network annually. To reduce the intermediate handlings of shipments as they travel over the railroad network, a set of shipments is classified (or grouped together) at a railroad yard to create a block. The railroad blocking problem is to identify this classification plan for all shipments at all yards in the network to minimize the total shipment cost, i.e., to create a blocking plan. The railroad blocking problem is a very large-scale, multicommodity, flow-network-design and routing problem with billions of decision variables. Its size and mathematical difficulty preclude solving it using any commercial software package. We developed an algorithm using an emerging technique known as very large-scale neighborhood (VLSN) search that is able to solve the problem to near optimality using one to two hours of computer time on a standard workstation computer. This algorithm can also handle a variety of practical and business constraints that are necessary for implementing a solution. When we applied this algorithm to the data that several railroads provided us, the computational results were excellent. Three Class I railroad companies (a Class I railroad, as defined by the Association of American Railroads, has an operating revenue exceeding $319.3 million) in the United States--CSX Transportation, Norfolk Southern Corporation, and Burlington Northern and Santa Fe Railway--used it in developing their operating plans. Two US Class I railroads have also licensed it for regular use in developing their operating plans, and other railroads are showing considerable interest. We expect this algorithm to become an industry standard for freight railroads worldwide. In this paper, we outline our algorithm, show the computational results we received using real data, and describe areas for future research.
Key words: networks; network design; multicommodity flows; flow algorithms; heuristics; transportation; freight; railroad; blocking; integer programming; neighborhood search.
**********
Large freight railroads use their networks to carry millions of shipments from their origins to their respective destinations. Central to railroad operations is the operating plan that dictates the movement of shipments (railcar loads), crews, and locomotives over the railroad's network. Each railroad company has a service-design department that is responsible for creating operating plans to enable efficient movement of shipments. (Figure 1).
The blocking plan determines how to aggregate a large number of shipments into blocks of shipments as they travel from origins to destinations. Train scheduling consists of designing train routes, days of operation, timings, and routing of blocks on trains to minimize the total systemwide cost; this cost includes car hire, crew, and locomotive costs. An operating plan dictates the flow of three important railroad assets: crews, locomotives, and railcars, all of which consume billions of dollars in operating costs for Class I railroads. A well-designed operating plan can reduce these costs significantly.
Developing an operating plan that satisfies various operating constraints and business rules and, at the same time, uses the railcar, crew, and locomotive resources optimally, is a very challenging task. It requires several months of painstaking effort by a team of highly-experienced service designers. US railroads face a large-scale retirement of experienced personnel in the next five years. Thus, they are looking for (1) software tools to allow them to decrease their reliance on people to the maximum extent possible, and (2) a decision-support system (DSS) that will enable less-experienced service-design professionals to develop operating plans that can be implemented quickly. We developed algorithms, which we describe in this paper, to solve the railroad blocking and train-scheduling problems using leading-edge operations research techniques.
[FIGURE 1 OMITTED]
Railroad blocking is critical for railroads if they are to reduce their costs. For a major US domestic railroad, a typical general-merchandise shipment comprises a set of individual cars that all share a common origin and destination. A shipment may pass through many classification yards on its route from origin to destination. At these yards, the incoming shipment, which may consist of a number of individual shipments, is reclassified (sorted and grouped) for placement on outgoing trains. However, because the reclassification process is labor and capital intensive, it delays the movement of shipments. Therefore, to prevent shipments from being reclassified at every yard through which they pass, railroads group several shipments together to form a block. A block is associated with an origin-destination pair that may or may not be the origin or destination of any of the individual shipments contained in the larger group. These shipments are reclassified only after reaching the destination of the block. The objective of railroad blocking is to choose which blocks to build at each yard and to determine the sequences of blocks that deliver each shipment to minimize the total miles that the shipments travel and their intermediate handlings (or reclassifications).
The railroad blocking problem is essentially a consolidation problem, and its variants arise in several transportation sectors including postal and package-delivery companies, trucking companies, and the airline industry (Figure 2).
[FIGURE 2 OMITTED]
The post office at Gainesville (GNV) receives tens of thousands of envelopes each day for mailing to cities across the United States. GNV sorts (or consolidates) these envelopes into a small number of postal bags that are destined for different regions in the United States. For example, it may sort all envelopes headed for northeast United States into the mailbag headed for New York City (NY). Similarly, GNV may sort all the mail going to California into the mailbag destined for Los Angeles (LA). LA may receive several hundred mailbags from different cities in the United States, which it will open and resort into new mailbags. The LA post office may create a mailbag for Palo Alto (PALO), which will contain all the mail arriving at LA from several mailbags but destined for Palo Alto. The purpose of the sorting is to reduce the handling of envelopes. An envelope from GNV to PALO will be handled at its origin in GNV, its destination in PALO, and an intermediate location in LA. If envelopes are not sorted into mailbags, then they must be looked at in every city as they journey from origin to destination--a very inefficient and time-consuming process. Given the number of mailbags that arrive at each city, the US Postal Service (USPS) essentially faces two decisions: determining the destinations of these mailbags and determining how to route envelopes with different origin-destination pairs through these mailbags to minimize the systemwide transportation cost. The railroad blocking problem is identical to the sorting problem that the USPS faces; in the railroad context, envelopes are railcars, mailbags are blocks, and the sorting process is called classification or reclassification. In the Future Research Directions section, we describe similar problems in other areas of the transportation industry, and how our approach can be adapted to solve these problems.
Mathematically, the railroad blocking problem is a multicommodity-flow, network-design, and routing problem. To solve it, we need to design the underlying blocking network and to route different commodities (where each set of railcars with the same origin-destination pair of nodes defines a separate commodity) on the blocking network to minimize the systemwide transportation costs. Multicommodity-flow and network-design problems (Magnanti and Wong 1996, Kim et al. 1999, and Lederer and Nambimadom 1998) are among the most difficult combinatorial problems in operations research. When they consist of a few hundred design variables, we can solve them optimally. However, real-life blocking problems often contain over a million design variables and hundreds of billions of flow variables. Modeling and solving them using commercially available software is nearly impossible. In this paper, we describe a new algorithm to solve this problem using an emerging technique known as very large-scale neighborhood (VLSN) search. Our algorithm solves the problem to near optimality using one to two hours of computer time on a standard workstation computer. The algorithm is also very flexible and can handle a variety of practical and business constraints that are necessary if we are to generate a solution that can be implemented. When we applied this algorithm to the data that several railroads provided, we received excellent results. Three major freight railroad companies in the United States recently used it to develop their operating plans--CX Transportation (One Plan), Norfolk Southern Corporation (Top II Plan), and Burlington Northern Santa Fe (BNSF) Railway. In addition, Norfolk Southern Corporation and BNSF Railway have licensed it and several other railroads are showing keen interest. We expect this algorithm to become an industry standard for freight railroads worldwide.
In this paper, we outline our algorithm, give its computational results using real data, and describe how railroads are using it. We have organized the paper as follows. The Railroad Blocking Problem section presents a brief description of the blocking problem; the Literature Review section presents a brief literature review. A Very Large-Scale Neighborhood Search Algorithm for Blocking outlines the...
|
