KARGO OPSİYONLU GEZGİN SATIN ALICI PROBLEMİ

Abstract

Yapılan bu çalışmada gezgin satıcı probleminin bilinen bir varyasyonu olan gezgin satın alıcı problemi (GSAP) e-ticaret faaliyetleri kapsamında genişletilmiştir. Son yıllarda kullanımı oldukça artan e-ticaret mağazaları ile müşteriler ürünlere kargo teslimatı yoluyla ulaşabilmektedir. Yapılan çalışmada artan e-ticaret faaliyetleri dikkate alınarak kargo teslimatı ile yapılan satın alımlar GSAP için uyarlanmıştır. Kargo opsiyonlu gezgin satın alıcı problemi (KO-GSAP) olarak adlandırılan problemde satın alıcı belirli adet ürün çeşidine ait talebi belirli marketlerden karşılaması gerekmektedir. Bu kapsamda belirli ürünler sanal market mağazalarından kargo teslimatı yoluyla veya marketi ziyaret ederek satın alınabilmektedir. Problemde amaç, satın alıcının toplam maliyetini en aza indirecek satın alma ve rota planının oluşturulmasıdır. Dikkate alınan problem için karışık tamsayılı bir model formülasyonu geliştirilmiştir. Elde edilen modelin çözümü için iki aşamalı bir çözüm yaklaşımı geliştirilmiştir. Geliştirilmiş olan çözüm yaklaşımının etkinliğini analiz edebilmek için GSAP için yaygın olarak kullanılan bir problem seti kullanılmış ve bu problem seti KO-GSAP’ye adapte edilmiştir. Yapılan sayısal çalışmalarda çözüm yaklaşımının performansı farklı senaryolarda elde edilen çözümler üzerinden kanıtlanmıştır.

Keywords

• Gezgin satın alıcı problemi
• Matematiksel modelleme
• Rota optimizasyonu

TRAVELING PURCHASER PROBLEM WITH CARGO OPTION

Abstract

In this study, the traveling purchaser problem (TPP), which is a well-known variation of the traveling salesman problem, has been extended based on e-commerce activities. With e-commerce stores, which have become higly popular in recent years, customers can access products by cargo delivery. Considering the increasing e-commerce activities, this study adapted the procurement made by cargo deliveries to the GSAP. In the problem, called the traveling purchaser problem with cargo option (TPP-CO), the purchaser has to meet the demand for a certain number of products from a number of markets. In this context, a set of products can be purchased from e-marketplaces with cargo delivery or by visiting the market. The aim of the problem is to generate a procurement and route plan that will minimize the total cost of the purchaser. A mixed integer model formulation was developed for the problem considered. To solve the model, a two-stage solution approach was developed. In order to analyze the effectiveness of the developed solution approach, a problem set widely used for TPP was used, and this problem set was adapted to TPP-CO. In the numerical studies, the performance of the solution approach was proven through the solutions obtained in different scenarios.

Keywords

• Traveling purchaser problem
• Mathematical modelling
• Route optimization

References

1. Almeida C.P., Gonçalves R.A., Goldbarg E.F., Goldbarg M.C., Delgado M.R., 2012. An experimental analysis of evolutionary heuristics for the biobjective traveling purchaser problem. Annals of Operations Research. 199. 305-341.
2. Batista-Galván M., Riera-Ledesma J., Salazar-González. J.J., 2013. The Traveling Purchaser Problem with Multiple Stacks and Deliveries: A Branch-and-Cut Approach. Computers & Operations Research. 40. 2103-2115.
3. Bernardino R., Paias A., 2018. Metaheuristics Based on Decision Hierarchies for the Traveling Purchaser Problem. International Transactions in Operational Research. 25. 1269-1295.
4. Bianchessi N., Mansini R., Speranza M.G., 2014. The Distance Constrained Multiple Vehicle Traveling Purchaser Problem. European Journal of Operational Research. 235. 73-87.
5. Choi M.J., Lee S.H., 2011. The Multiple Traveling Purchaser Problem for Maximizing System’s Reliability with Budget Constraints. Expert Systems with Applications. 38. 9848-9853.
6. Cheaitou A., Hamdan S., Larbi R., Alsyouf I., 2020. Sustainable traveling purchaser problem with speed optimization. International Journal of Sustainable Transportation. 1-20.
7. Cheaitou A., Hamdan S., Quteineh H., Alsyouf I., Shikhli A., 2025. Population-based and hybrid heuristic approaches for the bi-objective sustainable multi-vehicle traveling purchaser problem. Journal of the Operational Research. In press.
8. Cuellar‐Usaquén D., Gomez C., Álvarez‐Martínez D., 2023. A GRASP/Path‐Relinking algorithm for the traveling purchaser problem. International Transactions in Operational Research. 30. 831-857.

