Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller

Yıl 2022, Cilt: 37 Sayı: 1, 529 - 540, 10.11.2021

Gözde Önder Uzun İmdat Kara

https://doi.org/10.17341/gazimmfd.777322

Öz

Gecikme (latency) problemi (GP), gezgin satıcı probleminin (GSP) önemli bir türünü oluşturmaktadır. Problem, bir hareketlinin (kişi, araç, ekip vb.) verilen bir başlangıç noktasından hareket edip tüm müşterileri ziyaret ederek toplam gecikmeyi en küçük yapan Hamilton yolunu veya turunu bulmaktır. Gecikme, bir müşterinin talebinin karşılanıncaya kadar geçen süreyi ifade etmektedir. Zaman pencereli çok ekipli (gezginli) GP (ZPÇGP) ise her biri başlangıç düğümünden başlayıp, tüm müşterilerin belirlenmiş olan en erken ve en geç ziyaret zamanını ifade eden zaman penceresi aralığında talebini karşılayarak, toplam gecikmeyi en küçük yapan k adet turu veya yolu bulmayı amaçlamaktadır. Problem, düğümler arası seyahat gezgine (ekibe, araca) bağlı değil ise homojen, gezgine bağlı ise heterojen ZPÇGP olarak ele alınmaktadır. Kaynaklar incelendiğinde homojen durum için bir matematiksel model ve heterojen durum için de bir matematiksel model olduğu görülmüştür. Bu çalışmada, homojen ve heterojen durum için, polinom sayıda karar değişkenine ve kısıta sahip, matematiksel modeller önerilmiştir. Kaynaklarda var olan ve bu çalışmada geliştirilmiş olan matematiksel modeller kıyaslama problemleri kullanılarak farklı ekip sayıları için analiz edilmiştir. Sonuçlar CPU süreleri ve doğrusal programlama gevşetme değerlerinin en iyi değerden oransal sapmaları açısından karşılaştırılmıştır. Sonuç olarak, ZPÇGP için geliştirilen yeni matematiksel modellerin kaynaklarda var olan modellerden her problemde çok daha üstün olduğu görülmüştür.

Anahtar Kelimeler

Gecikme problemi, rotalama, çok gezgin, zaman penceresi, matematiksel modelleme

Kaynakça

• Conway, R., Maxwell, W., Miller, L., Theory of schduling, Addison-Wesley, 1967.
• Tsitsiklis, J. N., Special cases of traveling salesman and repairman problems with time windows, Networks, 22, 263-282, 1992.
• Fischetti, M., Laporte, G., Martello, S., The deliveryman problem and cumulative matroids, Oper. Res., 41 (6), 1055-1064, 1993.
• Bianco, L., Mingozzi, A., Ricciardelli, S., The traveling salesman problem with cumulative costs, Networks, 23 (2), 81-91, 1993.
• Zhang, H., Tong, W., Lin, G., Xu, Y., Online minimum latency problem with edge uncertainty, Eur. J. Oper. Res., 273 (2), 418-429, 2019.
• Avcı, M., Avcı, M. G., A GRASP with iterated local search for the traveling repairman problem with profits, Computers and Industrial Engineering, 113 (C), 323-332, 2017.
• Jmal, S., Haddar, B., Chabchoub, H., Apply the quantum particle swarm optimization for the K-traveling repairman problem, Soft Computing, 23 (1), 12547-12560, 2019.
• Martin, C.S. ve Salavatipour, M.R., Approximation Algorithms for Capacitated k-Travelling Repairmen Problems, 27th International Symposium on Algorithms and Computation (ISAAC 2016), Sidney-Avustralya, 1-12, 12-14 Aralık, 2016.
• Nucamendi, S., Cardona-Valdes, Y., Angel-Bello, F., Minimizing customers’ waiting time in a vehicle routing problem with unit demands, Journal of Computer and Systems Sciences International, 54 (6), 886-881, 2015.
• Fakcharoenphol, J., Harrelson, C., Rao, S., The k-traveling repairmen problem, ACM Trans. Algorithms, 3 (4), 2007.
• Heilporn, G., Cordeau, J., Laporte, G., The delivery man problem with time windows, Discrete Optim., 7 (4), 269-282, 2010.
• Silva, M.M., Subramanian, A., Vidal, T., Ochi, L.S., A simple and effective metaheuristic for the minimum latency problem, Eur. J. Oper. Res., 221 (3), 513-520, 2012.
• Hmayer, A. ve Ezzine, I.O., CLARANS heuristic based approach for the k-traveling repairman problem, International Conference on Advanced Logistics and Transport (ICALT 2013), Susa-Tunus, 535-538, 29-31 Mayıs, 2013.
• Nucamendi-Guillén, S., Martínez-Salazar, I., Angel-Bello, F., Moreno-Vega, J.M., A mixed integer formulation and an efficient metaheuristic procedure for the k-travelling repairmen problem, Journal of the Operational Research Society, 67 (8), 1121-1134, 2016.
• Van Der Meer, R., Operational control of internal transport, Doktora Tezi, Erasmus Üniversitesi, Hollanda, 2000.
• Bjelic, N., Vidovic, M., Popovic, D., Variable neighboorhood search algorithm for heterogeneous traveling repairmen problem with time windows, Expert Syst. Appl., 40 (15), 5997-6006, 2013.
• Kara, I. ve Derya, T., Formulations for minimizing tour duration of the traveling salesman problem with time windows, 4th World Conference on Business, Economics and Management, 2015.
• Kara, I., Koc, O.N., Altıparmak, F., Dengiz, B., New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times, Optimization, 62 (10), 1309-1319, 2013.
• Dumas, Y., Desrosiers, J., Gelinas, R., Solomon, M., An optimal algorithm for the traveling salesman problem with time windows, Oper. Res., 43 (2), 367-371, 1995.
• Kara, İ, Önder Uzun, G., Derya, T., Formulations for the multiple traveling repairmen problem: computational analysis and some extensions, 7th International Conference on Industrial Engineering and Operations Management, Rabat-Fas, 11-13 Nisan, 2017.
• Angel-Bello, F., Cardona-Valdes, Y., Alvarez, A., Mixed integer formulations for the multiple minimum latency problem, Operational Research, 19 (2), 369-398, 2017.
• Muritiba, A.E.F., Bonates, T., Oliveira Da Silva, S., Iori, M., Branch-and-cut and iterated local search for the weighted k-traveling repairman problem: an application to the maintenance of speed cameras, https://arxiv.org/abs/1909.06226, Yayın tarihi Eylül 13, 2019.