Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model

KARAOGLAN, Ismail; Can Atasagun, Gözde

doi:10.17341/gazimmfd.571515

Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model

Gözde CAN ATASAGUN, (Konya Teknik Üniversitesi, Endüstri Mühendisliği Bölümü, Konya, Türkiye)

İsmail KARAOĞLAN (Konya Teknik Üniversitesi, Endüstri Mühendisliği Bölümü, Konya, Türkiye)

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

8 1

Yıl: 2019 Cilt: 34 Sayı: 4 Sayfa Aralığı: 1743 - 1755 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.571515 İndeks Tarihi: 05-01-2021

Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model

Öz:

Bu çalışmada zaman bağımlı araç rotalama problemi (ZB_ARP) ve topla-dağıt araç rotalama problemi(TD_ARP) birlikte ele alınmıştır. Zaman Bağımlı Eşzamanlı Topla-Dağıt Araç Rotalama Problemi(ZB_ETD_ARP) olarak adlandırılan ve literatürde henüz ele alınmamış olan bu problem ilk kez tanımlanmışve çözümü için bir matematiksel model önerilmiştir. Önerilen model, ilk giren ilk çıkar (FIFO) özelliğinisağlayan ve zamana bağlı hız fonksiyonunu kullanan doğrusal bir yapıya sahiptir. Geliştirilen matematikselmodel literatürde mevcut problemler üzerinde test edilmiş ve yorumlanmıştır. 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.

Anahtar Kelime:

A mathematical model for the time dependent vehicle routing problem with simultaneous pick-up and delivery

Öz:

In this study, the Time Dependent Vehicle Routing Problem (TDVRP) and the Vehicle Routing Problem with Pick-up and Delivery (VRPPD) are considered simultaneously. This problem, which is called as the Time-Dependent Vehicle Routing Problem with Simultaneous Pick-up and Delivery (TD_VRP_SPD) and has not been considered in the literature, is described for the first time and a mathematical model is proposed for the solution of the problem. The proposed model has a linear structure that provides the “first-in-firstout” (FIFO) feature and uses the time-dependent speed function. Experimental studies of the proposed mathematical model are performed on well-known test problems of the literature and the results are interpreted. Performance of the model evaluated computation time and percentage deviations to optimal.

Anahtar Kelime:

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

