Integer Programming for Amtrak Train Fuel and Blocking Optimization

Introduction to the Amtrak Blocking Problem

The objective of this project is to use mathematical solution methods to solve problems facing Amtrak trains. One of the central problems facing Amtrak is the railroad blocking problem, which causes a constant increase in fuel costs and creates challenges in the allocation of scarce resources, ultimately reducing profitability. This paper uses integer programming to solve the blocking problem facing the company. Typically, blocking determines the train schedule, which in turn determines major resource costs such as car costs, locomotive costs, crew costs, and yard operating costs. Solving the blocking problem facing Amtrak trains to near optimality is critical to the efficiency of the company's operations.

The integer programming model used to solve the blocking problem is formulated as follows:

Minimize:

∑_k∈K ∑_(i,j)∈A c_ij x^k_ij + ∑_i∈N ∑_(i,j)∈O(i) h_i y_ij

Integer Programming Formulation

Subject to:

∑_(i,j)∈O(i) x^k_ij − ∑_(i,j)∈I(i) x^k_ij = v^k if i = o(k); = 0 if i ≠ o(k) or d(k); = −v^k if i = d(k)    for all k ∈ K

∑_k∈K x^k_ij ≤ u_ij y_ij    for all (i, j) ∈ A

∑_(i,j)∈O(i) y_ij ≤ b_i    for all i ∈ N

∑_k∈K ∑_(i,j)∈I(i) x^k_ij ≤ d_i    for all i ∈ N

y_ij ∈ {0, 1} and x^k_ij ∈ {0, v^k}

The railroad blocking model is built on the following constraints and objective components:

Network Analysis and Linear Programming

Constraints:

Objective Function components:

The US railroad blocking problem is characterized as follows: a routing problem and multi-commodity flow network design with 3,000 nodes, 50,000 commodities, over one million 0-1 network design variables (y_ij), hundreds of billions of integer flow variables (x^k_ij), and substantial costs — cost of flow: $1,000–$2,000 million; cost of handling: $500–$1,000 million.

This paper also uses network analysis and linear programming algorithms to address Amtrak's operational problems. The decision variables considered are as follows:

Additional constraints include yard capacity constraints, line capacity constraints, train capacity constraints, and applicable business rules. The train schedule design problem links shipments to block assignments, crew balance and assignment, and locomotive balance and assignment. The railcar, crew, and locomotive are the three resources maintained across time-space networks.

The weekly scale of the problem is substantial:

Integer programming is a mathematical technique concerned with the allocation of scarce resources to the best advantage of an organization. Linear programming is a procedure that assists an organization in optimizing value by reducing costs and maximizing profits. Allocation problems focus on the utilization of scarce resources in the most advantageous way possible. Within the contemporary business environment, resource allocation decisions to cut costs and enhance profitability are a primary management concern.

One of the major problems facing Amtrak is its inability to allocate track capacity to achieve optimal cost reduction in fuel. The company also faces management challenges in addressing optimization problems, and real-time rescheduling issues have caused overall company expenses to consistently exceed total revenue. Mathematical models and optimization techniques are effective tools for assisting Amtrak in achieving cost reduction and service improvement.

The paper develops integer programming based on a microscopic model. The governing equations are defined as follows:

Conclusion

Using the integer programming based on the microscopic model, Amtrak will be able to manage energy consumption to the company's advantage.

This paper attempts to solve the problems facing Amtrak trains using various mathematical tools, including integer programming, optimization techniques, and network analysis. The integer programming results reveal that the company will be able to achieve significant savings in operating costs by addressing the blocking problem and rescheduling its operations to best advantage. The decline in operating costs is projected to create meaningful value for the company, and the optimization-based approach demonstrates a substantial improvement pathway for railroad management overall.

Gély, L., Dessagne, G., and Lérin, C. "Train Re-scheduling Modeling with Operational Research and Optimization Techniques: Results and Applications at SNCF." SNCF Innovation and Research Department, 2008.

Semet, Y., and Schoenauer, M. "An Efficient Memetic, Permutation-Based Evolutionary Algorithm for Real-World Train Timetabling." The Journal, vol. [Volume], 2005, pp. 110–120.