nach oben

Journal of Combinatorial Optimization

Erschienen in:

17.06.2020

Parameterized algorithms and complexity for the traveling purchaser problem and its variants

verfasst von: Mingyu Xiao, Jianan Zhang, Weibo Lin

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2022

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The traveling purchaser problem (TPP), a generalization of the traveling salesman problem, is to determine a tour of suppliers and purchase needed products from suppliers while minimizing the traveling and purchasing cost. This problem finds applications in the routing and scheduling contexts and its variants with different constraints have been widely studied. Motivated by the phenomenon that most real-world instances of TPP have a small parameter (such as the number of suppliers, the number of products to purchase, and others), we study TPP and its variants from the view of parameterized complexity. We show that TPP and some variants are fixed-parameter tractable by taking the number k of products or the number m of suppliers as the parameter, and W[2]-hard by taking the number q of visited suppliers as the parameter. Furthermore, we implement some of our fixed-parameter tractable algorithms to show that they are practically effective when the parameters are not very large.

Vorheriger Artikel Online economic ordering problem for deteriorating items with limited price information

Nächster Artikel Principal–agent problem under the linear contract

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 "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

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

https://github.com/CsAlgorithm/TPP-parameterized-algorithms.

http://jriera.webs.ull.es/TPP.htm.

Ahuja RK, Orlin JB, Stein C (1994) Improved algorithms for bipartite network flow. SIAM J Comput 23(5):906–933MathSciNetCrossRef

Alon N, Yuster R, Zwick U (1995) Color-coding. J ACM 42(4):844–856MathSciNetCrossRef

Angelelli E, Mansini R, Vindigni M (2008) Exploring greedy criteria for the dynamic traveling purchaser problem. Central Eur J Oper Res 17(2):141–158MathSciNetCrossRef

Angelelli E, Mansini R, Vindigni M (2016) The stochastic and dynamic traveling purchaser problem. Transp Sci 50(2):642–658CrossRef

Angelelli E, Gendreau M, Mansini R, Vindigni M (2017) The traveling purchaser problem with time-dependent quantities. Comput Oper Res 82:15–26MathSciNetCrossRef

Bellman R (1962) Dynamic programming treatment of the travelling salesman problem. J ACM 9(1):61–63MathSciNetCrossRef

Bianchessi N, Mansini R, Speranza MG (2014) The distance constrained multiple vehicle traveling purchaser problem. Eur J Oper Res 235(1):73–87MathSciNetCrossRef

Cambazard H, Penz B (2012) A constraint programming approach for the traveling purchaser problem. In: Milano M (eds) Principles and practice of constraint programming. CP 2012. Lecture notes in computer science, vol 7514, pp 735–749. Springer, Berlin

Choi MJ, Lee SH (2011) The multiple traveling purchaser problem for maximizing system’s reliability with budget constraints. Expert Syst Appl 38(8):9848–9853CrossRef

Desaulniers G (2010) Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Oper Res 58(1):179–192MathSciNetCrossRef

Downey RG, Fellows MR (1992) Fixed-parameter tractability and completeness. Mathematical Sciences Institute, Cornell University, IthacaMATH

Downey RG, Fellows MR (1995) Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor Comput Sci 141(1):109–131MathSciNetCrossRef

Gouveia L, Paias A, Voß S (2011) Models for a traveling purchaser problem with additional side-constraints. Comput Oper Res 38(2):550–558MathSciNetCrossRef

Hamdan S, Larbi R, Cheaitou A, Alsyouf I (2017) Green traveling purchaser problem model: A bi-objective optimization approach. In: Proceedings of the 7th international conference on modeling, simulation, and applied optimization (ICM-SAO), pp 1–6

Held M, Karp RM (1962) A dynamic programming approach to sequencing problems. J Soc Ind Appl Math 10(1):196–210MathSciNetCrossRef

Ho SC, Haugland D (2004) A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Comput Oper Res 31(12):1947–1964CrossRef

Kang S, Ouyang Y (2011) The traveling purchaser problem with stochastic prices: exact and approximate algorithms. Eur J Oper Res 209(3):265–272MathSciNetCrossRef

Laporte G, Riera-Ledesma J, Salazar-González JJ (2003) A branch-and-cut algorithm for the undirected traveling purchaser problem. Oper Res 51(6):940–951MathSciNetCrossRef

Manerba D, Mansini R (2015) A branch-and-cut algorithm for the multi-vehicle traveling purchaser problem with pairwise incompatibility constraints. Networks 65(2):139–154MathSciNetCrossRef

Manerba D, Gendreau M, Mansini R (2016) The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: a branch-and-price approach. Eur J Oper Res 148:59–71MathSciNetMATH

Manerba D, Mansini R, Riera-Ledesma J (2017) The traveling purchaser problem and its variants. Eur J Oper Res 259(1):1–18MathSciNetCrossRef

Mansini R, Tocchella B (2009) The traveling purchaser problem with budget constraint. Comput Oper Res 36(7):2263–2274MathSciNetCrossRef

Narayanaswamy N, Raman V, Ramanujan M, Saurabh S (2012) LP can be a cure for parameterized problems. In: STACS’12 (29th symposium on theoretical aspects of computer science), vol 14. LIPIcs, pp 338–349

Palomo-Martínez PJ, Salazar-Aguilar MA (2019) The bi-objective traveling purchaser problem with deliveries. Eur J Oper Res 273(2):608–622MathSciNetCrossRef

Ramesh T (1981) Traveling purchaser problem. Opsearch 18(1–3):78–91MATH

Ravi R, Salman FS (1999) Approximation algorithms for the traveling purchaser problem and its variants in network design. In: Algorithms-ESA’99, pp 29–40

Riera-Ledesma J, Salazar-González JJ (2006) Solving the asymmetric traveling purchaser problem. Ann Oper Res 144(1):83–97MathSciNetCrossRef

Singh KN, van Oudheusden DL (1997) A branch and bound algorithm for the traveling purchaser problem. Eur J Oper Res 97(3):571–579CrossRef

Titel: Parameterized algorithms and complexity for the traveling purchaser problem and its variants
verfasst von: Mingyu Xiao
Jianan Zhang
Weibo Lin
Publikationsdatum: 17.06.2020
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00608-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2022

Study on the incentive and coordination mechanism of tumor healthcare alliance based on evolutionary game

The optimization of self-interference in wideband full-duplex phased array with joint transmit and receive beamforming

An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time

Surface polygonization of 3D objects using norm similarity

On the enumeration of minimal non-pairwise compatibility graphs

HM-EIICT: Fairness-aware link prediction in complex networks using community information

Premium Partner