Local search heuristics for pollution-routing problem with multiple vehicle types and deadlines

Abstract

Araç Rotalama Problemi (ARP), lojistik literatürünün üzerinde en geniş ölçüde çalışılan problemlerinden biridir. Hesaplamasal karmaşıklığı yüksek olan bu optimizasyon probleminin çeşitli varyantlarına çözüm üretmek üzere şu ana kadar çok sayıda farklı kesin çözüm yöntemi ve sezgisel yöntem geliştirilmiştir. Fakat çok az sayıda araştırmacı çalışmalarında hız kontrolü, yakıt tüketimi ve sera gazı (SG) salınımı kavramlarına yer vermiştir. Bu çalışmanın ilk kısmı ARP?nin yakıt tüketimi, SG salınımı ve sürücü ücretlerini dikkate alan kapsamlı bir maliyet fonksiyonuna sahip, Kirlilik-Rotalama Problemi (KRP) olarak adlandırılan özel bir varyantına ayrılmıştır. KRP?nin çoklu araç tipi ve terminleri içeren bir uzantısı göz önünde bulundurulmuştur. Bu kısımda ilk olarak bir Karışık Tamsayılı Programlama modeli ve bir İkinci Derece Konik Programlama modelinden oluşan iki kesin çözüm yöntemi, bunu takiben de özel bir başlangıç çözümü algoritması ve en iyi seyahat sürelerini belirleme prosedürünü içeren yerel arama sezgiselleri sunulmuştur. Deney sonuçları ayrıntılı bir sayısal çalışma ile yorumlanmıştır.İkinci kısımda (Bkz. Ek E) ise bir uygulamalı proje raporu sunulmuştur. Proje, çoklu depo ve otomatize planlama yaklaşımlarıyla elde edilebilecek olası iyileştirmelerin araştırılması amacıyla Hollanda?da bir üçüncü parti lojistik (3PL) şirketinde gerçekleştirilmiştir.

Vehicle Routing Problem (VRP) is one of the most widely studied problems in logistics literature. Up to now, many different types of exact solution methods and heuristics have been developed in order to deal with various variants of this computationally complex optimization problem. However, only a few researchers have included the concepts of speed control, fuel consumption and greenhouse gas (GHG) emissions in their studies. The first part of this study is dedicated to a special variant of VRP called the Pollution-Routing Problem (PRP), which includes a comprehensive cost function that takes into account fuel consumption, GHG emissions and driver wages. An extension of PRP incorporating multiple vehicle types and deadlines is considered. Throughout this part, firstly two alternative exact solution methods are proposed: a Mixed Integer Programming model with a piecewise linear cost function and a Mixed Integer Second Order Cone Programming model, followed by local search heuristics with a special initialization algorithm and optimal travel time determination procedure. Results of experiments are interpreted in an extensive computational study.In the second part (See Appendix E), the report of an applied project is represented. The project took place in a third-party logistics (3PL) company in the Netherlands with the aim of investigating the possible improvements that can be achieved via employing a multi-depot and automated planning approach.