ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL

Koc, Cagri; KARAOĞLAN, İSMAİL

ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL

Çağrı KOÇ, (Southampton Management School and Centre for Operational Research, Management Science and Information Systems (CORMSIS), University of Southampton, Southampton, United Kingdom)

İsmail KARAOĞLAN (Selçuk Üniversitesi, Endüstri Mühendisliği Bölümü, Konya)

Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi

11 6

Yıl: 2014 Cilt: 29 Sayı: 3 Sayfa Aralığı: 549 - 558 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL

Öz:

Bu çalışmada klasik Araç Rotalama Probleminin (ARP) genelleştirilmiş bir çeşidi olan Zaman Bağımlı Araç Rotalama Problemi (ZBARP) ele alınmıştır. ZBARP, ARPden farklı olarak, araç hızının düğümler arasında değişken olduğu durumlarda araç filosunun rotalanması olarak tanımlanmaktadır. ZBARP için literatürdeki modellerden farklı bir şekilde ilk olarak, ilk giren ilk çıkar (FIFO) özelliğini sağlayan, zamana bağlı hız fonksiyonunu göz önüne alan ve doğrusal yapıya sahip yeni bir karma tam sayılı matematiksel model geliştirilmiştir. Literatürden türetilen test problemleri üzerindeki deneysel çalışmalar sunulmuş ve modelin performansı en iyi çözüme ulaşma zamanı ve en iyi çözümden yüzde sapma değeri açısından değerlendirilmiştir. Çeşitli parametrelerin değişmesinin modelin performansı üzerindeki etkisinin anlaşılması için 3 farklı senaryo analizi oluşturulmuştur.

Anahtar Kelime:

A MATHEMATICAL MODEL FOR THE TIME-DEPENDENT VEHICLE ROUTING PROBLEM

Öz:

