Universität zu Köln

Engels, Birgit and Schrader, Rainer ORCID: 0000-0001-6635-0132 (2015). Freight car dispatching with generalized flows. Networks, 66 (1). S. 33 - 40. HOBOKEN: WILEY-BLACKWELL. ISSN 1097-0037

Full text not available from this repository.

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. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 33-39 2015

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Engels, Birgit UNSPECIFIED UNSPECIFIED UNSPECIFIED Schrader, Rainer UNSPECIFIED orcid.org/0000-0001-6635-0132 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-398407
DOI:	10.1002/net.21603
Journal or Publication Title:	Networks
Volume:	66
Number:	1
Page Range:	S. 33 - 40
Date:	2015
Publisher:	WILEY-BLACKWELL
Place of Publication:	HOBOKEN
ISSN:	1097-0037
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language TRAIN TIMETABLING PROBLEM; FLEET MANAGEMENT; EMPTY; OPTIMIZATION; CONTAINERS; OPERATIONS; ALLOCATION; ALGORITHM; MODELS; SCALE Multiple languages Computer Science, Hardware & Architecture; Operations Research & Management Science Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/39840