Discounted Traveling Purchaser Problem in Market Chains

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.

Keywords

• Traveling purchaser problem
• Mathematical modelling
• Tabu search algorithm

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

Abstract

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.

Keywords

• Gezgin satın alıcı problemi
• Matematiksel modelleme
• Tabu arama algoritması

References

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.