In this study, the Time-Dependent Vehicle Routing Problem (TDVRP) is considered which is a generalized version of the classical Vehicle Routing Problem (VRP). Unlike the VRP, the TDVRP can be defined as the routing a fleet of vehicle in which vehicle speeds are variable between the nodes. For the first time in literature, a new mathematical model, based on linear function, is developed for the TDVRP which considers the timedependent speed function that satisfies the first-in-first-out (FIFO) property and differs from the existing models in literature. Computational results on a large set of instances, generated from literature, are presented and the performance of the model evaluated in terms of computation time and percentage deviations to optimal solution. Three scenario analyses are conducted to assess the effect of changing several parameters on the model performance.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1. Toth, P. ve Vigo, D., The vehicle routing problem, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2002.
2. Clark, G. Ve Wright J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, Cilt 12, 568581, 1964.
3. Dantzig, G.B. ve Ramser, J.H., The truck dispatching problem, Management Science, Cilt 6, 8091, 1959.
4. Koç, Ç. ve Karaoğlan, İ., Çok kullanımlı ve zaman pencereli araç rotalama problemi için bir matematiksel model, Journal of the Faculty of Engineering and Architecture of Gazi University, Cilt 27, No 3, 569576, 2012.
5. Hezer, S. ve Kara, Y., Eşzamanlı dağıtımlı ve toplamalı araç rotalama problemlerinin çözümü için bakteriyel besin arama optimizasyonu tabanlı bir algoritma, Journal of the Faculty of Engineering and Architecture of Gazi University, Cilt 28, No 2, 373382, 2013.
6. Cordeau, J.-F., Laporte, G., Savelsbergh, M.W.P. ve Vigo, D., Vehicle routing. In: Barnhart, C., G. Laporte. (Eds.), Transportation, Handbooks in Operations Research and Management Science 14 367428 (Chapter 6). Elsevier, Amsterdam, The Netherlands, 2007.
7. Golden, B.L., Raghavan, S. ve Wasil, E.A., The Vehicle Routing Problem: Latest Advances and Recent Challenges, Operations Research Computer Science Interfaces. Springer, New York, 2008.
8. Malandraki, C. ve Daskin, M.S., "Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms", Transportation Science, Cilt 26, No 3, 185200, 1992.
9. Ahn, B. H. ve Shin, J. Y., Vehicle-routing with time windows and time-varying congestion, Journal of the Operational Research Society, Cilt 42, 393400, 1991.
10. Hill, A.V. ve Benton, W.C., "Modelling intra-city time-dependent travel speeds for vehicle scheduling problems", Journal of the Operational Research Society, Cilt 43, No 4, 343351, 1992.
11. Malandraki, C. ve Dial, R.B., "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem", European Journal of Operational Research, Cilt 90, No 1, 4555, 1996.
12. Park, Y. B., A solution of the bicriteria vehicle scheduling problems with time and area-depend travel speeds, Computers & Industrial Engineering, Cilt 38, 173187, 2000.
13. Jung, S. ve Haghani, A., Genetic Algorithm for the Time-Dependent Vehicle Routing Problem, Transportation Research Record, Cilt 1771, 164171, 2001.
14. Balseiro, S.R., Loiseau, I. ve Ramonet, J., "An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows", Computers & Operations Research, Cilt 38, No 6, 954966, 2011.
15. Ichoua, S., Gendreau, M. ve Potvin, J.Y., "Vehicle dispatching with time-dependent travel times", European Journal of Operational Research, Cilt 144, No 2, 379396, 2003.
16. Fleischmann, B., Gietz, M. ve Gnutzmann, S., "Time-varying travel times in vehicle routing", Transportation Science, Cilt 38, No 2, 160173, 2004.
17. Haghani, A. ve Jung, S., A dynamic vehicle routing problem with time-dependent travel times, Computers & Operations Research, Cilt 32, 29592986, 2005.
18. Chen, H.K., Hsueh, C.F. ve Chang, M.S., "The real-time time-dependent vehicle routing problem", Transportation Research Part E, 42(5), 383408, 2006.
19. Woensel, T. V., Kerbache, L., Peremans, H., ve Vandaele, N., A queueing framework for routing problems with time-dependent travel times, Journal of Mathematical Modelling and Algorithms, Cilt 6, 151173, 2007.
20. Woensel, T. V., Kerbache, L., Peremans, H., ve Vandaele, N., Vehicle routing with dynamic travel times: A queueing approach, European Journal of Operational Research, Cilt 186, 9901007, 2008.
21. Hashimoto, H., Yagiura, M. ve Ibaraki, T., "An iterated local search algorithm for the timedependent vehicle routing problem with time windows", Discrete Optimization, Cilt 5, No 2, 434456, 2008.
22. Kuo, Y., Wang, C.C. ve Chuang, P.Y., "Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds", Computers & Industrial Engineering, Cilt 57, No 4, 13851392, 2009.
23. Soler, D., Albiach, J. ve Martínez, E., "A way to optimally solve a time-dependent vehicle routing problem with time windows", Operations Research Letters, Cilt 37, No 1, 3742, 2009.
24. Donati, A.V., Montemanni, R., Casagrande, N., Rizzoli, A.E. ve Gambardella, L.M., "Time dependent vehicle routing problem with a multi ant colony system", European Journal of Operational Research, Cilt 185, No 3, 1174 1191, 2008.
25. Jabali, O., Van Woensel, T., de Kok, A.G., Lecluyse, C. ve Peremans, H., "Time-dependent vehicle routing subject to time delay perturbations", IIE Transactions, Cilt 41, No 12, 10491066, 2009.
26. Kuo, Y., "Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem", Computers & Industrial Engineering, Cilt 59, No 1, 157165, 2010.
27. Figliozzi, M.A., The impacts of congestion on time-definitive urban freight distribution networks CO2 emission levels: results from a case study in Portland, Oregon, Transportation Research Part C, Cilt 19, 766778, 2011
28. Liu, Y., Chang, Q. ve Xiong, H., An improved ant colony algorithm for the vehicle routing problem in time-dependent networks, IEICE Transactions on communications, Cilt 5, 1506 1510, 2011.
29. Solomon benchmark instances. http://web.cba.neu.edu/~msolomon/problems.htm. 2014.

APA	Koc C, KARAOĞLAN İ (2014). ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. , 549 - 558.
Chicago	Koc Cagri,KARAOĞLAN İSMAİL ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. (2014): 549 - 558.
MLA	Koc Cagri,KARAOĞLAN İSMAİL ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. , 2014, ss.549 - 558.
AMA	Koc C,KARAOĞLAN İ ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. . 2014; 549 - 558.
Vancouver	Koc C,KARAOĞLAN İ ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. . 2014; 549 - 558.
IEEE	Koc C,KARAOĞLAN İ "ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL." , ss.549 - 558, 2014.
ISNAD	Koc, Cagri - KARAOĞLAN, İSMAİL. "ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL". (2014), 549-558.

APA	Koc C, KARAOĞLAN İ (2014). ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 29(3), 549 - 558.
Chicago	Koc Cagri,KARAOĞLAN İSMAİL ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 29, no.3 (2014): 549 - 558.
MLA	Koc Cagri,KARAOĞLAN İSMAİL ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.29, no.3, 2014, ss.549 - 558.
AMA	Koc C,KARAOĞLAN İ ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2014; 29(3): 549 - 558.
Vancouver	Koc C,KARAOĞLAN İ ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2014; 29(3): 549 - 558.
IEEE	Koc C,KARAOĞLAN İ "ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 29, ss.549 - 558, 2014.
ISNAD	Koc, Cagri - KARAOĞLAN, İSMAİL. "ZAMAN BAĞIMLI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR MATEMATİKSEL MODEL". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 29/3 (2014), 549-558.