A TWO-PHASE SOLUTION APPROACH FOR THE TRAVELING PURCHASER PROBLEM IN COLD CHAIN LOGISTICS

Abstract

This paper introduces an extension of the well-known traveling purchaser problem in the literature by taking into account the procurement of perishable foods in cold chain logistics. The problem in which transportation operations are carried out based on the perishable product conditions is called the traveling purchaser problem in cold chain logistics (TPP-CCL). The TPP-CCL considers a set of perishable food demands to be purchased from a number of markets, where the foods have to be transported by a temperature-controlled vehicle. The aim of the problem is to find the best procurement and route plan for the purchaser that minimizes the total energy cost of the vehicle, damage cost of foods and purchasing cost. The problem is formulated as a nonlinear mixed-integer programming model and solved by using a two-phase solution procedure. In the first phase of the solution methodology, a rough solution is obtained through a solution construction method. Then the solution observed in the first phase is improved by using the GUROBI solver, where the solver is terminated at the end of a specific time limit. In the computational studies, the performance of the proposed solution methodology is analyzed on a benchmark problem set including different sized instances.

Keywords

• Traveling Purchaser Problem
• Cold Chain Logistics
• Mathematical Modelling
• Heuristic Methods

SOĞUK ZİNCİR LOJİSTİĞİNDE GEZGİN SATIN ALICI PROBLEMİ İÇİN İKİ AŞAMALI BİR ÇÖZÜM YÖNTEMİ

Abstract

Bu çalışma, soğuk zincir lojistiğinde bozulabilir gıdaların satın alınması işlemini dikkate alarak literatürde iyi bilinen gezgin satın alıcı probleminin genişletilmiş bir halini sunmaktadır. Taşıma işlemlerinin bozulabilir ürün şartlarına dayalı gerçekleştirildiği bu problem, soğuk zincir lojistiğinde gezgin satın alıcı problemi (SZL-GSAP) olarak adlandırılmıştır. SZL-GSAP, sıcaklık kontrollü bir araç ile taşınması gereken çeşitli ürün taleplerinin belirli sayıda marketlerden satın alınması işlemini dikkate almaktadır. Problemin amacı, satın alıcı için sıcaklık kontrollü aracın enerji maliyetinin, ürün bozulma maliyetinin ve satın alma maliyetinin toplamını minimize edecek satın alma ve rota planını elde etmektir. Problem, doğrusal olmayan bir karma tamsayılı programlama modeli olarak formüle edilmiş ve iki aşamalı bir yöntem kullanılarak çözülmüştür. Çözüm yönteminin ilk aşamasında, bir çözüm kurucu yöntem kullanılarak problem için kaba bir sonuç elde edilmektedir. Daha sonra ilk aşamada elde edilen çözüm, GUROBI çözücüsü kullanılarak belirli bir zaman kısıtı içerisinde geliştirilmektedir. Sayısal uygulamalarda, önerilen çözüm yönteminin performansı, farklı büyüklükte örnekleri içeren bir problem seti üzerinde analiz edilmiştir.

Keywords

• Gezgin Satın Alıcı Problemi
• Soğuk Zincir Lojistiği
• Matematiksel Modelleme
• Sezgisel Yöntemler

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(1), 305-341.
2. Amorim, P., Parragh, S.N., Sperandio, F., Almada-Lobo, B., 2014. A Rich Vehicle Routing Problem Dealing with Perishable Food: A Case Study. TOP, 22, 489-508.
3. Angelelli, E., Gendreau, M., Mansini, R., Vindigni, M., 2017. The Traveling Purchaser Problem with Time-Dependent Quantities. Computers & Operations Research, 82, 15-26.
4. Awad, M., Ndiaye, M., Osman, A., 2021. Vehicle Routing in Cold Food Supply Chain Logistics: A Literature Review. The International Journal of Logistics Management, 32(2), 592-617.
5. Bianchessi, N., Irnich, S., Tilk, C., 2021. A Branch-Price-and-Cut Algorithm for the Capacitated Multiple Vehicle Traveling Purchaser Problem with Unitary Demand. Discrete Applied Mathematics, 288, 152-170.
6. Bianchessi, N., Mansini, R., Speranza, M.G., 2014. The Distance Constrained Multiple Vehicle Traveling Purchaser Problem. European Journal of Operational Research, 235(1), 73-87.
7. Boctor, F.F., Laporte, G., Renaud, J., 2003. Heuristics for the Traveling Purchaser Problem. Computers & Operations Research, 30, 491-504.
8. Bontoux, B., Feillet, D., 2008. Ant Colony Optimization for the Traveling Purchaser Problem. Computers & Operations Research, 35(2), 628-637.

