Şehir İçi Deniz Yolu Toplu Taşımacılığında Vapur Atama ve Rotalama Optimizasyonu: İstanbul Şehir Hatları Uygulaması

Bu çalışmada, şehir içi deniz yolu toplu taşımacılığında seferlere vapur atama ve rotalama problemi ele alınmıştır. Problem, gerçek hayatta İstanbul Şehir Hatları A.Ş.’nin periyodik olarak karşılaştığı, tarifelerde saatleri belirlenen seferlere vapur atama probleminden yola çıkılarak tanımlanmıştır. Sefer tarifeleri, yaz ve kış dönemine ve haftanın günlerine göre farklılık göstermektedir. Atamada; seferlerin yolcu talepleri, hat-vapur kısıtları, vapurların yolcu kapasiteleri, iskelelerin vapur kapasiteleri, vapurların iskelelere bağlanabilme kısıtları dikkate alınmalıdır. Ayrıca, personellerin günlük çalışma saatini belirleyen kanuni düzenlemeler vapurların çalışma saatlerini kısıtlamaktadır. Amaç, yakıt tüketimi ve dış kaynak kullanımı maliyetlerinden oluşan toplam maliyetleri en küçüklenmektir. Öncelikle, problem için bir matematiksel model geliştirilmiştir. Gerçek boyutlu problem örnekleri için matematiksel modelin yetersiz kalması nedeniyle tabu arama yöntemine dayalı bir sezgisel yöntem geliştirilmiştir. Geliştirilen yöntemin etkinliği gerçekçi veri kümeleri üzerinde gösterilmiştir.

Anahtar Kelimeler:

Vapur-sefer atama ve rotalama, Düğüm ve zaman kısıtlı kapasiteli ayrıt rotalama, Deniz yolu toplu taşımacılığı, Tabu Arama

Ferry Assignment and Routing Optimization for Public Ferry Transportation: A Case Study for Istanbul Şehir Hatları

In this research, we study the trip-ferry assigment and ferry routing problem that arises in public ferry transportation services. The problem is motivated by the real problem that Istanbul Şehir Hatları Inc. needs to solve periodically while assigning ferries to ferry lines having predetermined tarrifs. Tariffs differ according to the season and day of the week. The trip-ferry assignment should consider passenger demand of ferry lines, line-ferry restrictions, ferry passenger capacities, ferry capacities of piers and ferry-pier restrictions. Additionally, working regulations of ferry personnel restrict ferry working hours. The objective is to minimize total cost of fuel consumption and outsourcing. First, a mathematical model was developed. As the mathematical model is inadequate for solving realistic size problem instances, a tabu search-based heuristic method is proposed. The effectiveness of the heuristic is analayzed on realistic data instances.

Keywords:

Ferry-trip assigment and ferry routing, Node and time constrained capacitated arc routing, Maritime pupblic transport, Tabu search,

PDF

___

[1] Tiwari, G. 2006. Urban Passenger Transport: Framework for an Optimal Modal Mix, INRM Policy Brief Series, No: 1, Asian Development Bank, New Delhi.
[2] http://www.udhb.gov.tr/images/kurumsal/3kbit.pdf ( Erişim Tarihi: 19/06/2018)
[3] Kepir, B., Koçyiğit, Ç., Koyuncu, I., Özer, M.B., Yetis Kara, B., Gürbüz, M.A. 2016. Flight-Scheduling Optimization and Automation for AnadoluJet, Interfaces, Cilt. 46(4), s. 315-325. DOI: 10.1287/inte.2016.0853
[4] Sniezek, J. 2001. The capacitated arc routing problem with vehicle/site dependencies: An application of arc routing and partitioning, University of Maryland, PhD thesis.
[5] Yan, S., Chen, C.H., Chen, H.Y., Lou, T.C. 2007. Optimal scheduling models for ferry compaies under alliances, Journal of Marine Science and Technology, Cilt. 15, s. 53-66.
[6] Huisman, D., Kroon, L.G., Lentink, R.M., Vromans, M.J.C.M. 2005. Operations Research in passenger railway transportation, Statistica Neerlandica, Cilt. 59(4), s. 467-497. DOI: 10.1111/j.1467-9574.2005.00303.x
[7] Eiselt, H.A., Gendreau, M., Laporte, G. 1995b. Arc Routing Problems, Part 1: The Chinese Postman Problem, Operations Research, Cilt. 43(2), s. 231-242. DOI: 10.1287/opre.43.2.231
[8] Eiselt, H. A., Gendreau, M., Laporte, G. 1995b. Arc Routing Problems, Part 2: The Rural Postman Problem, Operations Research, Cilt. 43(3), s. 399-414. DOI: 10.1287/opre.43.3.399
[9] Eglese, R.W., Murdock, H. 1991. Routing Road Sweepers in a Rural Area, The Journal of the Operational Research Society, Cilt. 42, s. 281-288. DOI: 10.2307/2583381
[10] Eglese, R.W., Li, L.Y.O. 1992. Efficient Routing for Winter Gritting, The Journal of the Operational Research Society, Cilt. 43, s. 1031-1034. DOI: 10.1057/palgrave.jors.0431102
[11] Bouliane, J., Laporte, G. 1992. Locating Postal Relay Boxes Using a Set Covering Algorithm, Am. J. Math. And Mgmt. Sci., Cilt. 12, s. 65-74. DOI: 10.1016/j.cor.2010.04.010
[12] Wunderlich, J., Collette, M., Levy, L., Bodin, L.D. 1992. Scheduling Meter Readers for Southern California Gas Company, Interfaces Cilt. 22(3), s. 22-30. DOI: 10.1287/inte.22.3.22
[13] Usberti, F.L., Franc, P. M., Frank, A.L.M. 2011. The Open Capacitated Arc Routing Problem, Computers & Operations Research, Cilt. 38(11), s. 1543-1555. DOI: 10.1016/j.cor.2011.01.012
[14] Ulusoy, G. 1985. The fleet size and mix problem for capacitated arc routing, European Journal of Operational Research, Cilt. 22, s. 329-337. DOI: 10.1016/0377-2217(85)90252-8
[15] Cattrysse, D., Muyldermans, L., Van Oudheusden, D. 2003. District design for arc routing applications, Journal of the Operational Research Society, Cilt. 54, s. 1209-1221. DOI: 10.1057/palgrave.jors.2601626
[16] Karapetyan, D., Abraham P.P. 2013. A reduced integer programming model for the ferry scheduling problem, Public Transport, Cilt. 4(3), s. 151-163. DOI: 10.1007/s12469-012-0058-0
[17] Orhan, I., Kapanoğlu, M., Karakoç H. 2010. Hava yolu Operasyonlarında Planlama ve Çizelgeleme, Pamukkale Uni. Muhendislik Bilimleri Dergisi, Cilt. 16(2), s. 181-191.
[18] Taillard, E.D., Badeau, P., Gendreau, M., Guertin, F., Potvin, J.Y. 1997. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, Cilt. 31, s. 170-186. DOI: 10.1287/trsc.31.2.170
[19] Gendreau, M., Laporte, G., Potvin, J.Y. 2002. Meta-heuristics for the capacitated VRP. ss 129-154. Toth, P. ve Vigo, D., ed. 2002. The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications. SIAM Publishing, Philadelphia.
[20] Glover, F., Laguna, M. 1998. Tabu Search. In: Du DZ., Pardalos P.M., ed. 1998. Handbook of Combinatorial Optimization. Springer, Boston, MA
[21] Bach, L., Gendreau, M., Wohlk, S. 2015. Freight railway operator timetabling and engine scheduling, European Journal of Operational Research, Cilt. 241(2), s. 309-319. DOI: 10.1016/j.ejor.2014.08.036
[22] Canca, D., Barrena, E. 2018. The integrated rolling stock circulation and depot location problem in railway rapid transit systems, Transportation Research Part E: Logistics and Transportation Review, Cilt. 109, s. 115-138. DOI: 10.1016/j.tre.2017.10.018