Freight car dispatching with generalized flows

Freight car dispatching with generalized flows

0.00 Avg rating0 Votes
Article ID: iaor201526399
Volume: 66
Issue: 1
Start Page Number: 33
End Page Number: 39
Publication Date: Aug 2015
Journal: Networks
Authors: ,
Keywords: scheduling, combinatorial optimization, graphs, programming: linear
Abstract:

In the freight car dispatching problem, empty freight cars have to be assigned to known demands respecting a given time horizon and certain constraints. The goal is to minimize the resulting transportation costs. One of the constraints is that customers can specify the type of cars they want. It is possible, however, that cars of certain types can be substituted by other cars, either in a 1‐to‐1 fashion or at different exchange rates. We show that these substitutions make the dispatching problem hard to solve and hard to approximate. We model the dispatching problem as an integral generalized transportation problem on a bipartite graph. Using rounding techniques, the LP‐relaxation can be transformed to a transportation schedule violating some of the constraints slightly. Under an additional assumption on the cost function, we fix this violation and derive a 4‐approximation of the problem.

Reviews

Required fields are marked *. Your email address will not be published.