Çok amaçlı elektrikli araç rotalama probleminin hiyerarşik bir metasezgisel algoritma ile çözümü = The solution to the multi-objective electric vehicle routing problem using a hierarchical metaheuristic algorithm

Abstract

Gerçek hayattaki rotalama planlarında, tek bir amaca dayanmadan birden fazla amacın optimize edilmeye çalışıldığı bir gerçektir. Bu doğrultuda, tez çalışmasında ürünlerin müşterilere dağıtım işleminin elektrikli araçlar (EA) ile yapıldığı araç rotalama probleminin (ARP) güncel bir çeşidi olan elektrikli araç rotalama problemi (EARP) çok amaçlı olarak ele alınmıştır. Ele alınan çok amaçlı elektrikli araç rotalama problemi (ÇAEARP), birbiriyle çelişen beş adet amaç fonksiyonu olacak şekilde düşünülmüş, buna ilaveten ÇAEARP, farklı şarj politikaları (tam veya kısmi) ve şarj teknolojileri (yavaş, orta veya hızlı) göz önünde bulundurularak üç farklı senaryo halinde modellenmiştir. Ele alınan ÇAEARP'nin çözümü için ilk aşamada Hibrit Karınca Kolonisi Optimizasyonu (HKKO) ve ikinci aşamada ise Yapay Arı Kolonisi Algoritmalarının (YAKA) kullanıldığı iki aşamadan oluşan hiyerarşik bir yöntem (HKKO-YAKA) geliştirilmiştir. YAKA'da başlangıç çözümü rastgele üretildiği için problemin çözüm süresi olumsuz yönde etkilenebilmektedir. Problemin çözüm süresini hem kısaltmak hem de daha iyi sonuçlar elde edebilmek için geliştirilen yöntemin ilk aşamasında, yerel arama yöntemleriyle desteklenmiş ve kabul kriteri olarak da tavlama benzetimi kullanılan HKKO kullanılmıştır. İkinci aşamada ise birinci aşamadan elde edilen çözüm YAKA için başlangıç çözüm olarak ele alınıp EA'lar için nihai rotalar oluşturulmuştur. HKKO-YAKA'nın performansının değerlendirilmesi için Felipe ve ark., (2014) tarafından geliştirilen test problemleri kullanılmıştır. Elde edilen sonuçlar geliştirilen yöntemin makul sürede iyi çözümler bulmada etkili olduğunu göstermektedir. Ayrıca, geliştirilen HKKO-YAKA'nın bir gerçek hayat ÇAEARP üzerinde uygulanabilirliği gösterilmiştir. HKKO-YAKA, Pareto-optimal çözümleri bulmak amacıyla ağırlıklı toplam yöntemi (ATY) ve konik skalerleştirme yöntemi (KSY) için arama işlemi olarak kullanılmıştır. KKO-YAKA'nın gerçek hayat problemi üzerindeki performansını değerlendirmek için çok amaçlı evrimsel algoritmalardan olan çok amaçlı parçacık sürü optimizasyonu (ÇAPSO) ve uyarlanmış ÇAPSO adını verdiğimiz başka bir ÇAPSO kullanılmıştır. Sonuç olarak, çok amaçlı geleneksel yöntemler çok amaçlı evrimsel algoritmalara göre daha etkili sonuçlar verdiği görülmekte ve kısmi şarj politikası ile çoklu şarj teknolojisi seçeneklerinin lojistik şirketlerinin rota kararlarını önemli ölçüde iyileştirebileceği görülmüştür.

In real-life routing plans, more than one objective is tried to be optimized without relying on a single objective. In this direction, the electric vehicle routing problem (EVRP), which is a current version of the vehicle routing problem (VRP), in which the products are distributed to the customers with electric vehicles (EV), was discussed in the thesis study. The multi-objective electric vehicle routing problem (MOEVRP) was considered to have five conflicting objective functions. The first is minimizing the total charging cost, which consists of fixed and variable costs. Because batteries allow a limited number of recharge cycles during their operating life, a fixed cost is associated with each recharge. On the other hand, variable cost is the sum of the cost of charging the batteries during the day and at night. The others minimize the number of vehicles required; the total traveled distance, the load-dependent energy consumption, and the number of charging stations required. In addition, MOEVRP was modeled in three different scenarios, considering different charging policies (full or partial) and charging technologies (slow, medium, or fast). A hierarchical approach consisting of two stages (HACO-ABCA) was developed, in which a hybrid ant colony optimization (HACO) was used in the first stage, and an artificial bee colony algorithm (ABCA) was used in the second stage for the solution of the MOEVRP. Since the initial solution is randomly generated in ABCA, the solution time of the problem may be adversely affected. HACO was used in the first stage of the developed approach to shorten the solution time and obtain better results. Local search methods supported the HACO, and simulated annealing was used as the acceptance criterion. In the second stage, the solution obtained from the first stage was considered the initial solution for ABCA, and final routes were created for the EVs. To test the performance of the developed HACO-ABCA, we used the benchmark instances presented by Felipe et al. (2014). The benchmark instances consist of 60 data sets. The results were compared with the TB-based algorithm and the mat-heuristic method proposed by Felipe et al. (2014) and Keskin and Çatay (2018), respectively. Comparisons are made in terms of total charging costs. The results show that our HACO-ABCA improves all the solutions and forty-seven instances found by Felipe et al. (2014) and Keskin and Çatay (2018), respectively. Also, the applicability of the developed HACO-ABCA on a real-life MOEVRP was demonstrated. The objective is to determine the most feasible routes for vehicles to meet the weekly store demands of a supermarket chain in Turkey. HACO-ABCA was used as the search engine for the weighted-sum method (WSM) and the conic method (CM) to find Pareto-optimal solutions. First, five objective functions were scalarized separately with WSM and CM, and then Pareto-optimal solutions were found with HACO-ABCA. Multi-objective particle swarm optimization (MOPSO), one of the multi-objective evolutionary algorithms, and another MOPSO, which we call the modified MOPSO, were used to evaluate the performance of the HACO-ABCA on the real-life problem. In MOPSO, the initial solution is randomly generated. This situation negatively affects the solution quality. In the modified MOPSO, the initial solution is determined by the developed hierarchical approach, and then the solution is continued with the MOPSO, and the final solution is found. The obtained results showed that the results obtained by the developed hierarchical approach produced better results than MOPSO and modified MOPSO in three scenarios. If we evaluate the hierarchical approach, better performance was obtained when using CM compared to WSM. Apart from comparing the methods, it can also be concluded that the partial recharge and multiple recharge technology options can significantly improve the route decisions of logistic companies.