The Freight Transportation Network Scheduling Problem: An Integer Programming-Based Column Generation Algorithm

References

• Andersen J, Crainic TG, Christiansen M (2009) Service network design with asset management: Formulations and comparative analyses. Transportation Res. Part C: Emerging Tech. 17(2):197–207.Crossref, Google Scholar
• Andersen J, Christiansen M, Crainic TG, Grønhaug R (2011) Branch and price for service network design with asset management constraints. Transportation Sci. 45(1):33–49.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Baubaid A, Boland N, Savelsbergh M (2021) The value of limited flexibility in service network designs. Transportation Sci. 55(1):52–74.Link, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numerical Math. 4(1):238–252.Crossref, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2019) The price of discretizing time: A study in service network design. EURO J. Transportation Logist. 8(2):195–216.Crossref, Google Scholar
• Chouman M, Crainic TG (2015) Cutting-plane matheuristic for service network design with design-balanced requirements. Transportation Sci. 49(1):99–113.Link, Google Scholar
• Crainic T (2000) Service network design in freight transportation. Eur. J. Oper. Res. 122(2):272–288.Crossref, Google Scholar
• Crainic TG, Hewitt M (2021) Service Network Design (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• Crainic TG, Sgalambro A (2014) Service network design models for two-tier city logistics. Optim. Lett. 8(4):1375–1387.Crossref, Google Scholar
• Dash S, Günlük O, Lodi A, Tramontani A (2012) A time bucket formulation for the traveling salesman problem with time windows. INFORMS J. Comput. 24(1):132–147.Link, Google Scholar
• Desaulniers G, Desrosiers J, Solomon MM (2006) Column Generation, vol. 5 (Springer Science & Business Media, New York).Google Scholar
• Erera A, Hewitt M, Savelsbergh M, Zhang Y (2013) Improved load plan design through integer programming based local search. Transportation Sci. 47(3):412–427.Link, Google Scholar
• Ford LR, Fulkerson DR (1958) Constructing maximal dynamic flows from static flows. Oper. Res. 6(3):419–433.Link, Google Scholar
• Ford LR, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Hewitt M (2019) Enhanced dynamic discretization discovery for the continuous time load plan design problem. Transportation Sci. 53(6):1731–1750.Link, Google Scholar
• Hewitt M, Lehuédé F (2023) New formulations for the scheduled service network design problem. Transportation Res. Part B: Methodological 172:117–133.Crossref, Google Scholar
• Hewitt M, Lehuédé F (2025) The freight transportation network scheduling problem: An integer programming-based column generation algorithm. https://doi.org/10.1287/ijoc.2023.0435.cd, https://github.com/INFORMSJoC/2023.0435.Google Scholar
• Hewitt M, Crainic TG, Nowak M, Rei W (2019) Scheduled service network design with resource acquisition and management under uncertainty. Transportation Res. Part B: Methodological 128:324–343.Crossref, Google Scholar
• Jarrah A, Johnson E, Neubert L (2009) Large-scale, less-than-truckload service network design. Oper. Res. 57(3):609–625.Link, Google Scholar
• Marshall L, Boland N, Savelsbergh M, Hewitt M (2021) Interval-based dynamic discretization discovery for solving the continuous-time service network design problem. Transportation Sci. 55(1):29–51.Link, Google Scholar
• Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization (Wiley, New York).Crossref, Google Scholar
• Pinedo M (2012) Scheduling (Springer, New York).Crossref, Google Scholar
• Powell WB, Sheffi Y (1983) The load planning problem of motor carriers: Problem description and proposed solution approach. Transportation Res. A 17A(6):471–480.Crossref, Google Scholar
• Powell WB, Sheffi Y (1989) Design and implementation of an interactive optimization system for network design in the motor carrier industry. Oper. Res. 37(1):12–29.Link, Google Scholar
• Rönnberg E, Larsson T (2009) Column generation in the integral simplex method. Eur. J. Oper. Res. 192(1):333–342.Crossref, Google Scholar
• Rönnberg E, Larsson T (2014) All-integer column generation for set partitioning: Basic principles and extensions. Eur. J. Oper. Res. 233(3):529–538.Crossref, Google Scholar
• Savelsbergh M (1997) A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6):831–841.Link, Google Scholar
• Scherr YO, Hewitt M, Saavedra BAN, Mattfeld DC (2020) Dynamic discretization discovery for the service network design problem with mixed autonomous fleets. Transportation Res. Part B: Methodological 141:164–195.Crossref, Google Scholar
• Scherr YO, Saavedra BAN, Hewitt M, Mattfeld DC (2019) Service network design with mixed autonomous fleets. Transportation Res. Part E: Logist. Transportation Rev. 124:40–55.Crossref, Google Scholar
• Schulz JD (2021) Rival carriers chase former central freight customers as tight LTL market shrinks. Accessed May 27, 2025, https://www.logisticsmgmt.com/article/rival\_carriers\_chase\_former\_central\_freight\_customers\_as\_tight\_ltl\_market\_s.Google Scholar
• Studio-CPLEX (2013) Users Manual, Version 12, Release 6 (IBM, North Castle, NY).Google Scholar
• Tahir A, Desaulniers G, El Hallaoui I (2019) Integral column generation for the set partitioning problem. EURO J. Transportation Logist. 8(5):713–744.Crossref, Google Scholar
• Tahir A, Desaulniers G, El Hallaoui I (2022) Integral column generation for set partitioning problems with side constraints. INFORMS J. Comput. 34(4):2313–2331.Link, Google Scholar
• Tahir A, Quesnel F, Desaulniers G, El Hallaoui I, Yaakoubi Y (2021) An improved integral column generation algorithm using machine learning for aircrew pairing. Transportation Sci. 55(6):1411–1429.Link, Google Scholar
• Toth P, Vigo D (2014) Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia).Crossref, Google Scholar
• UPS (2021) UPS annual report. Accessed May 27, 2025, https://investors.ups.com/company-profile.Google Scholar
• VanRossum G, Drake FL (2010) The Python Language Reference (Python Software Foundation, Amsterdam).Google Scholar
• Zhu E, Crainic TG, Gendreau M (2014) Scheduled service network design for freight rail transportation. Oper. Res. 62(2):383–400.Link, Google Scholar