1. Koç, Ç. and I. Karaoğlan, A mathematical model for the time-dependent vehicle routing problem. Journal of the Faculty of Engineering and Architecture of Gazi University, 29 (3), 549-55,. 2014.
2. Malandraki, C., Time dependent vehicle routing problem: Formulations, solution algorithms and computations experiments. Northwestern University. USA., 1989.
3. Malandraki, C. and M.S. Daskin, Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science, 26 (3), 185-200, 1992.
4. Hill, A.V. and W.C. Benton, Modelling Intra-City TimeDependent Travel Speeds for Vehicle Scheduling Problems. The Journal of the Operational Research Society, 43 (4), 343-351, 1992.
5. Malandraki, C. and R.B. Dial, A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem. European Journal of Operational Research, 90 (1), 45-55, 1996.
6. Park, Y.-B., A solution of the bicriteria vehicle scheduling problems with time and area-dependent travel speeds. Computers & Industrial Engineering, 38 (1), 173-187. 2000.
7. Jung, S. and A. Haghani, Genetic algorithm for the timedependent vehicle routing problem. Transportation Network Modeling, 2001 (1771), 164-171, 2001
8. Ichoua, S., M. Gendreau, and J.-Y. Potvin, Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144 (2), 379-396, 2003.
9. Fleischmann, B., M. Gietz, and S. Gnutzmann, Timevarying travel times in vehicle routing. Transportation Science, 38 (2), 160-173, 2004.
10. Haghani, A. and S. Jung, A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32 (11), 2959-2986, 2005.
11. Chen, H.K., C.F. Hsueh, and M.S. Chang, The real-time time-dependent vehicle routing problem. Transportation Research Part E-Logistics and Transportation Review, 42(5), 383-408, 2006.
12. Woensel, T., et al., A Queueing Framework for Routing Problems with Time-dependent Travel Times. Journal of Mathematical Modelling and Algorithms, 6 (1), 151- 173, 2007.
13. Van Woensel, T., et al., Vehicle routing with dynamic travel times: A queueing approach. European Journal of Operational Research, 186 (3), 990-1007, 2008.
14. Xin, Z., G. Goncalves, and R. Dupas. A genetic approach to solving the vehicle routing problem with time-dependent travel times. in 2008 Mediterranean Conference on Control and Automation - Conference Proceedings, MED'08. 2008.
15. Hashimoto, H., M. Yagiura, and T. Ibaraki, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. Discrete Optimization, 5 (2), 434-456, 2008.
16. Kuo, Y.Y., C.C. Wang, and P.Y. Chuang, Optimizing goods assignment and the vehicle routing problem with time-dependent travel speeds. Computers & Industrial Engineering, 57 (4), 1385-1392, 2009.
17. Soler, D., J. Albiach, and E. Martínez, A way to optimally solve a time-dependent Vehicle Routing Problem with Time Windows. Operations Research Letters, 37 (1), 37-42 2009.
18. Jabali, O., et al., Time-dependent vehicle routing subject to time delay perturbations. Iie Transactions, 41 (12), 1049-1066. 2009.
19. Kuo, Y., Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem. Computers and Industrial Engineering, 59 (1), 157-165. 2010.
20. Figliozzi, M.A., The impacts of congestion on timedefinitive urban freight distribution networks CO2 emission levels: Results from a case study in Portland, Oregon. Transportation Research Part C: Emerging Technologies, 19 (5), 766-778, 2011.
21. Figliozzi, M.A., The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics. Transportation Research Part E-Logistics and Transportation Review, 48 (3), 616-636, 2012.
22. Kritzinger, S., et al., Using traffic information for timedependent vehicle routing. Seventh International Conference on City Logistics, 39, 217-229, 2012.
23. Dabia, S., et al., Branch and Price for the TimeDependent Vehicle Routing Problem with Time Windows. Transportation Science, 47 (3), 380-396, 2013.
24. Mousavipour, S. and S.M.H. Hojjati, A particle swarm optimisation for time-dependent vehicle routing problem with an efficient travel time function. International Journal of Operational Research, 20 (1), 109-120, 2014.
25. Zhang, T., W.A. Chaovalitwongse, and Y.J. Zhang, Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery. Journal of Combinatorial Optimization, 28 (1), 288-309, 2014.
26. Johar, F., C. Potts, and J. Bennell, Solving the Time Dependent Vehicle Routing Problem by Metaheuristic Algorithms. 2nd Ism International Statistical Conference 2014 (Ism-Ii): Empowering the Applications of Statistical and Mathematical Sciences, 1643, 751-757, 2015.
27. Gendreau, M., G. Ghiani, and E. Guerriero, Timedependent routing problems: A review. Computers & Operations Research, 64 (Supplement C), 189-197, 2015.
28. Wang, X., Vehicle routing problems that minimize the completion time: Heuristics, worst-case analyses, and computational results., University of Maryland, College Park., 2016.
29. Huang, Y., et al., Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B: Methodological, 95, 169-195, 2017.
30. Rincon Garcia, N., B. Waterson, and T. Cherrett, A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows. International Journal of Industrial Engineering Computations, 8 (1), 141-160. 2017.
31. Spliet, R., S. Dabia, and T. van Woensel, The Time Window Assignment Vehicle Routing Problem with Time-Dependent Travel Times. Transportation Science, 2017.
32. Parragh, S., K. Doerner, and R. Hartl, A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58 (1), 21-51, 2008.
33. Ropke, S. and D. Pisinger, A unified heuristic for a large class of Vehicle Routing Problems with Backhauls. European Journal of Operational Research, 171 (3), 750- 775, 2006.
34. Karaoglan, I., Dağıtım Ağları Tasarımında Yer Seçimi ve Eşzamanlı Topla-Dağıt Araç Rotalama Problemleri, in Endüstri Mühendisliği Bölümü, Gazi Universitesi, Doktora Tezi, 2009
35. Min, H.K., The Multiple Vehicle-Routing Problem with Simultaneous Delivery and Pick-up Points. Transportation Research Part a-Policy and Practice, 23 (5), 377-386, 1989.
36. Halse, K., Modeling and solving complex vehicle routing problems, Institute of Mathematical Statistics and Operations Research (IMSOR), Technical University of Denmark, Ph.D. thesis, 1992.
37. Dethloff, J., Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. Or Spektrum, 23 (1), 79-96, 2001.
38. Nagy, G. and S.d. Salhi, Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research, 162 (1), 126-141, 2005.
39. Crispim, J. and B. J., Reactive tabu search and variable neighbourhood descent applied to the vehicle routing problem with backhauls, in MIC, 4th Metaheuristic International Conference. Porto, Portugal. 2001.
40. Chen, J.F. and T.H. Wu, Vehicle Routing Problem with Simultaneous Deliveries and Pickups. The Journal of the Operational Research Society, 57 (5), 579-587, 2006.
41. Montane, F.A.T. and R.D. Galvao, A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Computers & Operations Research, 33 (3), 595-619, 2006.
42. Bianchessi, N. and G. Righini, Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research, 34 (2), 578-594, 2007.
43. Ai, T.J. and V. Kachitvichyanukul, A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 36 (5),1693-1702, 2009.
44. Zachariadis, E.E., C.D. Tarantilis, and C.T. Kiranoudis, A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service. Expert Systems with Applications, 36 (2), 1070- 1081, 2009.
45. Gajpal, Y. and P. Abad, An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup. Computers & Operations Research, 36 (12), 3215-3223, 2009.
46. Zachariadis, E.E., C.D. Tarantilis, and C.T. Kiranoudis, An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries. European Journal of Operational Research, 202 (2), 401-411, 2010.
47. Subramanian, A., et al., Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Operations Research Letters, 39 (5), 338-341, 2011.
48. Zachariadis, E.E. and C.T. Kiranoudis, A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, 38 (3), 2717-2726, 2011.
49. Fan, J., The Vehicle Routing Problem with Simultaneous Pickup and Delivery Based on Customer Satisfaction. Procedia Engineering, 15, 5284-5289. 2011.
50. Wang, H.-F. and Y.-Y. Chen, A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 62 (1), 84-95, 2012.
51. Tasan, A.S. and M. Gen, A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers and Industrial Engineering, 62 (3), 755-761, 2012.
52. Zachariadis, E.E. and C.T. Kiranoudis, An effective local search approach for the Vehicle Routing Problem with Backhauls. Expert Systems with Applications, 39 (3), 3174-3184, 2012.
53. Goksal, F.P., I. Karaoglan, and F. Altiparmak, A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computers & Industrial Engineering, 65 (1), 39-53. 2013.
54. Liu, R., et al., Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research, 230 (3), 475-486, 2013.
55. Reil, S., A. Bortfeldt, and L. Mönch, Heuristics for vehicle routing problems with backhauls, time windows, and 3D loading constraints. European Journal of Operational Research, 266 (3), 877-894, 2018.
56. Koç, Ç. and G. Laporte, Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91 (Supplement C), 79-91. 2018.
57. Miller, C.E., A.W. Tucker, and R.A. Zemlin, Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7 (4), 326-329, 1960.
58. Kulkarni, R. and P.R. Bhave, Integer programming formulations of vehicle routing problems. European Journal of Operational Research, 20 (1), 58-67, 1985.
59. Solomon, M.M., Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35 (2), 254-265, 1987.
60. Angelelli, E., Mansini, R., Quantitative Approaches to Distribution Logistics and Supply Chain Management, Editörler: Klose, A., Speranza, M. G., Van Wassenhove, L. N., . Springer-Verlag, Berlin, 249-267, 2002.

