Heterojen Araç Filolu, Parçalı Teslimatlı, Açık veya Kapalı Uçlu Rotalar İçerebilen Zengin Araç Rotalama Problemi

Abstract

We study a rich vehicle routing problem motivated by a real-life problem, in which by the customer deliveries is done by a heterogeneous fleet with possible split deliveries. The routes can be performed by owned vehicles or outsourced vehicles, the routes of which can be closed or open, respectively. The routes of each hired vehicle ends at the last visited customer while the owned vehicles must return to the depot. Both the owned and the hired vehicles are of types that differ from each other in terms of capacity and cost per unit distance, exhibiting economies of scale. A fixed number of owned vehicles are available for use, while an unlimited number of hired vehicles can be used, albeit at a higher cost per unit distance than an owned vehicle of the same type. Our aim is to construct a set of routes with minimum total cost. We firstly develop a mixed integer linear programming model, and demonstrate the value of allowing flexible splits in deliveries with the help of this model on small instances. Because of the complexity of the problem, the model fails to find optimal solutions for larger instances in a reasonable time. In order to obtain high quality solutions efficiently, we propose an Adaptive Large Neighborhood Search (ALNS) algorithm with novel operators.

Araç Rotalama Problemi, yöneylem araştırmacılarının çalıştıkları temel konulardan biri olmakla birlikte günümüze kadar problemin birçok varyasyonu araştırılmıştır. Çoğu problemin çözümü gerçek hayatta yetersiz kalmaktadır. Problem çözümünün uygulanabilirliğinin arttırılması ve daha doğru sonuçların elde edilmesi amacıyla gerçek hayatta karşılaşılabilecek durumlar da dikkate alınmalıdır. Bu durumların bir veya daha fazlasının ele alındığı problemler "Zengin Araç Rotalama Problemi" olarak adlandırılmaktadır. Bu çalışmada müşteri talebinin parçalı teslimat ile karşılanabildiği, araç filosunun kapasite ve maliyet açısından farklı tipteki sınırlı sayıda araçlardan oluştuğu ve gereken durumlarda dışarıdan araç kiralanarak açık uçlu rotalar oluşturulabilen senaryo ele alınmıştır. Bu doğrultuda karma tam sayılı bir matematiksel model geliştirilmiştir. Problemin karmaşıklık seviyesinden ötürü geliştirilen model, boyutu yüksek olan problem örneklerinin çözümünde yetersiz kalmıştır. Makul süreler içerisinde, büyük boyutlu problem örnekleri için kaliteli çözümlerin elde edilmesi amacıyla özgün operasyonlar içeren Uyarlamalı Büyük Komşuluk Araması algoritması geliştirilmiştir.