مسدود کردن مشکل چند مسیری راه آهن با مدل بهبود یافته و الگوریتم کلونی مورچه در جهان واقعی

In rail freight transportation, general merchandise freight cars may pass through many classification stations on their route from origin to destination. The Railroad Blocking Problem (RBP) is to reclassify inbound traffic from various origins in the classification stations and put them on outbound trains with the same or close destinations, the objective of the RBP is to minimize the total operating costs of delivering all traffic on the railway network while satisfying the resource and capacity constraints at the stations and the priority constraints for shipments. In this paper, we introduce a new mathematic model which can comprehensively describe the blocking strategy and various combinations of multi-route O–D pairs in large scale railway network. Furthermore, we propose an improved Ant Colony (AC) algorithm for RPB, and a computational experiment derived from the real life instances of coal heavy haul rail network in north China is given. Experimental results verified the validation of the model and effectiveness of the algorithm

In railway industry, a general merchandise shipment may first be loaded into a railway car and then those cars with the same or close destination will be formatted into a train, this signals the beginning of the cars’ journey. Generally speaking, the modes of train operation are as follows: some cars will be operated into the mode of direct train to the destination with no reclassification in any marshalling stations, and the rest of the car will be operated into some other undirected-trains with the same direction and reclassified when they arrive some marshalling stations until they reach the destination. For undirected-trains, during this long haul part of the journey from Origin to Destination (OD), the cars may pass through several classification stations (marshalling stations). At each of these stations, this cars be taken as inbound traffic, and may be reclassified (sorted and grouped together) to be placed on another outgoing train, because some trains will be disassembled and vanished and some new trains will be generated in classification stations, the classification stations are also called railway terminals. Each time, once the cars are reclassified in the marshalling station, there will be one more converging time, and the converging process will be very time-consuming and complicated. Firstly, some train will be disassembled, and then there will be some processes for converging, that is, after disassembled and vanished, those dropped cars will be placed on the marshalling yard, until there are enough cars in the near classification track to format a new train in the same direction, since the requirements of weight and length of the train. The converging process is one necessary part in the reclassification process with great proportion, and each time in that process, lots of time that is called converging time will be spent into waiting. Therefore, the converging process cause the transportation delay for the shipment. The reclassification processes result in not only transporting delay for the shipment, but also waste of labor and capital, since construction and maintenance of large marshalling stations are expensive, many workers and large quantities of equipment are needed to handle the work. How to decrease the total reclassification number of all shipments is one of the key problems in railway operation planning policies. In this policy, many factors play an important role, such as the wagon flow structure, the wagon flow routing, the quantity of freight cars, and the capacity of the marshalling station and so on. When considering the wagon flow routing, “the shortest route” may mean the shortest path, may the shortest time or the most economic way. However, since the limit of the capacity of the station in the shortest route, part of the flow may go in another longer way. So the reasonable arrangement of the traffic flow is very important in the policy. To decrease the reclassification times of the shipments, several shipments are grouped together to form a block, once a shipment is placed in a block, it is not reclassified until it reaches the destination of that block. But how to decide which block should be built for marshalling stations and which blocks to use to deliver each commodity are the problems must be solved firstly, these sets of problems are called the Railroad Blocking Problem (RBP), and the solution of RBP is Train Blocking Plan (TBP), the objective of RBP is to develop a feasible TBP which minimize the total cost of delivering the commodities. The cost of the sum of delivering the commodities is usually considered as “car-handling” cost which is called “Converted Car-Hours (CCH)”. For the most past time, TBP had been evolved through incremental refinement of an existing plan by hand in China, these refinements are local in nature since they only considered the effects of changing a few number of blocks in the existing plan. The local incremental method has some obvious disadvantages, such as it may fail to get opportunities for improvement that require more significant changes to the current TBP, it may not be sophisticated enough to get the over-all optimal solution for large real life railway network. The RBP has been widely studied in the last few decades by railway engineers, both independently and in conjunction with other problems. Bodin, Golden, and Schuster (1980) proposed a large Mixed Integer Program (MIP) model with the nonlinear objective of minimizing the sum of the delays incurred during the reclassification. This model has an extremely large number of binary variables and solved by local searching with extensive manual intervention. Assad, 1980 and Assad, 1982 proposes an MIP formulation for routing and makeup based on a network model. His formulation decides which pairs of terminals should have direct train service between them. He also presents a branch-and-bound algorithm to find exact solution for small problems and a greedy search algorithm for comparatively large scale problems. Van Dyke (1986) presents the Automatic Blocking Model (ABM) micro-computer based system that became the heart of early blocking software marketed by ALK Associates, Inc. The ABM system developed a heuristic greedy algorithm to add blocks to an existing blocking plan. Haghani (1989) proposes an MIP with nonlinear objective to model the train routing and makeup decisions combined with empty car redistribution decisions and a heuristic method for solving it. Keaton (1992) proposes an Integer Programming (IP) formulation for deciding on blocking plan and the routings and frequencies of trains. He suggests a heuristic for solving the formulation and gets solutions with various constraints relaxed. Lin, Zhu, and Shi (1995) proposes an MIP for RBP and a simulated annealing based heuristic. David and Hualiang (1996) proposes neural network method to get a comparatively better solution for large scale RBP. Recardo, Marcus, and Oscar (2002) proposes an MIP of traffic flow and frequencies of trains for railway network. Newton, Barnhart, and Vance (1998) model the blocking problem as a network design model and formulate it as a mixed integer program. They develop column generation and branch-and-price algorithms to solve this problem. Barnhart, Jin, and Vance (2000) propose Lagrangian relaxation technique to decompose the problem in two sub-problems. Their approaches focus on determining a near-optimal solution. To summarize, most of the formulation of the RBP is Mixed Integer Program (MIP) model, and the algorithms developed to solve RBP either emphasize obtaining near-optimal solutions resulting in excessively high running times or suited only for small instances, and/or cannot handle real-life complexities of the blocking problems fast. There are some evolutionary meta-heuristics and have been developed for solving combinatorial optimization problems, but few were used to solve RBP. Through empirical studies with some of the well-known benchmarks, it has been identified that evolutionary meta-heuristics shows rapid convergence and consistency in performance. Recently Ant Colony (AC) algorithm have been successfully applied to various kinds of combinatorial optimization problems, the advantages of AC algorithm are not only robustness to control parameters and computational efficiency, especially for its simple concept, easy implementation to any scale of problems. In this paper, we give a new integer programming formulation of RBP combined with route choosing, and apply ant colony algorithm to solve it. The remainder of the paper is organized as follows: In Section 2, we present the model for multi-route RBP. In Section 3, we suggest an improved ant colony algorithm for RBP, experiments and application results are shown in Section 4, the conclusion and outlook for future studies are presented in Section 5.

The solution of RBP is one of the most important railroad basic plans and the difficulty to solving RBP precluded the development of automatic optimal algorithm. As a result, how to find a feasible better solution is the first step for many real-life railroads blocking problem. In this paper, we have discussed the model of multi-route RBP in detail, and then present an algorithm based on ant system, the computational results of this algorithm are very impressive. The AC algorithm successfully found the feasible better solution for RBP in very short time, for small scale RBP, AC algorithm also can find optimal solution easily shown as the example. For most large scale real-life RBPs, technicians currently solve this problem by making improvements from existing train blocking plan, it is efficient to generate a near-optimal solution for improving by AC algorithm. AC algorithm has a real potential to solve the blocking problem effectively and to be used in practice by railroads.