Engels, Birgit
(2011).
A Generalized Network Model for Freight Car Distribution.
PhD thesis, Universität zu Köln.
![[img]](https://kups.ub.uni-koeln.de/style/images/fileicons/application_pdf.png)
|
PDF
Thesis_EngelsBirgit_AGeneralizedNetworkModelForFreightCarDistribution.pdf - Published Version Download (2MB) |
Abstract
We consider the empty freight car distribution problem (DP) at DB Schenker Rail Deutschland AG under a wide range of application relevant constraints and real data sets. The (DP) is an online assignment problem between geographically distributed empty freight car supplies and customer demands for such cars in preparation of good transport. The objective is to minimize transport costs for empty cars while distributing them effectively with respect to the constraints. In our case, one major constraint is given by prescheduled freight trains: obviously a supply can only be assigned to a demand if it reaches the latter in time. Further, the variety of goods (bulk cargo, steel coils, etc.) to be transported requires distinct types of freight cars. Freight cars of a certain type can be exchanged by cars of other types with respect to a given substitution scheme and different 'exchange rates'. Allowed substitutions are therefore another major constraint of the (DP). We describe further `hard' and `soft' constraints and sketch the current work flow at DB Schenker Rail Deutschland AG to find an adequate solution for the (DP) on a daily base in practice. The (DP) is currently solved separately for groups of car types and in several steps. Moreover, some steps contain manual pre- and post-processing to ensure certain constraints. Hence global sub-optimal distributions can occur. We therefore integrate all constraints into a generalized network flow model for the (DP). A global optimal distribution is then provided by an integral minimum cost flow in the network. To find such a flow is NP-hard in general. We show that a general substitution scheme makes our notion of the (DP) also NP-hard. Hence independent of the applied model and with respect to practical runtime requirements, we have to find a compromise between solution time and quality. We do so in two ways. Instances of the (DP) which correspond to classical flow networks are solved by an integral minimum cost flow, which can be obtained in polynomial time. We use such instances to polynomially obtain minimum cost flows of fixed bounded fractionality for certain general instances. For those instances occurring in the application we obtain half-integral flows, which can be rounded to approximate or heuristic distributions in linear time. Moreover, we develop a network-based reoptimization approach, which yields optimal solutions for subsequent instances with few changes very fast. This thesis was inspired and funded by a 2-year research and development project of DB Schenker Rail Deutschland AG in cooperation with the work group Faigle/Schrader of the University of Cologne and the work group of Prof. Dr. Sven O. Krumke at the Technical University of Kaiserslautern. The project included the implementation of the generalized network model and the reoptimization, approximation and heuristic methods. The software is designed as a future optimization kernel for the (DP) at DB Schenker Rail Deutschland AG.
| Item Type: | Thesis (PhD thesis) | ||||||||
| Translated title: |
|
||||||||
| Translated abstract: |
|
||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-42621 | ||||||||
| Series Name: | Informatik | ||||||||
| Date: | June 2011 | ||||||||
| Publisher: | Dr. Hut Verlag München | ||||||||
| ISBN: | 978-3-86853-991-2 | ||||||||
| 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: | Data processing Computer science Commerce, communications, transport Mathematics |
||||||||
| Uncontrolled Keywords: |
|
||||||||
| Date of oral exam: | 23 May 2011 | ||||||||
| Referee: |
|
||||||||
| Funders: | DB Schenker Rail Deutschland AG | ||||||||
| Projects: | F+E-Projekt der DB Schenker Rail Deutschland AG | ||||||||
| References: | \bibitem{adler:1991} I.~Adler and S.~Corsares. \newblock A strongly polynomial algorithm for a special class of linear programs. \newblock {\em Operations Research}, 39(6):955--960, 1991. \bibitem{ahuja:1993} Ravindra~K. Ahuja, Thomas~L. Magnanti, and James~B. Orlin. \newblock {\em Network flows: theory, algorithms, and applications}. \newblock Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993. \bibitem{ahuja:2005} R.K. Ahuja, C.B. Cunha, and G.~Sahin. \newblock Network models in railroad planning and scheduling. \newblock {\em Tutorials in Operations Research}, 1:54--101, 2005. \bibitem{ahuja:1992} R.K. Ahuja, A.V. Goldberg, J.B. Orlin, and R.E. Tarjan. \newblock Finding minimum-cost flows by double scaling. \newblock {\em Mathematical Programming}, 53:243--266, 1992. \bibitem{ahuja:2007} R.K. Ahuja, K.C. Jha, and J.~Liu. \newblock Solving real-life railroad blocking problems. \newblock {\em Interfaces}, 37(5):404--419, 2007. \bibitem{ahuja:2005a} R.K. Ahuja, J.~Liu, J.B. Orlin, D.~Sharma, and L.A. Shughart. \newblock Solving real-life locomotive-scheduling problems. \newblock {\em Transportation Science}, 39:503--517, 2005. \bibitem{appa:1993} G.~Appa. \newblock K-integrality, an extension of total unimodularity. \newblock {\em Operations Research Letters}, 13:159--163, 1993. \bibitem{appa:2004} G.~Appa and B.~Kotnyek. \newblock Rational and integral k-regular matrices. \newblock {\em Discrete Mathematics}, 275(1-3):1--15, 2004. \bibitem{assad:1980} A.A. Assad. \newblock Models for rail transportation. \newblock {\em Transportation Research Part A: General}, 14:205 -- 220, 1980. \bibitem{barahona:1989} F.~Barahona and E.~Tardos. \newblock Note on weintraub's minimum-cost circulation algorithm. \newblock {\em SIAM Journal on Computing}, 18, 1989. \bibitem{bellman:1958} R.~Bellman. \newblock On a routing problem. \newblock {\em Quarterly of Applied Mathematics}, 16(1):87--90, 1958. \bibitem{beygang:2008} K.~Beygang. \newblock Modelle und {A}lgorithmen f\"{u}r die {L}eerwagendisposition im {S}chieneng\"{u}terverkehr, 2008. \newblock Diplomarbeit, AG Optimierung, Fachbereich Mathematik, Technische Universit\"{a}t Kaiserslautern. \bibitem{beygang:2010} K.~Beygang, S.O. Krumke, and C.~Zeck. \newblock Generalized max flow in series-parallel graphs, 2010. \newblock WIMA Report, Band 125. \bibitem{bland:1992} R.G. Bland and D.L. Jensen. \newblock On the computational behavior of a polynomial-time network flow algorithm. \newblock {\em Mathematical Programming}, 54:1--39. \bibitem{busaker:1961} R.G. Busaker and P.J. Gowen. \newblock A procedure for determining a family of minimal-cost network flow patterns. \newblock Technical Report~15, Operational Research Office, John Hopkins University, Baltimore, MD, 1961. \bibitem{caprara:2002} A.~Caprara, M.~Fischetti, and P.~Toth. \newblock Modeling and solving the train timetabling problem. \newblock {\em Operations Research}, 50:851--861, 2002. \bibitem{caprara:2006} A.~Caprara, M.~Monaci, P.~Toth, and P.L. Guida. \newblock A lagrangian heuristic algorithm for a real-world train timetabling problem. \newblock {\em Discrete Applied Mathematics}, 154:738--753, 2006. \bibitem{chvatal:1983} V.~Chv\'{a}tal. \newblock {\em Linear Programming}. \newblock W. H. Freeman and Company, New York, 1983. \bibitem{cohen:1994} E.~Cohen and N.~Megiddo. \newblock Improved algorithms for linear inequalities with two variables per inequality. \newblock {\em SIAM Journal on Computing}, 23(6):1313--1347, 1994. \bibitem{cohen:1994a} E.~Cohen and N.~Megiddo. \newblock New algorithms for generalized network flows. \newblock {\em Mathematical Programming}, 64:325--336, 1994. \bibitem{cook:1999} W.~Cook and A.~Rohe. \newblock Computing minimum-weight perfect matchings. \newblock {\em INFORMS Journal on Computing}, 11:138--148, 1999. \bibitem{cook:1998} W.~J. Cook, W.~H. Cunningham, W.~R. Pulleyblank, and A.~Schrijver. \newblock {\em Combinatorial optimization}. \newblock John Wiley \& Sons, Inc., New York, NY, USA, 1998. \bibitem{cordeau:1998} J.-F. Cordeau, P.~Toth, and D.~Vigo. \newblock A survey of optimization models for train routing and scheduling. \newblock {\em Transportation Science}, 32(4):380--404, 1998. \bibitem{cormen:2001} T.H. Cormen, C.~E. Leiserson, R.~L. Rivest, and C.~Stein. \newblock {\em Introduction to Algorithms}. \newblock MIT Press, Cambridge, MA, 2001. \newblock Second Edition. \bibitem{crainic:1993} T.~G. Crainic, M.~Gendreau, and P.~Dejax. \newblock Dynamic and stochastic models for the allocation of empty containers. \newblock {\em Operations Research}, 41(1):102--126, 1993. \bibitem{dantzig:1963} G.B. Dantzig. \newblock {\em Linear Programming and Extensions}. \newblock Princeton University Press, Princeton, NJ, USA, 1963. \bibitem{darmann:2009} A.~Darmann, U.~Pferschy, J.~Schauer, and G.J. Woeginger. \newblock Paths, trees and matchings under disjunctive constraints. \newblock Optimization Online. \bibitem{dejax:1987} P.~Dejax and T.~G. Crainic. \newblock A review of empty flows and fleet management in freight transportation. \newblock {\em Transportation Science}, 21(4):227--247, 1987. \bibitem{dijkstra:1959} E.~W. Dijkstra. \newblock A note on two problems in connexion with graphs. \newblock {\em Numerische Mathematik}, 1:269--271, 1959. \bibitem{dinic:1970} E.~A. Dinic. \newblock Algorithm for solution of a problem of maximum flow in networks with power estimation. \newblock {\em Soviet Mathematics Doklady}, 11:1277--1280, 1970. \bibitem{edmonds:1965} J.~Edmonds. \newblock Paths, trees, and flowers. \newblock {\em Canadian Journal of Mathematics}, 17:449--467, 1965. \bibitem{edmonds:1973} J.~Edmonds and E.~L. Johnson. \newblock Matching, euler tours and the chinese postman. \newblock {\em Mathematical Programming}, 5:88--124, 1973. \bibitem{edmonds:1972} J.~Edmonds and R.M. Karp. \newblock Theoretical improvements in algorithmic efficiency for network flow problems. \newblock {\em Journal of the ACM}, 19, 1972. \bibitem{erlebach:2001} T.~Erlebach and K.~Jansen. \newblock The maximum edge-disjoint paths problem in bidirected trees. \newblock {\em SIAM J. Discrete Math}, 14:326--355, 2001. \bibitem{euler:1736} L.~Euler. \newblock Solutio problematis ad geometriam situs pertinentis. \newblock {\em Commentarii academiae scientiarum Petropolitanae}, 8:128--140, 1736. \bibitem{fleiner:2007} T.~Fleiner, R.W. Irving, and D.~Manlove. \newblock Efficient algorithms for generalized stable marriage and roommates problems. \newblock {\em Theoretical Computer Science}, 381:162--176, 2007. \bibitem{fleischer:2010} L.~Fleischer and Z.~Svitkina. \newblock Preference-constrained, oriented matching. \newblock In {\em 2010 Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO)}, pages 66--73. SIAM, 2010. \bibitem{fleischer:2001} L.~Fleischer and K.~D. Wayne. \newblock Fast and simple approximation schemes for generalized flow. \newblock {\em Mathematical Programming}, 91(2):215--238, 2001. \bibitem{fordfulkerson:1962} Jr. L.~R. Ford and D.R. Fulkerson. \newblock {\em Flows in Networks}. \newblock Princeton University Press, Princeton, NJ, 1962. \bibitem{frank:1990} A.~Frank. \newblock chapter Packing paths, curcuits and cuts -- a survey, pages 47--100. \newblock Springer, Berlin, 1990. \bibitem{fulkerson:1961} D.~R. Fulkerson. \newblock An out of kilter method for minimal cost flow problems. \newblock {\em SIAM Journal on Applied Mathematics}, 9:18--20, 1961. \bibitem{gabow:1990} H.N. Gabow. \newblock Data structures for weighted matching and nearest common ancestors with linking. \newblock In D.~Johnson, editor, {\em Proceedings of the 1st Annual {ACM}-{SIAM} Symposium on Discrete Algorithms ({SODA} '90)}, pages 434--443, San Francisco, CA, USA, 1990. SIAM. \bibitem{gabow:1989} H.N. Gabow, Z.~Galil, and T.H. Spencer. \newblock Efficient implementation of graph algorithms using contraction. \newblock {\em Journal of the ACM}, 36:540--572, 1989. \bibitem{gale:1962} D.~Gale and L.~S. Shapley. \newblock College admissions and the stability of marriage. \newblock {\em American Mathematical Monthly}, 69:9--14, 1962. \bibitem{gale:1985} D.~Gale and M.~Sotomayor. \newblock Some remarks on the stable matching problem. \newblock {\em Discrete Applied Mathematics}, 11:223--232, 1985. \bibitem{galil:1986} Z.~Galil, S.~Micali, and H.~Gabow. \newblock An ${O}({EV}\log {V})$-algorithm for finding a maximal weighted matching in general graphs. \newblock {\em SIAM Journal on Computing}, 15:120--130, 1986. \bibitem{garey:1979} M.~Garey and D.~Johnson. \newblock {\em Computers and Intractability: A guide to the theory of NP-Completeness}. \newblock W.H. Freeman, New York, USA, 1979. \bibitem{garg:1997} N.~Garg, V.~V. Vazirani, and M.~Yannakakis. \newblock Primal-dual approximation algorithms for integral flow and multicut in trees. \newblock {\em Algorithmica}, 18(1):3--20, 1997. \bibitem{gigon:1967} J.M. Gigon and F.~Schlaepfer. \newblock {Kybernetik und Elektronik bei den Eisenbahnen -- Die Leerwagenverteilung auf einer elektronischen Rechenanlage}. \newblock Technical report, 1967. \bibitem{glover:1978} F.~Glover, J.~Hultz, D.~Klingman, and J.~Stutz. \newblock Generalized networks: A fundamental computer-based planning tool. \newblock {\em Management Science}, 24:1209--1220, 1978. \bibitem{glover:1973} F.~Glover and D.~Klingman. \newblock On the equivalence of some generalized network problems to pure network problems. \newblock {\em Mathematical Programming}, 4:269--278, 1973. \bibitem{goldberg:1988} A.~Goldberg and R.~E. Tarjan. \newblock A new approach to the maximum flow problem. \newblock {\em Journal of the {ACM}}, 35:921--940, 1988. \bibitem{goldberg:1989} A.~Goldberg and R.~E. Tarjan. \newblock Finding minimum-cost circulations by canceling negative cycles. \newblock {\em Journal of the ACM}, 36, 1989. \bibitem{goldberg:1990} A.~Goldberg and R.~E. Tarjan. \newblock Finding minimum-cost circulations by successive approximation. \newblock {\em Mathematics of Operations Research}, 15, 1990. \bibitem{goldberg:1991} A.V. Goldberg, S.A. Plotkin, and E.~Tardos. \newblock Combinatorial algorithms for the generalized circulation problem. \newblock {\em Mathematics of Operations Research}, 16:351--379, 1991. \bibitem{goldfarb:1990} D.~Goldfarb and J.~Hao. \newblock A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and {O}(n$^2$m) time. \newblock {\em Mathematical Programming}, 47:353--365, 1990. \bibitem{goldfarb:1992} D.~Goldfarb and J.~Hao. \newblock Polynomial-time primal simplex algorithms for the minimum cost network flow problem. \newblock {\em Algorithmica}, 8:145--160, 1992. \bibitem{goldfarb:1996} D.~Goldfarb and Z.~Jin. \newblock A faster combinatorial algorithm for the generalized circulation problem. \newblock {\em Mathematics of Operations Research}, 21, 1996. \bibitem{goldfarb:2002} D.~Goldfarb, Z.~Jin, and Y.~Lin. \newblock A polynomial dual simplex algorithm for the generalized circulation problem. \newblock {\em Mathematical Programming}, 91(2):271--288, 2002. \bibitem{goldfarb:1997} D.~Goldfarb, Z.~Jin, and J.B. Orlin. \newblock Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem. \newblock {\em Mathematics of Operations Research}, 22, 1997. \bibitem{gondran:1984} M.~Gondran and M.~Minoux. \newblock {\em Graphs and Algorithms}. \newblock John Wiley \& Sons, New York, 1984. \bibitem{gorman:2010} M.F. Gorman, D.~Acharya, and D.~Sellers. \newblock {CSX} railway uses {OR} to cash in on optimized equipment distribution. \newblock {\em Interfaces}, 40(1):5--16, 2010. \bibitem{gorman:2011} M.F. Gorman, K.~Crook, and D.~Sellers. \newblock North american freight rail industry real-time optimized equipment distribution systems: State of the practice. \newblock {\em Transportation Research Part C: Emerging Technologies}, 19(1):103--114, 2011. \bibitem{haghani:1987} A.E. Haghani. \newblock Rail freight transportation: A review of recent optimization models for train routing and empty car distribution. \newblock {\em Journal of Advanced Transportation}, 21:147--172, 1987. \bibitem{haghani:1989} A.E. Haghani. \newblock Formulation and solution of a combined train routing and makeup, and empty car distribution model. \newblock {\em Transportation Research}, 23:433--452, 1989. \bibitem{hefner:1995} A.~Hefner and P.~Kleinschmidt. \newblock A constrained matching problem. \newblock {\em Annals of Operations Research}, 57:135--145, 1995. \bibitem{herren:1977} H.~Herren. \newblock Computer controlled empty wagon distribution on the {SSB}. \newblock {\em Rail International}, 8(1). \bibitem{hochbaum:1998} D.S. Hochbaum. \newblock Instant recognition of half integrality and 2-approximations. \newblock In {\em APPROX: International Workshop on Approximation Algorithms for Combinatorial Optimization}, 1998. \bibitem{hochbaum:1993} D.S. Hochbaum, N.~Megiddo, J.~Naor, and A.~Tamir. \newblock Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. \newblock {\em Mathematical Programming}, 62:69--83, 1993. \bibitem{hochbaum:1994} D.S. Hochbaum and J.~Naor. \newblock Simple and fast algorithms for linear and integer programs with two variables per inequality. \newblock {\em SIAM Journal on Computing}, 23, 1994. \bibitem{holmberg:1998} K.~Holmberg, M.~Joborn, and J.T. Lundgren. \newblock Improved empty freight car distribution. \newblock {\em Transportation Science}, 32(2):163--173, 1998. \bibitem{ireland:2004} P~Ireland, R.~Case, J.~Fallis, C.~Van~Dyke, J.~Kuehn, and M.~Meketon. \newblock The canadian pacific railway transforms operations by using models to develop its operating plans. \newblock {\em Interfaces}, 34(1):5--14, 2004. \bibitem{iri:1960} M.~Iri. \newblock A new method of solving transportation-network problems. \newblock {\em Journal of the Operations Research Society of Japan}, 3:27--87, 1960. \bibitem{jarvis:1972} J.J. Jarvis and A.M. Jezior. \newblock Maximal flow with gains through a special network. \newblock {\em Operations Research}, 20:678--688, 1972. \bibitem{jewell:1962} W.~S. Jewell. \newblock Optimal flow through networks with gains. \newblock {\em Operations Research}, 10:476--499, 1962. \bibitem{jewell:1958} W.S. Jewell. \newblock Optimal flow through networks. \newblock Technical Report~8, MIT, Cambridge, MA, 1958. \bibitem{joborn:2004} M.~Joborn, T.G. Crainic, M.~Gendreau, K.~Holmberg, and J.T. Lundgren. \newblock Economies of scale in empty freight car distribution in scheduled railways. \newblock {\em Transportation Science}, 38:121--134, 2004. \bibitem{kannan:1980} R.~Kannan. \newblock A polynomial algorithm for the two-variable integer programming problem. \newblock {\em Journal of the ACM}, 27(1):118--122, 1980. \bibitem{kapoor:1996} S.~Kapoor and P.~Vaidya. \newblock Speeding up {Karmarkar's} algorithm for multicommodity flows. \newblock {\em Mathematical Programming}, 73:111--127, 1996. \bibitem{karmarkar:1984} N.~Karmarkar. \newblock A new polynomial--time algorithm for linear programming. \newblock {\em Combinatorica}, 4:373--395, 1984. \bibitem{keaton:1989} M.H. Keaton. \newblock Designing optimal railroad operating plans: Lagrangian relaxations and heuristic approaches. \newblock {\em Transportation Science}, 23:415--431, 1989. \bibitem{khachian:1979} L.~G. Khachian. \newblock A polynomial algorithm in linear programming. \newblock {\em Soviet Mathematics Doklady}, 20(1):191--194, 1979. \bibitem{klein:1967} M.~Klein. \newblock A primal method for minimal cost flows. \newblock {\em Management Science}, 14:205--220, 1967. \bibitem{kolmogorov:2009} V.~Kolmogorov. \newblock Blossom v: A new implementation of a minimum cost perfect matching algorithm. \newblock {\em Mat | ||||||||
| Refereed: | Yes | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/4262 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |