VRPSPD Model to Re-Route The Sea Buses in İstanbul: The Case of Bosphorus
Özet
This study aims to minimize transportation costs and determine the optimal fleet size by optimizing the routes and schedules of sea buses operated by Istanbul Sea Buses Corp. (ISB) in the Bosphorus. Today, maritime transport accounts for a low share of 2.5% in Istanbul's overall transportation, and the routes for 17 sea buses carrying out 260 daily missions across 19 ports are planned based on experience rather than scientific methods. The paper addresses this structure as a Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries (VRPSPD) with time windows and develops an integer linear programming model. By solving the model—comprising 65,326 variables and 65,847 constraints—using LINGO 15.0, the results reveal that the 260 missions can be fully met using 16 sea buses instead of 17. Through this optimization, the daily total operational cost is reduced to $2,377, yielding a 17.2% cost reduction, increasing the sea bus utilization rate by 5.18 percentage points, and achieving $142,216 in annual operational savings. Furthermore, the saved sea bus enhances fleet efficiency without necessitating the purchase of a new vessel (which carries an average investment cost of $6 million). In conclusion, applying scientific routing methods reduces operational expenses, enabling potential ticket price reductions and improving the overall efficiency of maritime transport in Istanbul.
Referanslar
Avci, M., & Topaloglu, S. (2015). An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries. Computers & Industrial Engineering, 83, 15-29.
Belgin, O., Karaoglan, I., & Altiparmak, F. (2018). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115, 1-16.
Bodin, L., Golden, B., Assad, A and Ball, M., (1983). “Routing and Scheduling of Vehicles and Crews: The State of the Art”. Computers and Operations Research 10, 63-211.
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300-313.
Bronmo, G., Christiansen, M., Fagerholt, K., & Nygreen, B. (2007). A multi-start local search heuristic for ship scheduling—a computational study. Computers & Operations Research, 34(3), 900-917.
Bronmo, G., Nygreen, B., & Lysgaard, J. (2010). Column generation approaches to ship scheduling with flexible cargo sizes. European Journal of Operational Research, 200 (1), 139-150.
Christiansen, M., Fagerholt, K., Nygreen, B., & Ronen, D. (2013). Ship routing and scheduling in the new millennium. European Journal of Operational Research, 228(3), 467-483.
Cho, S. C., & Perakis, A. N. (1996). Optimal liner fleet routeing strategies. Maritime policy and management, 23(3), 249-259.
Dantzig G.B., Ramser J.H., (1959), “The truck Dispatching Problem”, Management Science, 6, 80-91.
Darzentas, J., & Spyrou, T. (1996). Ferry traffic in the Aegean Islands: a simulation study. Journal of the Operational Research Society, 47(2), 203-216.
Dethloff, J., (2001), “ Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem With Simultaneous Delivery and Pick-Up”, OR Spectrum, 23, 79-96.
Drexl, M. (2013). Applications of the vehicle routing problem with trailers and transshipments. European Journal of Operational Research, 227(2), 275-283.
Fagerholt, K. (2001). Ship scheduling with soft time windows: An optimization-based approach. European Journal of Operational Research, 131(3), 559-571.
Fagerholt, K., & Ronen, D. (2013). Bulk ship routing and scheduling: solving practical problems may provide better results. Maritime Policy & Management, 40(1), 48-64.
Fan, X. C., Li, N. L., Zhang, B. Y., & Liu, Z. H. (2011). Research on vehicle routing problem with soft time windows based on tabu search algorithm. 18th International Conference on Industrial Engineering and Engineering Management, Singapore, (pp. 420-423).
Fazi, S., Fransoo, J. C., Van Woensel, T., & Dong, J. X. (2020). A variant of the split vehicle routing problem with simultaneous deliveries and pickups for inland container shipping in dry-port based systems. Logistics and Transportation Review, 142, 102057.
Gajpal, Y., Abad, P., (2009), “An Ant Colony System (ACS) For Vehicle Routing Problem With Simultaneous Delivery and Pick-up”, Computer & Operations Research, 36, 215-223.
Gansterer, M., & Hartl, R. F. (2018). Collaborative vehicle routing: a survey. European Journal of Operational Research, 268(1), 1-12.
ISB (Istanbul Sea Buses) A.Ş. (2020). Official Web Page. (Access date and address: www.ido.com.tr, 15/09/2020)
Jozefowiez, N., Semet F., Talbi E., (2008), “Multi-objective Vehicle Routing Problems” European Journal of Operational Research, 189, 293-309.
Jun, Y., & Kim, B. I. (2012). New best solutions to VRPSPD benchmark problems by a perturbation based algorithm. Expert Systems with Applications, 39(5), 5641-5648.
Kassem, S., & Chen, M. (2013). Solving reverse logistics vehicle routing problems with time windows. The International Journal of Advanced Manufacturing Technology, 68(1-4), 57-68.
Koç, Ç., & Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79-91.
Koç, Ç., Laporte, G., & Tükenmez, İ. (2020). A Review on Vehicle Routing with Simultaneous Pickup and Delivery. Computers & Operations Research, 104987.
Min, H., (1989), “The multiple Vehicle Routing Probem with Simultaneous Delivery and Pick-up Points” Transportation Research, 23A, 377-386.
Mingyong, L., & Erbao, C. (2010). An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 23(2), 188-195.
Mu, D., Wang, C., Zhao, F., & Sutherland, J. W. (2016). Solving vehicle routing problem with simultaneous pickup and delivery using parallel simulated annealing algorithm. International Journal of Shipping and Transport Logistics, 8(1), 81-106.
Quirion-Blais, O., & Chen, L. (2020). A case-based reasoning approach to solve the vehicle routing problem with time windows and drivers’ experience. Omega, (In press) 102340.
Rodrigues, V. P., Morabito, R., Yamashita, D., Da Silva, B. J., & Ribas, P. C. (2016). Ship routing with pickup and delivery for a maritime oil transportation system: MIP model and heuristics. Systems, 4(3), 31.
Ronen, D., (1993), “Ship Scheduling: The Last Decade”, European Journal of Operational Research, 71, 325–333.
Santos, P. T. G., Kretschmann, E., Borenstein, D., & Guedes, P. C. (2020). Cargo routing and scheduling problem in deep-sea transportation: Case study from a fertilizer company. Computers & Operations Research, (In press) 104934.
Solomon, M.M., (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints” Operations Research, 35(2), 254-265.
Subramanian, A., Drummond, L. M. D. A., Bentes, C., Ochi, L. S., & Farias, R. (2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, 37(11), 1899-1911.
Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519-2531.
Trottier, L. P., & Cordeau, J. F. (2019). Solving the vessel routing and scheduling problem at a Canadian maritime transportation company. Information Systems and Operational Research, 57(2), 260-285.
Vidal, T., Laporte, G., & Matl, P. (2019). A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research. 286(2), 401-416.
Wang, H. F., & Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 62(1), 84-95.
Wang, X., Choi, T. M., Liu, H., & Yue, X. (2016). Novel ant colony optimization methods for simplifying solution construction in vehicle routing problems. IEEE Transactions on Intelligent Transportation Systems, 17(11), 3132-3141.
Yin, C., Bu, L., & Gong, H. (2013). Mathematical model and algorithm of split load vehicle routing problem with simultaneous delivery and pickup. International journal of innovative computing, information and control, 9(11), 4497-4508.
Zachariadis, E. E., & Kiranoudis, C. T. (2011). A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries. Expert Systems with Applications, 38(3), 2717-2726.
Zhang, Z., Cheang, B., Li, C., & Lim, A. (2019). Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer. Computers & Operations Research, 103, 81-96.
