Skip to main content
SpringerLink
Log in

Perspectives on integer programming for time-dependent models

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

Integer programs for solving time-dependent models—models in which decisions have to be made about the times at which activities occur and/or resources are utilized—are pervasive in industry, but are notoriously difficult to solve. In the last few years, interest in the role of discretization in approaches to solve these problems has intensified. One novel paradigm, dynamic discretization discovery, has emerged with the potential to greatly enhance the practical tractability of time-dependent models using integer programming technology. We introduce dynamic discretization discovery, illustrate its use on the traveling salesman problem with time windows, highlight its core principles, and point to opportunities for further research. Relations to other approaches for tackling time-dependent models are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. For minimization problems, dual bounds are lower bounds, which is the prevalent dual bound considered in this paper. However, the problem studied by Boland et al. (2015) has a maximization objective, so its dual bounds are upper bounds.

References

  • Abeledo H, Fukasawa R, Pessao A, Uchoa E (2013) The time dependent traveling salesman problem: polyhedra and algorithm. Math Program Comput 5:27–55

    Article  Google Scholar 

  • Albiach J, Sanchis J, Soler D (2008) An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation. Eur J Oper Res 189:789–802

    Article  Google Scholar 

  • Anderson E, Nash P, Philpott A (1982) A class of continuous network flow problems. Math Oper Res 7:501–514

    Article  Google Scholar 

  • Arigliano A, Ghiani G, Grieco A, Guerriero E, Plana I (2018) Time-dependent asymmetric traveling salesman problem with time windows: properties and an exact algorithm. Discrete Appl Math. https://doi.org/10.1016/j.dam.2018.09.017 In press

  • Ascheuer N, Fischetti M, Grötschel M (2001) Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math Program 90(3):475–506

    Article  Google Scholar 

  • Baker EK (1983) Technical note—an exact algorithm for the time-constrained traveling salesman problem. Oper Res 31(5):938–945

    Article  Google Scholar 

  • Baldacci R, Mingozzi A, Roberti R (2012) New state-space relaxations for solving the traveling salesman problem with time windows. INFORMS J Comput 24:356–371

    Article  Google Scholar 

  • Baptiste P, Sadykov R (2009) On scheduling a single machine to minimize a piecewise linear objective function: a compact IP formulation. Naval Res Logist 56:487–502

    Article  Google Scholar 

  • Belvaux G, Wolsey L (2000) bc-prod: a specialized branch-and-cut system for lot-sizing problems. Manag Sci 46:724–738

    Article  Google Scholar 

  • Belvaux G, Wolsey L (2001) Modelling practical lot-sizing problems as mixed-integer programs. Manag Sci 47:993–1007

    Article  Google Scholar 

  • Boland N, Kalinowski T, Kaur S (2015) Scheduling network maintenance jobs with release dates and deadlines to maximize total flow over time: bounds and solution strategies. Comput Oper Res 64:113–129

    Article  Google Scholar 

  • Boland N, Clement R, Waterer H (2016) A bucket indexed formulation for nonpreemptive single machine scheduling problems. INFORMS J Comput 28:14–30

    Article  Google Scholar 

  • Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous time service network design problem. Oper Res 65:1303–1321

    Article  Google Scholar 

  • Christofides N, Mingozzi A, Toth P (1981) State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145–164

    Article  Google Scholar 

  • Clautiaux F, Hanafi S, Macedo R, Voge M-E, Alves C (2017) Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints. Eur J Oper Res 258:467–477

    Article  Google Scholar 

  • Dash S, Günlük O, Lodi A, Tramontani A (2012) A time bucket formulation for the travelling salesman problem with time windows. INFORMS J Comput 24:132–147

    Article  Google Scholar 

  • Fischer F, Helmberg C (2014) Dynamic graph generation for the shortest path problem in time-expanded networks. Math Program Ser A 143:1–16

    Article  Google Scholar 

  • Focacci F, Lodi A, Milano M (2002) A hybrid exact algorithm for the TSPTW. INFORMS J Comput 14(4):403–417

    Article  Google Scholar 

  • Foschini L, Hershberger J, Suri S (2014) On the complexity of time-dependent shortest paths. Algorithmica 68(4):1075–1097

    Article  Google Scholar 

  • Gouveia L, Ruthmair M (2015) Load-dependent and precedence-based models for pickup and delivery problems. Comput Oper Res 63:56–71

    Article  Google Scholar 

  • Gouveia L, Leitner M, Ruthmair M (2019) Layered graph approaches for combinatorial optimization problems. Comput Oper Res 102:22–38

    Article  Google Scholar 

  • He E, Boland N, Nemhauser G, Savelsbergh M (2019) Dynamic discretization discovery algorithms for time-dependent shortest path problems. Optimization Online 2019-7082

  • Irnich S (2008) Resource extension functions: properties, inversion, and generalization to segments. OR Spectr 30(1):113–148

    Article  Google Scholar 

  • Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, Boston, MA

    Google Scholar 

  • Irnich S, Desaulniers G, Desrosiers J, Hadjar A (2010) Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J Comput 22(2):297–313

    Article  Google Scholar 

  • Kara I, Derya T (2015) Formulations for minimizing tour duration of the traveling salesman problem with time windows. Procedia Econ Finance 26:1026–1034

    Article  Google Scholar 

  • Lagos F, Boland N, Savelsbergh M (2018) The continuous time inventory routing problem. Optimization Online 2018-6439

  • Langevin A, Desrochers M, Desrosiers J, Gélinas S, Soumis F (1993) A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows. Networks 23(7):631–640

    Article  Google Scholar 

  • Mahmoudi M, Zhou X (2016) Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations. Transp Res Part B Methodol 89:19–42

    Article  Google Scholar 

  • Marshall L, Boland N, Hewitt M, Savelsbergh M (2018) Interval-based dynamic discretization discovery for solving the continuous-time service network design problem. Optimization Online 2018-6883

  • Montero A, Méndez-Dıaz I, Miranda-Bront J (2017) An integer programming approach for the time-dependent traveling salesman problem with time windows. Comput Oper Res 88:280–289

    Article  Google Scholar 

  • Pesant G, Gendreau M, Potvin J, Rousseau J (1998) An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transp Sci 32(1):12–29

    Article  Google Scholar 

  • Pessoa A, Uchoa E, Poggi de Aragao M, Rodrigues R (2010) Exact algorithm over an arc-time indexed formulation for parallel machine scheduling problems. Math Program Comput 2:259–290

    Article  Google Scholar 

  • Philpott AB (1990) Continuous-time flows in networks. Math Oper Res 15:640–661

    Article  Google Scholar 

  • Philpott A, Craddock M (1995) An adaptive discretization algorithm for a class of continuous knapsack problems. Networks 26:1–11

    Article  Google Scholar 

  • Picard J-C, Queyranne M (1978) The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling. Oper Res 26:86–110

    Article  Google Scholar 

  • Pugliese LDP, Guerriero F (2013) A survey of resource constrained shortest path problems: exact solution approaches. Networks 62(3):183–200

    Article  Google Scholar 

  • Riedler M, Ruthmair M, Raidl G (2018) Strategies for iteratively refining layered graph models. Researchgate 328314707

  • Savelsbergh M (1985) Local search in routing problems with time windows. Ann Oper Res 4(1):285–305

    Article  Google Scholar 

  • Skutella M (2009) An introduction to network flows over time. In: Cook W, Lovász L, Vygen J (eds) Research trends in combinatorial optimization. Springer, Berlin, pp 451–482

    Chapter  Google Scholar 

  • Vu DM, Boland N, Hewitt M, Savelsbergh M (2018) Solving time dependent traveling salesman problems with time windows. Optimization Online 2018-6640. Transp Sci (to appear)

  • Wang X, Regan A (2002) Local truckload pickup and delivery with hard time window constraints. Transp Res B 36:97–112

    Article  Google Scholar 

  • Wang X, Regan A (2009) On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints. Comput Ind Eng 56:161–164

    Article  Google Scholar 

Download references

Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant no. 1662848.

Author information

Authors and Affiliations

  1. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA

    Natashia L. Boland & Martin W. P. Savelsbergh

Authors
  1. Natashia L. Boland
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin W. P. Savelsbergh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Natashia L. Boland.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This invited paper is discussed in the comments available at https://doi.org/10.1007/s11750-019-00510-8, https://doi.org/10.1007/s11750-019-00511-7, https://doi.org/10.1007/s11750-019-00512-6.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Boland, N.L., Savelsbergh, M.W.P. Perspectives on integer programming for time-dependent models. TOP 27, 147–173 (2019). https://doi.org/10.1007/s11750-019-00514-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-019-00514-4

Keywords

Mathematics Subject Classification

Search

Navigation