| The routing of traffic is a major logistical concern for transportation services. For railroads, routing has historically been handled by large, hard-coded tables. Norfolk Southern Railways developed a more sophisticated routing system that takes advantage of network flow theory. Their Algorithmic Blocking and Classification (ABC) system routes traffic commodities (or waybills) according to shortest paths. The routing of multiple waybills is a form of the Multicommodity Flow Problem (MCFP).; Since routes for commodities are still often predetermined, the success of ABC relies on finding costs that make the desired routes optimal in terms of shortest paths. The problem of finding costs to make a solution optimal is called inverse optimization. The procedure of finding an adequate set of costs for the ABC system is known as calibration and is a form of the Inverse Multicommodity Flow Problem (IMCFP).; ABC calibration seeks a solution that makes all predetermined paths uniquely optimal with respect to the costs. Such a solution does not always exist. Conflicts between the routing preferences of different waybills reflect inconsistencies that prevent all waybills from being routed as desired based strictly on costs. Simple conflicts, which exist between exactly two waybills, are easy to detect and eliminate. However, there are complex conflicts that pose a more difficult problem. We cover methods for dealing with both types of conflicts.; Once conflicts are eliminated, the problem (IMCFP) can be solved optimally using the simplex method. We present formulations, specialized pivoting rules, and a hot start basis-finding algorithm for deriving optimal solutions. In addition, we can use Lagrangian relaxation to find heuristic solutions when optimality is not required or computationally feasible.; Once a feasible solution to (IMCFP) is found, it is possible that routing preferences and the system's costs will change. Altering costs to achieve specified traffic flows and predicting the effects of costs changes on existing routes can be computed or estimated using sensitivity analysis. A large number of commodities with different feasible networks can make sensitivity analysis difficult. Applying standard techniques to networks aggregated by common attributes, we propose a framework for sensitivity analysis of complicated networks. |
