Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
On CNF Encodings of Decision Diagrams Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Logic-Based Decomposition Methods for the Travelling Purchaser Problem

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

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

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Decomposition Based on Decision Diagrams
Nächstes Kapitel Lagrangian Decomposition via Sub-problem Search
Fußnoten
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.
 
Literatur
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.
Bontoux, B., Feillet, D.: Ant colony optimization for the traveling purchaser problem. Comput. Oper. Res. 35(2), 628–637 (2008)MathSciNetCrossRefMATH
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
Metadaten
Titel
Logic-Based Decomposition Methods for the Travelling Purchaser Problem
verfasst von
Kyle E. C. Booth
Tony T. Tran
J. Christopher Beck
Copyright-Jahr
2016
Buch
Integration of AI and OR Techniques in Constraint Programming

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

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

Copyright-Jahr: 2016

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

Premium Partner

    Bildnachweise