Aylak zamanı en küçükleme amaçlı araç rotalama probleminin genetik algoritma ile çözümü
Loading...
Files
Date
2018-05-17
Authors
Çam, Ömer Nuri
Journal Title
Journal ISSN
Volume Title
Publisher
Uludağ Üniversitesi
Abstract
Neredeyse 60 yıl boyunca tartışılan problemlerden biri olan Araç Rotalama Problemi (ARP); farklı durumlara ilişkin yeni kısıtlar eklenerek çeşitlenmiş, 10'dan fazla temel problem türü modellenmiştir. Bu problemler incelendiğinde tümünün amaç fonksiyonlarının doğrudan veya dolaylı olarak maliyeti azaltmaya yönelik olduğu görülmektedir. Bu çalışmada yeni bir ARP problemi tanıtılmaktadır. Problem Türkiye'de şehirler arası yolcu taşıyan bir firmanın operasyonlarının daha iyi yönetilmesi amacıyla yapılan araştırmada ortaya çıkmıştır. Diğer ARP'lerden farkı amaç fonksiyonundan kaynaklanmaktadır. Problemde; çalıştıkça para kazanabilen araçların, bekleme sürelerinin (aylak zaman) en aza indirilmesi amaçlanmaktadır. Önceki problemlerle karşılaştırıldığında, araçların az çalışması değil çok çalışması- bazen en kısa yol yerine daha uzun yolu tercih etmeleri önerilebilir. Diğer iki farkı da kısıtlarla ilgilidir; Bazı coğrafi noktalar birden fazla ziyaret edilmelidir ve alt tur oluşturulmasına izin verilebilir. Problemin ayrıntılı sunumunda kullanılmak üzere firmanın operasyonlarının kümelendiği beş alt gruptan birinde yer alan 34 sefer örnek olarak seçilmiştir. Çözüm için genetik algoritma kullanılmıştır. Bulunan en küçük aylak zaman için verimlilik oranı %66,78 iken, en uzun aylak süre için %40,42 bulunmuştur. Bu durum eniyi çözümlerin bulunmasını garanti eden kesin (exact) yöntemlerin kullanımının önemine işaret etmektedir. Problem bir çok taşıma (deniz yolu, hava yolu, kara yolu ) şirketi için geçerlidir. Bazı imalat firmalarında otomatik kontrollü araçların fabrika içinde yaptıkları turlar, iş sırlama problemleri de bu yaklaşımla ele alınıp iyileştirilebilir. Gelecekte sürücüler için yasal kısıtlamaların olmadığı otomatik kontrollü insansız araçların daha iyi işletilmesine de uygulanabilecektir. Aylak sürenin düşürülmesi neticesinde beklentilerden biri, fazla sayıda olan araçların azaltılmasını mümkün kılmasıdır. Problem için geliştirilecek çözümler, araç sayısı, filo yönetimi, servis-bakım maliyetlerinin, bilet fiyatlarının, karbon salınımının, israfın azalması, dünyada refahın artması gibi doğrudan, dolaylı etkilere yol açabilecektir.
Vehicle routing problem (VRP) is one of the problems discussed for almost 60 years among researchers, branched to more than 10 general subcategories, depending on problems' constraints or/and their aim functions. When these problems are examined, their aims are focused on reducing costs. (or cost related pollution etc.) In this study, a new VRP approach is introduced. This approach is realized when to manage better the route operations of a company carrying long-distance passengers in Turkey. The difference of the problem based on its aim function. It suggests vehicles should work more because they make profit if they work. So this aim function suggests minimizing idle time of those vehicles. Opposite of VRP function which are examined till today, vehicles should work more and sometimes they should prefer long distance route. One of the result is that it is possible to reduce the number of vehicles used. For a problem, 34 route surveyed from bus company. To solve and introduce that problem a software developed using genetic algorithm. As a result, one appoach efficiency is %66.78 and other is %40.42. Outputs showed importance of using exact algorithms. The problem can be applied to many transport companies (ship, plane, road). Also in some manufacturing companies, tours and work scheduling problems can be handled and improved with this approach for automatic controlled vehicles in factory. It can also be adapted to better maneuvering autonomous unmanned vehicles without legal restrictions for future drivers. The solutions to be developed for the problem may lead directly or indirectly to the number of vehicles, fleet management, service-maintenance costs, ticket prices, carbon emissions, reduction of wastage, and welfare in the world.
Vehicle routing problem (VRP) is one of the problems discussed for almost 60 years among researchers, branched to more than 10 general subcategories, depending on problems' constraints or/and their aim functions. When these problems are examined, their aims are focused on reducing costs. (or cost related pollution etc.) In this study, a new VRP approach is introduced. This approach is realized when to manage better the route operations of a company carrying long-distance passengers in Turkey. The difference of the problem based on its aim function. It suggests vehicles should work more because they make profit if they work. So this aim function suggests minimizing idle time of those vehicles. Opposite of VRP function which are examined till today, vehicles should work more and sometimes they should prefer long distance route. One of the result is that it is possible to reduce the number of vehicles used. For a problem, 34 route surveyed from bus company. To solve and introduce that problem a software developed using genetic algorithm. As a result, one appoach efficiency is %66.78 and other is %40.42. Outputs showed importance of using exact algorithms. The problem can be applied to many transport companies (ship, plane, road). Also in some manufacturing companies, tours and work scheduling problems can be handled and improved with this approach for automatic controlled vehicles in factory. It can also be adapted to better maneuvering autonomous unmanned vehicles without legal restrictions for future drivers. The solutions to be developed for the problem may lead directly or indirectly to the number of vehicles, fleet management, service-maintenance costs, ticket prices, carbon emissions, reduction of wastage, and welfare in the world.
Description
Keywords
Araç rotalama problemi (ARP), Aylak sürenin en küçüklenmesi, En kısa yol, EKAZARP, Zaman boyutlu coğrafi nokta, Vehicle routing problem, Minimizing idle time, Shortest path, VRPMIT
Citation
Çam, Ö. N. (2018). Aylak zamanı en küçükleme amaçlı araç rotalama probleminin genetik algoritma ile çözümü. Yayınlanmamış doktora tezi. Uludağ Üniversitesi Sosyal Bilimler Enstitüsü.