SavedAdd your journal

Journals / Uludağ Üniversitesi Mühendislik Fakültesi Dergisi / 2026 / Cilt: 30 Sayı: 2

Discounted Traveling Purchaser Problem in Market Chains

ZİNCİR MARKET HARCAMALARINDA İNDİRİMLİ GEZGİN SATIN ALICI PROBLEMİ

Özlem Okumuş0009-0000-0173-5074
İlker Küçükoğlu(Bursa Uludağ Üniversitesi)0000-0002-5075-0876
Pages
459–472
Publication Date
2025-08-20
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The results show that TA is able to produce more efficient results in shorter times.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:This study addresses the traveling purchaser problem (TPP), which is a well-known extension of the traveling salesman problem as presented in the literature.
📊
Key Findings & Data:A problem set has been generated to test the effectiveness of the developed TS in solving the MCD-TPP.
💡
Conclusion & Impact:The results show that TA is able to produce more efficient results in shorter times.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Gezgin satın alıcı problemi · Matematiksel modelleme · Tabu arama algoritması

Abstract

This study addresses the traveling purchaser problem (TPP), which is a well-known extension of the traveling salesman problem as presented in the literature. In TPP, a purchaser traveling from a central depot visits a number of markets at different locations to satisfy a given product demand and then returns to the depot. The aim of the problem is to find a procurement and route plan that minimizes the total procurement and transportation cost of the purchaser. In this study, TPP is extended by considering the promotional practices of chain markets. In this context, the purchaser may earn a discount from a market chain if he/she makes a certain number of market visits and purchases a certain amount of products. In this way, a reduction in the total cost of the purchaser can be achieved. In order to solve the problem, which is called the market chain discounted traveling purchaser problem (MCD-TPP), a tabu search (TS) algorithm is proposed. A problem set has been generated to test the effectiveness of the developed TS in solving the MCD-TPP. In the computational experiments, the TS is compared to the GUROBI solver. The results show that TA is able to produce more efficient results in shorter times.

Özet

Bu çalışma literatürde iyi bilinen gezgin satıcı probleminin genişletilmiş bir versiyonu olan gezgin satın alıcı problemi (GSAP) dikkate almaktadır. GSAP’de merkezi bir depodan dolaşıma çıkan satın alıcı belirli ürün talebini karşılamak üzere farklı lokasyonlarda bulunan marketleri ziyaret ederek tekrar depoya geri dönmektedir. Problemde amaç satın alıcının toplam dolaşım ve satın alma maliyetini minimize edecek satın alma ve rota planının bulunmasıdır. Yapılan bu çalışmada GSAP, zincir marketlerin promosyon uygulamaları dikkate alınarak genişletilmiştir. Bu kapsamda, gezgin satın alıcı belirli zincir market grubundan belirli sayıda ve belirli miktarda satın alma işlemi yapması durumunda indirim kazanabilmektedir. Bu sayede satın alıcının toplam maliyetinde bir düşüş sağlanabilmektedir. Zincir market harcamalarında indirimli gezgin satın alıcı problemi (ZMHİ-GSAP) olarak adlandırılan problemin çözümü için bir tabu arama (TA) algoritması geliştirilmiştir. Geliştirilmiş olan TA’nın ZMHİ-GSAP’nin çözümünde etkinliğini test edebilmek için bir problem seti üretilmiştir. Yapılan sayısal çalışmalarda TA, GUROBI çözücüsü ile karşılaştırılmıştır. Elde edilen sonuçlar, TA’nın kısa sürelerde daha etkin sonuçlar üretebildiğini göstermiştir.

🔖

Cite This Article

