Solving Unsplittable Network Flow Problems with Decision Diagrams

References

• Abbink E, Van den Berg B, Kroon L, Salomon M (2004) Allocation of railway rolling stock for passenger trains. Transportation Sci. 38(1):33–41.Link, Google Scholar
• Alfieri A, Groot R, Kroon L, Schrijver A (2006) Efficient circulation of railway rolling stock. Transportation Sci. 40(3):378–391.Link, Google Scholar
• Andersen HR, Hadzic T, Hooker JN, Tiedemann P (2007) A constraint store based on multivalued decision diagrams. Proc. Internat. Conf. on Principles and Practice of Constraint Programming (Springer, Berlin), 118–132.Google Scholar
• Association of American Railroads (2021) Freight railroads fact sheet. Accessed June 28, 2021, https://www.aar.org.Google Scholar
• Baier G, Köhler E, Skutella M (2005) The k-splittable flow problem. Algorithmica 42(3):231–248.Crossref, Google Scholar
• Bergman D, Cire AA (2018) Discrete nonlinear optimization by state-space decompositions. Management Sci. 64(10):4700–4720.Link, Google Scholar
• Bergman D, Cire AA, Van Hoeve WJ, Hooker J (2016a) Decision Diagrams for Optimization, vol. 1 (Springer, Berlin).Crossref, Google Scholar
• Bergman D, Cire AA, Van Hoeve WJ, Hooker JN (2016b) Discrete optimization with decision diagrams. INFORMS J. Comput. 28(1):47–66.Link, Google Scholar
• Borndörfer R, Reuther M, Schlechte T, Waas K, Weider S (2016) Integrated optimization of rolling stock rotations for intercity railways. Transportation Sci. 50(3):863–877.Link, Google Scholar
• Cacchiani V, Toth P (2012) Nominal and robust train timetabling problems. Eur. J. Oper. Res. 219(3):727–737.Crossref, Google Scholar
• Carey M, Crawford I (2007) Scheduling trains on a network of busy complex stations. Transportation Res. Part B: Methodological 41(2):159–178.Crossref, Google Scholar
• Ceselli A, Gatto M, Lübbecke ME, Nunkesser M, Schilling H (2008) Optimizing the cargo express service of Swiss federal railways. Transportation Sci. 42(4):450–465.Link, Google Scholar
• Chakrabarti A, Chekuri C, Gupta A, Kumar A (2007) Approximation algorithms for the unsplittable flow problem. Algorithmica 47(1):53–78.Crossref, Google Scholar
• Cordeau JF, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transportation Sci. 32(4):380–404.Link, Google Scholar
• Cornelsen S, Di Stefano G (2007) Track assignment. J. Discrete Algorithms 5(2):250–261.Crossref, Google Scholar
• Davarnia D (2021) Strong relaxations for continuous nonlinear programs based on decision diagrams. Oper. Res. Lett. 49(2):239–245.Crossref, Google Scholar
• Davarnia D, Van Hoeve WJ (2021) Outer approximation for integer nonlinear programs via decision diagrams. Math. Programming 187:111–150.Crossref, Google Scholar
• Davarnia D, Richard JPP, Içyüz-Ay E, Taslimi B (2019) Network models with unsplittable node flows with application to unit train scheduling. Oper. Res. 67(4):1053–1068.Abstract, Google Scholar
• Demir E, Burgholzer W, Hrušovskỳ M, Arikan E, Jammernegg W, Van Woensel T (2016) A green intermodal service network design problem with travel time uncertainty. Transportation Res. Part B: Methodological 93:789–807.Crossref, Google Scholar
• Fuchsberger M, Lüthi P (2007) Solving the Train Scheduling Problem in a Main Station Area via a Resource Constrained Space-Time Integer Multi-Commodity Flow (Institute for Operations Research, ETH Zurich, Zurich).Google Scholar
• Furchtgott-Roth D, Hu PS, Nguyen L, Jahanmir S, Moore WH, Riley D, Beningo S, et al. (2023) Pocket Guide to Transportation 2021 (Bureau of Transportation Statistics, Washington, DC).Google Scholar
• Gong C, Shi J, Wang Y, Zhou H, Yang L, Chen D, Pan H (2021) Train timetabling with dynamic and random passenger demand: A stochastic optimization method. Transporation Res., Part C Emerging Tech. 123:102963.Crossref, Google Scholar
• Gonzalez JE, Cire AA, Lodi A, Rousseau LM (2020) Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem. Constraints 25:23–46.Crossref, Google Scholar
• Haahr J, Lusby RM (2017) Integrating rolling stock scheduling with train unit shunting. Eur. J. Oper. Res. 259(2):452–468.Crossref, Google Scholar
• Haahr JT, Wagenaar JC, Veelenturf LP, Kroon LG (2016) A comparison of two exact methods for passenger railway rolling stock (re) scheduling. Transportation Res., Part E Logist. Transportation Rev. 91:15–32.Crossref, Google Scholar
• Hadzić T, Hooker J (2006) Discrete global optimization with binary decision diagrams. Proc. Workshop on Global Optim.: Integrating Convexity, Optimization, Logic Programming, and Comput. Algebraic Geometry (Vienna).Google Scholar
• Harrod S, Gorman MF (2010) Operations Research for Freight Train Routing and Scheduling (Wiley, New York).Google Scholar
• Heil J, Hoffmann K, Buscher U (2020) Railway crew scheduling: Models, methods and applications. Eur. J. Oper. Res. 283(2):405–425.Crossref, Google Scholar
• Holzhauser M, Krumke SO, Thielen C (2017a) Maximum flows in generalized processing networks. J. Combinatorial Optim. 33(4):1226–1256.Crossref, Google Scholar
• Holzhauser M, Krumke SO, Thielen C (2017b) A network simplex method for the budget-constrained minimum cost flow problem. Eur. J. Oper. Res. 259(3):864–872.Crossref, Google Scholar
• Hosseininasab A, Van Hoeve WJ (2021) Exact multiple sequence alignment by synchronized decision diagrams. INFORMS J. Comput. 33(2):721–738.Abstract, Google Scholar
• Hu Y, Lan J, Wan C (2009) An algorithm for unsplittable flow problem in flexible reconfigurable network. Proc. 4th Internat. Conf. on Frontier of Comput. Sci. and Tech. (IEEE, New York), 543–547.Google Scholar
• Huntley CL, Brown DE, Sappington DE, Markowicz BP (1995) Freight routing and scheduling at CSX transportation. Interfaces 25(3):58–71.Link, Google Scholar
• Içyüz IE, Richard JPP, Eskigun E, Acharya D (2016) A two-model solution approach for the monthly coal train reservations planning problem. Transportation Sci. 50(3):926–946.Link, Google Scholar
• Jin G, He S, Li J, Guo X, Li Y (2019) An approach for train stop planning with variable train length and stop time of high-speed rail under stochastic demand. IEEE Access 7:129690–129708.Crossref, Google Scholar
• Jordan WC, Turnquist MA (1983) A stochastic, dynamic network model for railroad car distribution. Transportation Sci. 17(2):123–145.Link, Google Scholar
• Jovanović D, Harker PT (1991) Tactical scheduling of rail operations: The scan I system. Transportation Sci. 25(1):46–64.Link, Google Scholar
• Kleinberg JM (1996) Approximation algorithms for disjoint paths problems. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Kolman P, Scheideler C (2006) Improved bounds for the unsplittable flow problem. J. Algorithms 61(1):20–44.Crossref, Google Scholar
• Kwan RS (2011) Case studies of successful train crew scheduling optimisation. J. Scheduling 14(5):423–434.Crossref, Google Scholar
• Larsen R, Pranzo M, D’Ariano A, Corman F, Pacciarelli D (2014) Susceptibility of optimal train schedules to stochastic disturbances of process times. Flexible Service Manufacturing J. 26(4):466–489.Crossref, Google Scholar
• Lawley M, Parmeshwaran V, Richard JP, Turkcan A, Dalal M, Ramcharan D (2008) A time–space scheduling model for optimizing recurring bulk railcar deliveries. Transportation Res. Part B: Methodological 42(5):438–454.Crossref, Google Scholar
• Layeb SB, Jaoua A, Jbira A, Makhlouf Y (2018) A simulation-optimization approach for scheduling in stochastic freight transportation. Comput. Industry Engrg. 126:99–110.Crossref, Google Scholar
• Liu SQ, Kozan E (2011) Optimising a coal rail network under capacity constraints. Flexible Service Manufacturing J. 23(2):90–110.Crossref, Google Scholar
• Lin Z, Kwan RS (2014) A two-phase approach for real-world train unit scheduling. Public Transportation (Berlin) 6(1–2):35–65.Crossref, Google Scholar
• Lin Z, Kwan RS (2016) A branch-and-price approach for solving the train unit scheduling problem. Transportation Res. Part B: Methodological 94:97–120.Crossref, Google Scholar
• Lin Z, Kwan RS (2018) Redundant coupling/decoupling in train unit scheduling optimization. Electronic Notes Discrete Math. 64:45–54.Crossref, Google Scholar
• Lusby RM (2008) Optimization methods for routing trains through railway junctions. PhD thesis, ResearchSpace, Auckland, New Zealand.Google Scholar
• Lusby RM, Larsen J, Ehrgott M, Ryan D (2011) Railway track allocation: models and methods. OR Spectrum 33(4):843–883.Crossref, Google Scholar
• Meng L, Zhou X (2011) Robust single-track train dispatching model under a dynamic and stochastic environment: A scenario-based rolling horizon solution approach. Transportation Res. Part B: Methodological 45(7):1080–1102.Crossref, Google Scholar
• Quaglietta E, Corman F, Goverde RM (2013) Stability of railway dispatching solutions under a stochastic and dynamic environment. Proc. RailCopenhagen2013: 5th Internat. Seminar on Railway Operations Modelling and Analysis (Institute for Transport Planning and Systems, ETH Zurich, Zurich).Google Scholar
• Salemi H, Davarnia D (2022a) On the structure of decision diagram-representable mixed integer programs with application to unit commitment. Oper. Res., ePub ahead of print August 4, https://doi.org/10.1287/opre.2022.2353.Google Scholar
• Salemi H, Davarnia D (2022b) Test instances for SGUFP. https://doi.org/10.5281/zenodo.6373664.Google Scholar
• Serra T, Hooker JN (2020) Compact representation of near-optimal integer programming solutions. Math. Programming 182:199–232.Crossref, Google Scholar
• Shen Y, Peng K, Chen K, Li J (2013) Evolutionary crew scheduling with adaptive chromosomes. Transportation Res. Part B: Methodological 56:174–185.Crossref, Google Scholar
• Sherali HD, Suharko AB (1998) A tactical decision support system for empty railcar management. Transportation Sci. 32(4):306–329.Link, Google Scholar
• Turner C, Tiwari A, Starr A, Blacktop K (2016) A review of key planning and scheduling in the rail industry in Europe and UK. Proc. Inst. Mechanical Engrg., F J. Rail Rapid Transit 230(3):984–998.Crossref, Google Scholar
• Walkowiak K (2006) New algorithms for the unsplittable flow problem. Proc. Internat. Conf. on Comput. Sci. and Its Appl. (Springer, Berlin), 1101–1110.Google Scholar
• Ying Cs, Chow AH, Chin KS (2020) An actor-critic deep reinforcement learning approach for metro train scheduling with rolling stock circulation under stochastic demand. Transportation Res. Part B: Methodological 140:210–235.Crossref, Google Scholar
• Zwaneveld PJ, Kroon LG, Van Hoesel SP (2001) Routing trains through a railway station based on a node packing model. Eur. J. Oper. Res. 128(1):14–33.Crossref, Google Scholar