A Genetic algorithm based meta-heuristic for capacitated vehicle routing problem with simultaneous pick-up and delivery

Abstract

ÖZET Bu çalışmada gerçek hayatta örnekleri görülebilen özel bir karar problemi için kuramsal bir yapı oluşturma üzerine odaklanılmışlar. Problemin kendisi aynı büyüklükte olan dağıtılacak ve iade malların kapasiteleri belirlenmiş özdeş araçlardan oluşan bir filo ile dağıtılması ve aynı anda depoya götürülmek üzere toplanması olarak tanımlanabilir. Literatürde benzer problemler `geri seferli toplama ve iade problemleri` ve `kırsal kesim postacı problemleri` başlıkları altında incelenmektedir. Oluşan NP- hard problemin çözümü için genetik algoritma (GA) kullanılmıştır. İşlemsel verimlilik ve iyi çözüm performansı aranmıştır. Araç rotalama problemleri üzerine olan geniş literatür taranmış, en çok kullanılan çözüm yöntemleri kendi aralarında sınıflandırılmış ve kısaca tanıtılmıştır. Dethloff (2001) tarafından önerilen doğrusal tamsayı programlama modeli baz alınarak genetic algoritma esaslı bir model geliştirilmiş ve bunun üzerinde denemeler gerçekleştirilerek yüksek kalitede sonuç üretebilen sağlam bir yaklaşım geliştirilmesine çalışılmıştır. Üzerinde çalıştığımız modeller benzer özellikler sergileyen makine çizelgeleme literatüründen alınarak problemimize uyarlanmıştır. Araştırmamız, üzerinde çalıştığımız problem için henüz GA'lan kullanarak çözüme ulaşmış herhangi bir çalışma olmadığım göstermiştir. Dolayısıyla yaptığımız çalışma mevcut haliyle alanında bir ilktir. ikinci olarak önerilen geliştirilmiş algoritmamız oldukça başarılı sonuçlar üretirken rastsal anahtarlama metodu ile üretilen sonuçların oldukça kötü olduğu gözlenmiştir. Çözümlerimiz, yayınlanmış ve akademik literature girmiş olan Min'in (1989) tek ve Dethloff un (2001) kırk örnekli problemlerinin girdileri esas alınarak üretilmiş ve yayınlanmış, bilinen en iyi sonuçlarla karşılaştrnlmıştır. Parametre testleri

ABSTRACT In this study, we focus on the theoretical framework of a decision model for a real world problem. The problem reveals itself as simultaneous distribution of commodities and recollection of empty packages the same size as the initial state with a single depot and a fleet of uniform vehicles with limited capacities. Resembling instances pile a profound literature under the category of `pick-up and delivery problems with backhauls` and `rural postman problem.` To solve the arousing NP-hard problem we use genetic algorithm approach. Computational efficiency and a good solution performance are sought. We have studied the wide literature of the vehicle routing problems, classified and briefly introduced the previous asserted algorithms, which provide considerably high quality solutions. We have developed a genetic algorithm based meta-heuristic on a linear IP model proposed by Dethloff (2001) and conducted tests to come up with a robust heusritic producing results with a reasonable quality. The models we studied were mainly taken from the machine scheduling literature and adapted to handle our problem. Our research has revealed that no resembling problem has ever been proposed to be solved using the genetic algorithms approach. Thus, this work is a first in its field. The improvement algorithm is found to be considerably good performing while the random keys method failed to produce reasonable solutions. We have tested our algorithm on two benchmark problems introduced by Min (1989) and Dethloff (2001). The latter is composed of 40 problem instances generated. We have performed parameter tests to tune our algorithm and shown that our algorithm produced the best ever solution for the first problem and considerably good solutions for the second one.