Okumuş, Ö., Küçükoğlu, İ. (2025). Discounted Traveling Purchaser Problem in Market Chains. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi, Cilt: 30 Sayı: 2, 459–472. https://doi.org/10.17482/uumfd.1571735

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (33)

  1. Batista-Galván. M. Riera-Ledesma. J. ve Salazar-González. J. J. (2013). The traveling purchaser problem. with multiple stacks and deliveries: A branch-and-cut approach. Computers & Operations Research. 40(8). 2103-2115. doi.org/10.1016/j.cor.2013.02.007
  2. Bianchessi. N. Mansini. R. ve Speranza. M. G. (2014). The distance constrained multiple vehicle traveling purchaser problem. European Journal of Operational Research. 235(1). 73-87. doi.org/10.1016/j.ejor.2013.10.018
  3. Choi. M.J. ve Lee. S.H. (2011). The multiple traveling purchaser problem for maximizing system’s reliability with budget constraints. Expert Systems with Applications. 38(8). 9848-9853. doi.org/10.1016/j.eswa.2011.02.018
  4. Gendreau. M. Manerba. D. ve Mansini. R. (2016). The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach. European Journal of Operational Research. 248(1). 59-71. doi.org/10.1016/j.ejor.2015.06.073
  5. Glover. F. (1989) Tabu search – Part I. ORSA Journal on Computing. 1(3). 190-206.
  6. Glover. F. (1990). Tabu search – Part II. ORSA Journal on Computing. 2(1). 4-32.
  7. Gouveia. L. Paias. A. ve Voß. S. (2011). Models for a traveling purchaser problem with additional side-constraints. Computers and Operations Research. 38(2). 550-558. doi.org/10.1016/j.cor.2010.07.016
  8. Hasanpour Jesri. Z.S. Eshghi. K. Rafiee. M. ve Van Woensel. T. (2022). The multi-depot traveling purchaser problem with shared resources. Sustainability. 14(16). 10190. doi.org/10.3390/su141610190
  9. Kang. S. ve Ouyang. Y. (2011). The traveling purchaser problem with stochastic prices: Exact and approximate algorithms. European Journal of Operational Research. 209(3). 265-272. doi.org/10.1016/j.ejor.2010.09.012
  10. Kucukoglu. I. (2022). The traveling purchaser problem with fast service option. Computers and Operations Research. 141. 105700. doi.org/10.1016/j.cor.2022.105700
  11. Kucukoglu. I. Vansteenwegen. P. ve Cattrysse. D. (2023). The traveling purchaser problem for perishable foods. Computers and Industrial Engineering. 195. 110424. doi.org/10.1016/j.cie.2024.110424
  12. Laporte. G. Riera-Ledesma. J. ve Salazar-González. J.J. (2003). A branch-and-cut algorithm for the undirected traveling purchaser problem. Operations Research. 51(6). 940-951. doi.org/10.1287/opre.51.6.940.24921
  13. Maji. S. Pradhan. K. Maity. S. Nielsen. I.E. Giri. D. ve Maiti. M. (2023). Multipath traveling purchaser problem with time-dependent market structure using quantum-inspired variable length genetic algorithm. Computers & Industrial Engineering. 186. 109710. doi.org/https://doi.org/10.1016/j.cie.2023.109710
  14. Manerba. D. ve Mansini. R. (2015). A branch-and-cut algorithm for the multi-vehicle traveling purchaser problem with pairwise incompatibility constraints. Networks. 65(2). 139-154. doi.org/10.1002/net.21588
  15. Manerba. D. Mansini. R. ve Riera-Ledesma. J. (2017). The traveling purchaser problem and its variants. European Journal of Operational Research. 259(1). 1-18. doi.org/10.1016/j.ejor.2016.12.017
  16. Mansini. R. ve Tocchella. B. (2009). The traveling purchaser problem with budget constraint. Computers & Operations Research. 36(7). 2263-2274. doi.org/10.1016/j.cor.2008.09.001
  17. Miller. C.E. Tucker. A.W. ve Zemlin. R.A. (1960). Integer programming formulation of traveling salesman problems. Journal of the Association for Computing Machinery. 7(4). 326–329.
  18. Palomo-Martínez. P.J. ve Salazar-Aguilar. M.A. (2019). The bi-objective traveling purchaser problem with deliveries. European Journal of Operational Research. 273(2). 608-622. doi.org/10.1016/j.ejor.2018.08.039
  19. Pearn. W. (1991). On the traveling purchaser problem. Teknik Rapor.
  20. Riera-Ledesma. J. ve Salazar-González. J.J. (2013). A column generation approach for a school bus routing problem with resource constraints. Computers & Operations Research. 40(2). 566-583. doi.org/10.1016/j.cor.2012.08.011
  21. Roy. A. Maity. S. ve Moon. I. (2023). Multi-vehicle clustered traveling purchaser problem using a variable-length genetic algorithm. Engineering Applications of Artificial Intelligence. 123. 106351. doi.org/10.1016/j.engappai.2023.106351
  22. Voß. S. (1996). Dynamic tabu search strategies for the traveling purchaser problem. Annals of Operations Research. 63(2). 253-275.
  23. Batista-Galván. M. Riera-Ledesma. J. ve Salazar-González. J. J. (2013). The traveling purchaser problem. with multiple stacks and deliveries: A branch-and-cut approach. Computers & Operations Research. 40(8). 2103-2115. doi.org/10.1016/j.cor.2013.02.007
  24. Bianchessi. N. Mansini. R. ve Speranza. M. G. (2014). The distance constrained multiple vehicle traveling purchaser problem. European Journal of Operational Research. 235(1). 73-87. doi.org/10.1016/j.ejor.2013.10.018
  25. Gendreau. M. Manerba. D. ve Mansini. R. (2016). The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: A branch-and-price approach. European Journal of Operational Research. 248(1). 59-71. doi.org/10.1016/j.ejor.2015.06.073
  26. Gouveia. L. Paias. A. ve Voß. S. (2011). Models for a traveling purchaser problem with additional side-constraints. Computers and Operations Research. 38(2). 550-558. doi.org/10.1016/j.cor.2010.07.016
  27. Hasanpour Jesri. Z.S. Eshghi. K. Rafiee. M. ve Van Woensel. T. (2022). The multi-depot traveling purchaser problem with shared resources. Sustainability. 14(16). 10190. doi.org/10.3390/su141610190
  28. Kucukoglu. I. Vansteenwegen. P. ve Cattrysse. D. (2023). The traveling purchaser problem for perishable foods. Computers and Industrial Engineering. 195. 110424. doi.org/10.1016/j.cie.2024.110424
  29. Laporte. G. Riera-Ledesma. J. ve Salazar-González. J.J. (2003). A branch-and-cut algorithm for the undirected traveling purchaser problem. Operations Research. 51(6). 940-951. doi.org/10.1287/opre.51.6.940.24921
  30. Maji. S. Pradhan. K. Maity. S. Nielsen. I.E. Giri. D. ve Maiti. M. (2023). Multipath traveling purchaser problem with time-dependent market structure using quantum-inspired variable length genetic algorithm. Computers & Industrial Engineering. 186. 109710. doi.org/https://doi.org/10.1016/j.cie.2023.109710
  31. Manerba. D. Mansini. R. ve Riera-Ledesma. J. (2017). The traveling purchaser problem and its variants. European Journal of Operational Research. 259(1). 1-18. doi.org/10.1016/j.ejor.2016.12.017
  32. Miller. C.E. Tucker. A.W. ve Zemlin. R.A. (1960). Integer programming formulation of traveling salesman problems. Journal of the Association for Computing Machinery. 7(4). 326–329.
  33. Roy. A. Maity. S. ve Moon. I. (2023). Multi-vehicle clustered traveling purchaser problem using a variable-length genetic algorithm. Engineering Applications of Artificial Intelligence. 123. 106351. doi.org/10.1016/j.engappai.2023.106351