Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
On CNF Encodings of Decision Diagrams Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Logic-Based Decomposition Methods for the Travelling Purchaser Problem

Authors : Kyle E. C. Booth, Tony T. Tran, J. Christopher Beck

Published in: Integration of AI and OR Techniques in Constraint Programming

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present novel branch-and-check and logic-based Benders decomposition techniques for the Travelling Purchaser Problem, an important optimization problem with applications in vehicle routing, logistics, and warehouse management. Our master problem determines a set of markets and directed travel arcs that satisfy product purchase constraints with relaxed travel costs. Our subproblem identifies subtours within this master assignment and produces a set of generalized subtour elimination cuts. We show that the proposed technique demonstrates strong performance on the asymmetric problem variants, finding optimal solutions to previously unsolved instances, while performing competitively on a number of symmetric problem classes. Furthermore, our model is implemented unchanged for the four problem variants whereas other state-of-the-art approaches are variant-specific.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Decomposition Based on Decision Diagrams
next chapter Lagrangian Decomposition via Sub-problem Search
Footnotes
1
The limit of one per iteration is due to the depot inclusion condition.
 
2
Experiments using dynamic variable creation in SCIP [1] show a relative improvement in B&C compared to LBBD though both CPLEX implementations are faster.
 
Literature
1.
2.
Applegate, D., Bixby, R., Cook, W., Chvátal, V.: On the solution of traveling salesman problems. Rheinische Friedrich-Wilhelms-Universität Bonn (1998)
3.
Balas, E., Toth, P.: Branch and bound methods for the traveling salesman problem. Technical report MSRR-488, DTIC Document (1983)
4.
Beck, J.C.: Checking-up on branch-and-check. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 84–98. Springer, Heidelberg (2010)CrossRef
5.
6.
Burt, C.N., Lipovetzky, N., Pearce, A.R., Stuckey, P.J.: Approximate uni-directional benders decomposition. In: Proceedings of PlanSOpt-15 Workshop on Planning, Search and Optimization AAAI-15 (2015)
7.
Cambazard, H., Penz, B.: A constraint programming approach for the traveling purchaser problem. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 735–749. Springer, Heidelberg (2012)CrossRef
8.
Desrochers, M., Laporte, G.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett. 10(1), 27–36 (1991)MathSciNetCrossRefMATH
9.
10.
11.
12.
Goerler, A., Schulte, F., Voß, S.: An application of late acceptance hill-climbing to the traveling purchaser problem. In: Pacino, D., Voß, S., Jensen, R.M. (eds.) ICCL 2013. LNCS, vol. 8197, pp. 173–183. Springer, Heidelberg (2013)CrossRef
13.
Goldbarg, M.C., Bagi, L.B., Goldbarg, E.F.G.: Transgenetic algorithm for the traveling purchaser problem. Eur. J. Oper. Res. 199(1), 36–45 (2009)CrossRefMATH
14.
Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logistics (NRL) 34(3), 307–318 (1987)CrossRefMATH
15.
Hooker, J.N., Ottosson, G.: Logic-based benders decomposition. Math. Program. 96(1), 33–60 (2003)MathSciNetMATH
16.
Laporte, G.: Generalized subtour elimination constraints and connectivity constraints. J. Oper. Res. Soc. 37, 509–514 (1986)CrossRefMATH
17.
Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)CrossRefMATH
18.
19.
Laporte, G., Riera-Ledesma, J., Salazar-González, J.-J.: A branch-and-cut algorithm for the undirected traveling purchaser problem. Oper. Res. 51(6), 940–951 (2003)MathSciNetCrossRefMATH
20.
21.
Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. ACM (JACM) 7(4), 326–329 (1960)MathSciNetCrossRefMATH
22.
Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60–100 (1991)MathSciNetCrossRefMATH
23.
Ramesh, T.: Traveling purchaser problem. Opsearch 18(1–3), 78–91 (1981)MATH
24.
Riera-Ledesma, J., Salazar-González, J.-J.: Solving the asymmetric traveling purchaser problem. Ann. Oper. Res. 144(1), 83–97 (2006)MathSciNetCrossRefMATH
25.
Singh, K.N., van Oudheusden, D.L.: A branch and bound algorithm for the traveling purchaser problem. Eur. J. Oper. Res. 97(3), 571–579 (1997)CrossRefMATH
26.
Thorsteinsson, E.S.: Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 16–30. Springer, Heidelberg (2001)CrossRef
27.
Tran, T.T., Araujo, A., Beck, J.C.: Decomposition methods for the parallel machine scheduling problem with setups. INFORMS J. Comput. 28(1), 83–95 (2016)CrossRef
Metadata
Title
Logic-Based Decomposition Methods for the Travelling Purchaser Problem
Authors
Kyle E. C. Booth
Tony T. Tran
J. Christopher Beck
Copyright Year
2016
Book
Integration of AI and OR Techniques in Constraint Programming

Print ISBN: 978-3-319-33953-5

Electronic ISBN: 978-3-319-33954-2

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-33954-2_5

Premium Partner

    Image Credits