9. Cambazard, H., Penz, B., 2012. A Constraint Programming Approach for the Traveling Purchaser Problem. Principles and Practice of Constraint Programming – CP 2004 (pp. 735-749). Springer.
10. Cheaitou, A., Hamdan, S., Larbi, R., Alsyouf, I., 2020. Sustainable Traveling Purchaser Problem with Speed Optimization. International Journal of Sustainable Transportation, 1-20.
11. Chen, H.-K., Hsueh, C.-F., Chang, M.-S. 2009. Production Scheduling and Vehicle Routing with Time Windows for Perishable Food Products. Computers & Operations Research, 36, 2311-2319.
12. Chen, L., Liu, Y., Langevin, A. 2019. A Multi-Compartment Vehicle Routing Problem in Cold-Chain Distribution. Computers & Operations Research, 111, 58-66.
13. 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(8), 9848-9853.
14. Gendreau, M., Manerba, D., 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.
15. Golden, B., Levy, L., Dahl, R., 1981. Two Generalizations of the Traveling Salesman Problem. Omega, 9(4), 439-441.
16. Gouveia, L., Paias, A., Voß, S., 2011. Models for a Traveling Purchaser Problem with Additional Side Constraints. Computers & Operations Research, 38(2), 550-558.
17. Hamdan, S., Larbi, R., Cheaitou, A., Alsyouf, I., 2017. Green Traveling Purchaser Problem Model: A Bi-Objective Optimization Approach. 7th International Conference on Modeling, Simulation, and Applied Optimization (ICMSAO), Sharjah, United Arab Emirates, 4-6 Nisan.
18. Hsu, C.-I., Hung, S.-F., Li, H.-C., 2007. Vehicle Routing Problem with Time Windows for Perishable Food Delivery. Journal of Food Engineering, 80, 465-475.
19. Kang, S., Ouyang, Y., 2011. The Traveling Purchaser Problem with Stochastic Prices: Exact and Approximate Algorithms. European Journal of Operational Research, 209(3), 265-272.
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(6), 940-951.
21. Li, Y., Lim, M.K., Tseng, M.-L. 2019. A Green Vehicle Routing Model Based on Modified Particle Swarm Optimization for Cold Chain Logistics. Industrial Management & Data Systems, 119(3), 473-494.
22. Liu, G., Hu, J., Yang, Y., Xia, S., Lim, M.K. 2020. Vehicle Routing Problem in Cold Chain Logistics: A Joint Distribution Model with Carbon Trading Mechanisms. Resources, Conservation & Recycling, 156, 104715.
23. Manerba, D., Mansini, R., Riera-Ledesma, J., 2017. The Traveling Purchaser Problem and Its Variations. European Journal of Operational Reearch, 259(1), 1-18.
24. Mansini, R., Tocchella, B., 2009. The Traveling Purchaser Problem with Budget Constraint. Computers & Operations Research, 36(7), 2263-2274.
25. Ong, H.L., 1982. Approximate Algorithms for the Travelling Purchaser Problem. Operations Research Letters, 1(5), 201-205.
26. Osvald, A., Stirn, L.Z., 2008. A Vehicle Routing Algorithm for the Distribution of Fresh Vegetables and Similar Perishable Food. Journal of Food Engineering, 85, 285-295.
27. Palomo-Martínez, P.J., Salazar-Aguilar, M.A., 2019. The Bi-objective Traveling Purchaser Problem with Deliveries. European Journal of Operational Research, 273(2), 608-622.
28. Pearn, W.L. 1991. On the Traveling Purchaser Problem. Teknik Rapor.
29. Pearn, W.L., Chien, R., 1998. Improved Solutions for the Traveling Purchaser Problem. Computers & Operations Research, 25(11), 879-885.
30. Qi, C., Hu, L., 2020. Optimization of Vehicle Routing Problem for Emergency Cold Chain Logistics Based on Minimum Loss. Physical Communication, 40, 101085.
31. Riera-Ledesma, J., Salazar-González, J. J., 2005. The Biobjective Travelling Purchaser Problem. European Journal of Operational Research, 160(3), 599-613.
32. Riera-Ledesma, J., Salazar-González, J.-J., 2006. Solving the Asymmetric Traveling Purchaser Problem. Annals of Operations Research, 144(1), 83-97.
33. Riera-Ledesma, J., Salazar-González, J.-J., 2012. Solving School Bus Routing Using the Multiple Vehicle Traveling Purchaser Problem: A Branch-and-Cut Approach. Computers & Operations Research, 39(2), 391-404.
34. Singh, K.N., van Oudheusden, D.L., 1997. A Branch and Bound Algorithm for the Traveling Purchaser Problem. European Journal of Operational Research, 97(3), 571-579.
35. Song, M.-X., Li, J.-Q., Han, Y.-Q., Han, Y.-Y., Liu, L.-L., Sun, Q. 2020. Metaheuristics for Solving the Vehicle Routing Problem with the Time Windows and Energy Consumption in Cold Chain Logistics. Applied Soft Computing Journal, 95, 106561.
36. Teeninga, A., Volgenant, A., 2004. Improved Heuristics for the Traveling Purchaser Problem. Computers & Operations Research, 31(1), 139-150.
37. Voß, S., 1996. Dynamic Tabu Search Strategies for the Traveling Purchaser Problem. Annals of Operations Research, 63(2), 253-275.
38. Wang, Z., Wen, P., 2020. Optimization of a Low-Carbon Two-Echelon Heterogeneous-Fleet Vehicle Routing for Cold Chain Logistics under Mixed Time Window. Sustainability, 2020, 1-22.
39. Zhang, L., Gao, Y., Sun, Y., Fei, T., Wang, Y. 2019. Application on Cold Chain Logistics Routing Optimization Based on Improved Genetic Algorithm. Automatic Control and Computer Sciences, 53(2), 169-180.