Modeling Vehicle Routing Problem With Time Windows With Genetic Algorithm

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2009Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2009Küreselleşmenin rekabeti hızla arttırdığı son yıllarda müşteri memnuniyeti bu rekabetin en belirleyici faktörlerinden biri olmuştur. Tedarik zincirinde, ürünün ya da hizmetin müşteriye ulaştığı son aşama olan lojistik ve dağıtım şirketlerin üzerinde daha dikkatli durduğu bir alan haline gelmiştir. Ne kadar hızlı ve çok sayıda müşteriye ulaşılırsa, o kadar müşteri memnuniyeti artacaktır. Fakat bunun yanısıra şirketler, kendi maliyetlerini de azaltmaya çalışmaktadır. Sözkonusu rekabetin içerisindeki büyük lojistik ve dağıtım şirketlerinin en iyilemeye çalıştıkları problemler de büyük ve karmaşık olacaktır. Aynı anda hem müşterilerine hızlı ve kaliteli hizmet sağlamak hem de maliyetleri en aza indirmek bu şirketlerin hedefidir. Bu çalışmada, bu şirketlerin problemlerinden biri olan araç rotalama probleminin özel bir hali ele alınmıştır. Müşterilere belirli bir zaman aralığında hizmet verilebilen zaman pencereli araç rotalama probleminin çözümünde hızlı ve maliyetleri en aza indirgeyen bir rotalama ortaya konulmaya çalışılır. Belirli bir dönem için bu rotaların çıkarılması gerektiği ve problem boyutunun büyük olması nedeniyle kesin en iyileme yöntemleri yavaş çözüm vereceklerinden, sözkonusu yöntemleri kullanmak verimli olmayacaktır. Dolayısıyla en iyi çözümü garanti etmeyen fakat en iyi çözüme makul yakınlıkta çözüm elde edilebilen sezgisel yöntemler devreye girmektedir. Bu çalışmada meta-sezgisel bir yöntem olan genetik algoritma ile sözkonusu problem modellenerek, genel bir uygulama verisi üzerinde test edilmiştir. Genetik algoritmada yeni bir birey kodlama yaklaşımı olan ve bu çalışmada araç rotalama problemi için kullanılan rassal sayılı kodlama, permütasyon kodlama gibi onarıcı işlemlere gerek duymadığından modelin daha etkin ve hızlı olmasını sağlayacaktır. Bu problemi ele alan diğer modellerle karşılaştırılabilir bir model ortaya koymak, bu çalışmanın amacıdır.In recent years, globalization increases competition between companies rapidly, customer satisfaction has become one of the most significant factors of the competition. In supply chain, logistics and distribution, which is the last process that product or service reaches to customers, has become an area that companies pay more attention. Faster delivery and more customer reachability cause more customer satisfaction. But, companies should also consider and decrease their operational costs. The aim of these companies is to provide quality and speed service and minimizing the costs as well. In this study, one of the special forms of vehicle routing problem is taken into consideration. At the solution of the vehicle routing problem with time windows, which the customers can be served between a specific time windows only, a routing that minimizes the time and the costs is tried to be reached. Because of being necessary of getting the routes between a specific period and the size of problem is large, classical optimization methods are not enough because of being slow. Therefore, the heuristic methods that do not guarantee the optimal solution but can obtain a good solution are used. In this study, the problem was modeled with genetic algorithm, which is one of the meta-heuristic methods and tested over a benchmark data. Random key representation is a new approach for individual coding in genetic algorithm and does not need repairment operations as permutational coding. The aim of the study is to get a comparative model with other studies.Yüksek LisansM.Sc