APA	Can Atasagun G, KARAOGLAN I (2019). Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. , 1743 - 1755. 10.17341/gazimmfd.571515
Chicago	Can Atasagun Gözde,KARAOGLAN Ismail Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. (2019): 1743 - 1755. 10.17341/gazimmfd.571515
MLA	Can Atasagun Gözde,KARAOGLAN Ismail Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. , 2019, ss.1743 - 1755. 10.17341/gazimmfd.571515
AMA	Can Atasagun G,KARAOGLAN I Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. . 2019; 1743 - 1755. 10.17341/gazimmfd.571515
Vancouver	Can Atasagun G,KARAOGLAN I Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. . 2019; 1743 - 1755. 10.17341/gazimmfd.571515
IEEE	Can Atasagun G,KARAOGLAN I "Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model." , ss.1743 - 1755, 2019. 10.17341/gazimmfd.571515
ISNAD	Can Atasagun, Gözde - KARAOGLAN, Ismail. "Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model". (2019), 1743-1755. https://doi.org/10.17341/gazimmfd.571515

APA	Can Atasagun G, KARAOGLAN I (2019). Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 34(4), 1743 - 1755. 10.17341/gazimmfd.571515
Chicago	Can Atasagun Gözde,KARAOGLAN Ismail Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 34, no.4 (2019): 1743 - 1755. 10.17341/gazimmfd.571515
MLA	Can Atasagun Gözde,KARAOGLAN Ismail Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.34, no.4, 2019, ss.1743 - 1755. 10.17341/gazimmfd.571515
AMA	Can Atasagun G,KARAOGLAN I Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2019; 34(4): 1743 - 1755. 10.17341/gazimmfd.571515
Vancouver	Can Atasagun G,KARAOGLAN I Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2019; 34(4): 1743 - 1755. 10.17341/gazimmfd.571515
IEEE	Can Atasagun G,KARAOGLAN I "Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 34, ss.1743 - 1755, 2019. 10.17341/gazimmfd.571515
ISNAD	Can Atasagun, Gözde - KARAOGLAN, Ismail. "Zaman bağımlı eş zamanlı topla dağıt araç rotalama problemi için bir matematiksel model". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 34/4 (2019), 1743-1755. https://doi.org/10.17341/gazimmfd.571515