Eş zamanlı dağıtım ve toplamalı elektrikli araç rotalama problemi için kısıt programlama yaklaşımları

Bağcı İ., Çil Z. A., Öztop H.

JOURNAL OF THE FACULTY OF ENGINEERING AND ARCHITECTURE OF GAZI UNIVERSITY, cilt.41, sa.2, ss.795-813, 2026 (SCI-Expanded, Scopus, TRDizin)

Özet

Ulaştırma faaliyetlerinde kaynak tüketimi ve geleneksel araçların çevreye verdiği zararların artması ile sürdürülebilirlik çalışmaları kapsamında çevre dostu elektrikli araçların kullanımı giderek artmaktadır. Bu çalışmada, elektrikli araç rotalama problemi (EARP) ve dağıtım ve toplama operasyonlarının eş zamanlı gerçekleştiği eş zamanlı dağıtım ve toplamalı elektrikli araç rotalama problemi (EDT-EARP) incelenmiştir. Çalışılan problemlerde, mesafeye bağlı toplam elektrik tüketim maliyeti ve kullanılan toplam elektrikli araç sayısının maliyetini içeren toplam maliyet minimizasyonu hedeflenmiştir. Bu çalışmada, literatürdeki çalışmalardan farklı modelleme yaklaşımları kullanılarak EARP için bir karma tam sayılı doğrusal programlama (KTDP) modeli ve iki farklı kısıt programlama (KP) modeli sunulmuştur. Ayrıca, EDT-EARP için iki özgün KTDP modeli ve iki özgün KP modeli de geliştirilmiştir. Çalışmada çözüm uzayını daraltmak amacıyla EARP ve EDT-EARP için önerilen KTDP ve KP modellerinde simetri-kırma yapısı kullanılmıştır. Geliştirilen matematiksel modellerin performansı üretilen veri örnekleri üzerinde detaylı sayısal analizler yapılarak karşılaştırılmıştır. Sayısal sonuçlar incelendiğinde, problemin boyutu arttıkça geliştirilen KP modellerinin KTDP modellerine kıyasla daha iyi çözüm performansı gösterdiği görülmüştür. Ayrıca, simetri-kırma yapısının kullanımı ile hem KP hem de KTDP modellerinin etkinliğinin arttığı gözlemlenmiştir.

With the increasing consumption of resources and the environmental damage caused by conventional vehicles in transportation systems, the use of environmentally friendly electric vehicles has been gaining importance within sustainability-oriented efforts. This study focuses on the Electric Vehicle Routing Problem (EVRP) and the Simultaneous Pickup and Delivery Electric Vehicle Routing Problem (SPD-EVRP), in which delivery and collection operations are performed simultaneously. The studied problems aim to minimize the total cost, which includes the cost of distance-based electricity consumption and the cost of the total number of electric vehicles used. In this study, a mixed-integer linear programming (MILP) model and two different constraint programming (CP) models are developed for the EVRP by using different modeling approaches from the studies in the literature. Two novel MILP and two new CP models have also been developed for SPD-EVRP. Symmetry-breaking structures are used in the proposed MILP and CP models for the EVRP and SPD-EVRP to reduce the solution space of the problems. The performance of the developed mathematical models is tested on the generated instances by performing a detailed numerical analysis. When the numerical results are examined, it is observed that, as the problem size increases, the CP models demonstrate superior solution performance compared to the MILP models. Furthermore, the incorporation of symmetry-breaking structures enhances the computational efficiency of both CP and MILP approaches.