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

Gözde Önder Uzun; İmdat Kara

doi:10.17341/gazimmfd.777322

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

Ö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

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 proﬁts, 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.

Ayrıntılar

Birincil Dil

Türkçe

Konular

Mühendislik

Bölüm

Araştırma Makalesi

Yazarlar

Gözde Önder Uzun ^*
0000-0001-7527-0310
Türkiye

İmdat Kara
0000-0002-1756-2873
Türkiye

Yayımlanma Tarihi

10 Kasım 2021

Gönderilme Tarihi

5 Ağustos 2020

Kabul Tarihi

15 Temmuz 2021

Yayımlandığı Sayı

Yıl 2022 Cilt: 37 Sayı: 1

DOI

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

IZ

https://izlik.org/JA52HC63JD

Kaynak Göster

RIS / Bibtex

APA

Önder Uzun, G., & Kara, İ. (2021). Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37(1), 529-540. https://doi.org/10.17341/gazimmfd.777322

AMA

1.Önder Uzun G, Kara İ. Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller. GUMMFD. 2021;37(1):529-540. doi:10.17341/gazimmfd.777322

Chicago

Önder Uzun, Gözde, ve İmdat Kara. 2021. “Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37 (1): 529-40. https://doi.org/10.17341/gazimmfd.777322.

EndNote

Önder Uzun G, Kara İ (01 Kasım 2021) Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37 1 529–540.

IEEE

[1]G. Önder Uzun ve İ. Kara, “Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller”, GUMMFD, c. 37, sy 1, ss. 529–540, Kas. 2021, doi: 10.17341/gazimmfd.777322.

ISNAD

Önder Uzun, Gözde - Kara, İmdat. “Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37/1 (01 Kasım 2021): 529-540. https://doi.org/10.17341/gazimmfd.777322.

JAMA

1.Önder Uzun G, Kara İ. Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller. GUMMFD. 2021;37:529–540.

MLA

Önder Uzun, Gözde, ve İmdat Kara. “Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, c. 37, sy 1, Kasım 2021, ss. 529-40, doi:10.17341/gazimmfd.777322.

Vancouver

1.Gözde Önder Uzun, İmdat Kara. Zaman pencereli çok ekipli gecikme problemi için yeni matematiksel modeller. GUMMFD. 01 Kasım 2021;37(1):529-40. doi:10.17341/gazimmfd.777322