Kapasiteli ayrıt rotalama problemi (KARP), bir serimdeki gezilmesi gereken bütün ayrıtlara kapasite kısıtlı araçlarla toplamda en küçük maliyetli olacak şekilde servis verecek araç turlarının belirlenmesi olarak tanımlanır. KARP‘ta araçlar gezilmesi gereken ayrıtlara servis verirken kapasite kullanmaktadır. Bu çalışmada, araçların servis verirken kullandığı kapasitenin yanı sıra servis vermeden geçtiği ayrıtlarda da kapasite kullandığı yeni bir KARP türü incelenmiştir. Tanımlanan KARP türündeki ayrıt talebi, ayrıta servis verilip verilmemesine göre değiştiğinden bu problem değişken ayrıt talepli kapasiteli ayrıt rotalama problemi (DAT-KARP) olarak adlandırılmıştır. Bu çalışmada, DAT-KARP için bir matematiksel model geliştirilmiştir. Ayrıca tanımlanan problemin büyük boyutlu problemlerde çözülebilmesi için KARP için önerilmiş olan Ulusoy‘un bölümlendirme sezgiseli probleme uyumlandırılmış ve bir genetik algoritma önerilmiştir. KARP için önerilmiş test problemleri DAT-KARP‘a uygun hale getirilmiş ve önerilen yöntemlerin etkinliği bu test problemleri üzerinde gösterilmiştir.
Capacitated arc routing problem (CARP) is the determination of vehicle tours that serve all required edges exactly in a network by a capacity constraint vehicles with minimization of total cost of all vehicle tours. In CARP, vehicles use capacity while servicing required edges. In this study, a new CARP variation is examined in which vehicles use capacity while traversing an edge whether servicing or not. In the new CARP formulation, the demand of an edge is varied depends on the service status, so this problem called as capacitated arc routing problem with varying arc demands (VAD-CARP). In this study, a mathematical model is proposed for the VAD-CARP. For the large scale problems Ulusoy‘s partitioning heuristic is modified and a genetic algorithm is proposed for the new CARP variation. Effectiveness of the proposed methods is shown on test problems for VAD-CARP which are obtained by modifying CARP test problem instances.
