Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Mixed integer programming formulations for the generalized traveling salesman problem with time windows

  • Research Paper
  • Published:
4OR Aims and scope Submit manuscript

Abstract

The generalized traveling salesman problem with time windows (GTSPTW) is defined on a directed graph where the vertex set is partitioned into clusters. One cluster contains only the depot. Each vertex is associated with a time window, during which the visit must take place if the vertex is visited. The objective is to find a minimum cost tour starting and ending at the depot such that each cluster is visited exactly once and time constraints are respected, i.e., for each cluster, a single vertex is visited during its time window. In this paper, four mixed integer linear programming formulations for the GTSPTW are proposed and compared. They are based on different definitions of variables. All the formulations are compact, which means the number of decision variables and constraints is polynomial with respect to the size of the instance. Dominance relations between their linear relaxations are established theoretically. Computational experiments are conducted to compare the linear relaxations and branch-and-bound performances of the four formulations. The results show that two formulations are better than the other ones.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • 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 

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

    Article  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

    Article  Google Scholar 

  • Desrochers M, Desrosiers J, Solomon M (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper Res 40(2):342–354

    Article  Google Scholar 

  • Fischetti M, Salazar González JJ, Toth P (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper Res 45(3):378–394

    Article  Google Scholar 

  • Hawkins AJ (2018) Amazon will now deliver packages to the trunk of your car. https://www.theverge.com/2018/4/24/17261744/amazon-package-delivery-car-trunk-gm-volvo. Accessed May 2019

  • Israeli E, Wood RK (2002) Shortest-path network interdiction. Netw Int J 40(2):97–111

    Google Scholar 

  • Kara I, Guden H, Koc ON (2012) New formulations for the generalized traveling salesman problem. In: Proceedings of the 6th international conference on applied mathematics, simulation, modelling, ASM, vol 12, pp 60–65

  • Karapetyan D (2012) Gtsp instances library. http://www.cs.nott.ac.uk/~pszdk/gtsp.html. Accessed Aug 2018

  • Kirsten K (2016) Volvo’s solution for the package theft epidemic: your car’s trunk. http://fortune.com/2016/05/10/volvo-urb-it-delivery/. Accessed Mar 2019

  • Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7(4):326–329

    Article  Google Scholar 

  • Ozbaygin G, Karasan OE, Savelsbergh M, Yaman H (2017) A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transp Res Part B Methodol 100:115–137

    Article  Google Scholar 

  • Pop PC (2007) New integer programming formulations of the generalized traveling salesman problem. Am J Appl Sci 4(11):932–937

    Article  Google Scholar 

  • Reyes D, Savelsbergh M, Toriello A (2017) Vehicle routing with roaming delivery locations. Transp Res Part C Emerg Technol 80:71–91

    Article  Google Scholar 

  • Yuan Y, Cattaruzza D, Ogier M, Semet F (2020a) A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. Eur J Oper Res 286(3):849–866

    Article  Google Scholar 

  • Yuan Y, Cattaruzza D, Ogier M, Semet F (2020b) A note on the lifted Miller–Tucker–Zemlin subtour elimination constraints for routing problems with time windows. Oper Res Lett 48(2):167–169

    Article  Google Scholar 

Download references

Acknowledgements

This work is partially supported by the CSC (China Scholarship Council (Grant No. 201604490024)) and by the ELSAT 2020 project. This support is gratefully acknowledged.

Author information

Authors and Affiliations

  1. CNRS, Centrale Lille, Inria, UMR 9189 - CRIStAL Lille, Univ. Lille, Lille, France

    Yuan Yuan, Diego Cattaruzza, Maxime Ogier, Cyriaque Rousselot & Frédéric Semet

Authors
  1. Yuan Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diego Cattaruzza
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maxime Ogier
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Cyriaque Rousselot
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Frédéric Semet
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuan Yuan.

Ethics declarations

Conflict of interest

This manuscript has not been published and is not under consideration for publication elsewhere. We have no conflicts of interest to disclose. All authors have approved the manuscript and agree with its submission to “4OR-A Quarterly Journal of Operations Research”.

Additional information

Publisher's Note

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

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yuan, Y., Cattaruzza, D., Ogier, M. et al. Mixed integer programming formulations for the generalized traveling salesman problem with time windows. 4OR-Q J Oper Res 19, 571–592 (2021). https://doi.org/10.1007/s10288-020-00461-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-020-00461-y

Keywords

Mathematics Subject Classification

Search

Navigation