Classical Approximation to Networks of Nonstandard Reachability in Relation to Locomotive Assignment Problem

摘要

The authors consider locomotives assignment to trains [1], [2] in order to provide train schedule fulfilment with optimal resource utilization. When applying the maximum network flow [3] method to the task of connecting locomotives to trains [4] the edges of the network have a complex selective permeability, which leads to the non-classical case of the problem of convergence of the solution to a global minimum. Nevertheless, it is possible to avoid stacking of the solution in local extrema by using the analogy with the classical case. The analogy is observed when pushing back the resource along the edge occupied by another resource. In this case, the route of the old resource is cut along the current edge, and its final part transforms into an addition to the route of the new resource. As a result, it is possible to obtain a significant gain in the number of locomotives employed in the delivery of trains, while maintaining, or an insignificant decrease in the total number of trains delivered.