Freight car dispatching with generalized flows
Engels, Birgit and Schrader, Rainer
(2015)
Freight car dispatching with generalized flows.
Published in:
Networks Vol. 66 (1).
pp. 3339.
ISSN 10970037
This is the latest version of this item.
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 1to1 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 LPrelaxation 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.
Download: 
PDF (Rev. Version)
Download (276kB)  Preview 

Editorial actions:  View Item (Login required) 
ZAIK Number:  zaik2011618 

Depositing User:  Rainer Schrader 
Date Deposited:  03 Apr 2014 12:16 
Last Modified:  03 Nov 2015 13:00 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/778 
Available Versions of this Item

A Generalized Flow Network for Freight Car Dispatching. (deposited 17 May 2011 00:00)
 Freight car dispatching with generalized flows. (deposited 03 Apr 2014 12:16) [Currently Displayed]