9. Goldbarg M.C., Bagi L.B., Goldbarg E.F.G., 2009. Transgenetic algorithm for the traveling purchaser problem. European Journal of Operational Research. 199. 36-45.
10. Golden B., Levy L., Dahl R., 1981. Two generalizations of the traveling salesman problem. Omega. 9. 439-441.
11. Gouveia L., Paias A., Voß S., 2011. Models for a Traveling Purchaser Problem with Additional Side-Constraints. Computers & Operations Research. 38. 550-558.
12. Hasanpour Jesri Z.S., Eshghi K., Rafiee M., Van Woensel T., 2022. The multi-depot traveling purchaser problem with shared resources. Sustainability 14. 10190.
13. Kang H.-Y., Lee A.H., Yeh Y.-F., 2021. An optimization approach for traveling purchaser problem with environmental impact of transportation cost. Kybernetes. 50. 2289-2317.
14. Kang S., Ouyang Y., 2011. The Traveling Purchaser Problem with Stochastic Prices: Exact and Approximate Algorithms. European Journal of Operational Research. 209. 265-272.
15. Khatua S., Maity S., De D., Nielsen I., Maiti M., 2024. IoT-ML-enabledmultipath traveling purchaser problem using variable length genetic algorithm. Annals of Operations Research. In press.
16. Kucukoglu I., 2022. The Traveling Purchaser Problem with Fast Service Option. Computers & Operations Research. 141. 105700.
17. Kucukoglu I., Cattrysse D., Vansteenwegen P., 2023. Simulated Annealing for the Traveling Purchaser Problem in Cold Chain Logistics. Lecture Notes in Mechanical Engineering: Advances in Intelligent Manufacturing and Service System Informatics. Springer.
18. Kucukoglu I., Vansteenwegen P., Cattrysse D., 2024. The traveling purchaser problem for perishable foods. Computers & Industrial Engineering. 195. 110424.
19. Langevin A., Soumis F., 1990. Classification of Travelling Salesman Problem Formulations. Operations Research Letters. 9. 127-132.
20. Laporte G., Riera-Ledesma J., Salazar-González J.J., 2003. A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem. Operations Research. 51. 940-951.
21. Manerba D., Mansini R., 2015. A Branch‐and‐Cut Algorithm for the Multi‐Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints. Networks. 65. 139-154.
22. Manerba D., Mansini R., Riera-Ledesma J., 2017. The Traveling Purchaser Problem and Its Variants. European Journal of Operational Research. 259. 1-18.
23. Mansini R., Tocchella B., 2009. The Traveling Purchaser Problem with Budget Constraint. Computers & Operations Research. 36. 2263-2274.
24. Miller C.E., Tucker A.W., Zemlin R.A., 1960. Integer Programming Formulations and Traveling Salesman Problems. Journal of the ACM. 7. 326–329.
25. Ochi L., Silva M., Drummond L., Metaheuristics based on GRASP and VNS for solving the Traveling Purchaser Problem. Proc. of the IV Metaheuristic International Conference (MIC’2001), July 16-20 2001 Porto, Portugal. 489-494.
26. Ong H.L., 1982. Approximate algorithms for the travelling purchaser problem. Operations Research Letters. 1. 201-205.
27. Pearn W.L., 1991. On the traveling purchaser problem. Department of Industrial Engineering and Management, National Chiao Tung University: Department of Industrial Engineering and Management, National Chiao Tung University.
28. Pradhan K., Basu S., Thakur K., Maity S., Maiti M., 2020. Imprecise modified solid green traveling purchaser problem for substitute items using quantum-inspired genetic algorithm. Computers & Industrial Engineering. 147. 106578.
29. Ramesh T., 1981. Traveling Purchaser Problem. Opsearch. 18. 78-91.
30. Riera-Ledesma J., Salazar-González J.J., 2013. A Column Generation Approach for a School Bus Routing Problem with Resource Constraints. Computers & Operations Research. 40. 566-583.
31. Roy A., Gao R., Jia L., Maity S., Kar S., 2020. A noble genetic algorithm to solve a solid green traveling purchaser problem with uncertain cost parameters. American Journal of Mathematical Management Sciences. 1-15.
32. Roy A., Maity S., Moon I., 2023. Multi-Vehicle Clustered Traveling Purchaser Problem Using a Variable-Length Genetic Algorithm. Engineering Applications of Artificial Intelligence. 123. 106351.
33. Voß S., 1996. Dynamic Tabu Search Strategies for the Traveling Purchaser Problem. Annals of Operations Research. 63. 253-275.
34. Yuan H., Zhu R., Yang W., Song S., You K., Fan W., Chen P., 2025. Deep Reinforcement Learning for Traveling Purchaser Problems. Preprint submitted to Expert Systems with Applications.