Capacitated vehicle routing optimization via quantum inspired hybrid metaheuristics: Feature angular encodings and kernel-based embedding models
Kuantumdan esinlenilmiş hibrit metasezgisel yöntemlerle kapasiteli araç rotalama optimizasyonu: Özellik açısal kodlaması ve kernel tabanlı kodlama modelleri
- Tez No: 1024517
- Danışmanlar: PROF. DR. BAŞAR ÖZTAYŞİ
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Quantum-Inspired Hybrid Optimization, Meta-Heuristic Hybrid Hamiltonian Scoring, Capacitated Vehicle Routing Problem (CVRP)
- Yıl: 2026
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Kapasite kısıtlı araç rotalama problemleri, lojistik ve tedarik zinciri sistemlerinin uzun yıllardır en çok çalışılan ve geliştirilen alanlarından birisidir. Amaç kapasite kısıtlı araçların, belirli talep noktalarına hzimet verebilmesini minimum maliyetle sağlayan rotaların planlanmasıdır. Klasik yöntemlerle çözülmesi zor olan bu sınıf problemlerde özellikle günümüz çok değişkenli ve akış öncelikli sistemlerin devasa boyutlara ulaşması neticesinde çok değişkenli bir yapıya genişlemiş olmasıyla karşı karşıyayız. Bu durumda daha esnek çözüm aralıklarına, esnek kısıt davranışlarına izin veren metasezgisel yöntemlerin geliştirilmesi sonucunda sektörel ve güncel problemlerin üstesinden gelinmeye çalışılmaktadır. Bu çözüm yöntemlerinin yanında geliştirilen hibrit algoritmalar sayesinde yakınsama hızını arttıran yöntemler literatürde gittikçe daha geniş yer tutmaktadır. Kuantum çerçevesinde geliştirilmiş algoritmalar, lojistikten yapay zeka sistemlerine, kimya uygulamalarından finansal sistemlere kadar başta araştırmaların ve endüstri pratiklerinin odak noktası halini almıştır. Avantaj/dezavantaj karşılaştırmalarının hız kazanmasıyla şüphesiz optimizasyon ve insan-makine etkileşiminin boyutlarının gelecekte daha çok önem kazanacağı açıktır. Kuantum tabanlı yaklaşımlar, süperpozisyon ve paralel durum uzayı keşfi gibi hesaplama becerileri sayesinde klasik ve yalın metasezgisel algoritmalara kıyasla farklı arama alanlarında yalnızca alternatif oluşturmakla kalmayıp sektörün büyük hacimli problemlerde ihtiyaç duyacağı dinamikleri sunmaktadır. Özellikle kuantumdan ilham alan hibrit modeller, klasik meta-sezgisellerle kıyaslandığında daha zengin çözüm uzayına erken aşamalardan erişmesiyle ve daha hızlı alternatif çözümler üreterek optimuma yakınsama potansiyeli göstermektedir. Bu karşılaştırmalı avantaj, kuantum optimizasyonun günümüz gelişen koşullarında henüz erken aşamalarında olmasına rağmen altyapının gelişmesiyle birlikte lojistik problemleri bağlamında büyük bir potansiyeli olduğunu şimdiden göstermektedir. Kuantum optimizasyonu sayesinde, özellikle büyük ölçekli lojistik problemlerde stokastisite kısıtları gibi koşulların yeterince doğal olarak ifade edilememesi durumunda alternatif çözümler sunan bu çalışma literatüre geniş kapılar açmaktadır. Buradaki zorluk, -“NP-hard”sınıfı altında ifade edilen kapasite kısıtlı araç rotalama problemi olan CVRP, çok depolu kapasite kısıtlı araç rotalama problemini ifade eden MDCVRP gibi çeşitli problem tipleri ve varyantlarında- literatüre ek olarak daha önce sunulmamış olan optimuma yakınsayan başlangıç çözümlerinin kuantum özellik haritalama sayesinde üretilmesiyle çözülmektedir. Başlangıç çözümlerinin oluşturulmasında kuantum hesaplama yöntemleri kullanılarak veri setleri içerisindeki veri benzerliklerinin yakalanması sayesinde nicel olarak birbirlerine benzer kümeler oluşturulabilmektedir. Literatürdeki kuantum optimizasyon yaklaşımlarından en belirgin ikinci farklı nokta olarak, değişkenleri doğrudan qubitlere atamak yerine değişken özellikleri olan koordinat verileri qubitlere kodlanmaktadır. Böylece klasik QAOA gibi yöntemlerden farkı veri seti büyüdükçe qubit ihtiyacının kümülatif olarak artmasının önüne geçmektir. Burada doğrusal olmayan etkileşimler doğal biçimde temsil edilerek kuantum dolanıklıkla ifade edilmektedir. Söz konusu düğüm skorları, kuantum dönüş açıları, gürültü altında ölçüm, durum vektörü simülasyonları gibi aracılarla ölçülerek kuantumun beklenen skor üretme yeteneğinden faydalanılmaktadır. Depo parametrelerini merkez kabul eden ve deterministik şekilde kalibre edilmeden (sabit parametre içermeyen ölçümlere dayanan) modellerde kurulan denklemlere ek; yalın düğüm benzerliklerine dayalı, kernel matris üzerinde ikili karşılaştırma yöntemi esas alınan kuantum skorlar elde edilmiştir. Önce grupla sonra rotala stratejisine benzer bir strateji uygulanır. Skorların sıralanmasıyla tek zincirli yapı kurulur, sonrasında araç atama stratejileri geliştirilir. Burada beklenen çıktı; tek zincirli yapıda ardışık olarak sıralanan düğümlerin, sınırları kendiliğinden belirlenmiş kümeler oluşturması yönündedir. Bu sayede tek zincirli ham rota, sonraki adımlarda uygulanacak olan metasezgisel komşuluk aramalarına düşen yükü azaltacak ve kuantumun ürettiği ham araç rotalarında dahi optimuma yakınsayan çözümler sunacaktır. Sonraki aşamada araç kapasitelerine bakılarak geliştirilen atama stratejileriyle literatürde gelecek çalışmalar için yön belirlenmiştir. Kuantum algoritmaları ile üretilen başlangıç çözümleri, literatürde sıkça karşılaşılan Tabu arama, Genetik algoritma gibi çeşitli metasezgisel çözüm yöntemlerine aktarılmıştır. Düğüm noktalarının koordinat ve talep değerleri gibi tekil“özellikleri”kuantumun Hilbert uzayına aktarılarak özellik haritaları hazırlanmakta, haritalar üzerindeki veri noktalarının enerji skorları ölçülerek de 5 farklı yöntem geliştirilmektedir. Tam olarak bu noktada zincirde ardışık olarak yer alan herhangi iki komşu noktanın Öklidyen uzaklığının da benzer korelasyona sahip olduğunu göstermek amacıyla pearson korelasyon testleri uygulanmıştır. Kuantum enerji yüzeyli faz haritaları üzerine düğümler yerleştirilir. Skorların dağılımı literatürde çokça kullanılan karşılaştırma setlerinden olan Augerat'ın A-n32-k5 seti üzerinde uygulanarak görselleştirilmiştir. Çalışmada geliştirilen beş yöntem ayrıca Augerat setlerinden olan A-n33-k5, B-n38-k6 ve An-45-k6 veri setleri üzerinde de test edilmiştir. Başlangıç atamaları kuantum yöntemleri ile hesaplanarak skorlandırılan verilere ait ilk atama sonuçları ayrıca çalışmanın sonunda ekler bölümünde detaylı şekilde sunulmuştur. Ekler içerisinde bu atamalar üzerinde kuantumun performansına ölçemeye dayanan metriklere de yer verilmiştir. Bu metrikler, araç atama adımları tamamlanan başlangıç rotalarının optimum çözümleri bilinen bahsi edilen karşılaştırma setleri üzerinde uygulanması, araştırmanın kanıtlanabilirliğini desteklemektedir. Bu adımdan sonra önerilen her methodun başlangıç çözümlerine Levenshtein ve kenar benzerlik testleri uygulanmıştır. Testlerin uygulanışı optimum sonuçlar ile başlangıç atamaları arasında gerçekleştirilmektedir. Benzerlikler, ekler kısmında açıkça gösterilmiştir. Bahsedilen tüm methodlar Python (3.12.3 versiyonu) çerçevesinde IBM Qiskit kütüphanesi (2.3 versiyonu) kullanılarak 2.3 GHz CPU çekirdek hızındaki AMD Ryzen 7 3750H altyapısı ile simüle edilmektedir. Tabu arama algoritması, araç rotalama problemleri gibi kombinatoryal optimizasyon problemlerinde sıkça kullanılan güçlü meta-sezgisel yöntemlerden birisidir. Temel yaklaşımında, klasik ve tam çözümü hedefleyen yerel arama algoritmaları ile grafik tabanlı uygulamaların sıkça karşılaştığı lokal optimuma takılma sorununu aşmak için bellek yapıları kullanmaktır. Tabu listesi olan aramanın hafızası mekanizması sayesinde, yakın geçmişte araçlar arası uygulanan her hareket veya elde edilen çözüm geçici olarak kısıtlanır ve algoritma çözüm uzayında yeni alanlara genişleyerek keşif yeteneğini arttırır. Bu mekanizma, CVRP gibi karmaşık ve çok boyutlu problemlerde yerel en iyilere takılmaktan çözümü kurtarır. Çalışmada tercih edilen metasezgisel yöntem olan Tabu arama algoritmasının komşuluk tanımları geniş tutulmuştur. İki farklı gruba ayrılan veri setleri üzerinde testler gerçekleştirilmiştir. Komşuluk arama tanımları rota içi ikili segment değişimi, çapraz segment değişimi, rotalar arası segment değişimi ve kuyruk değişimleri olarak belirlenmiştir. Metasezgisel yöntem uygulamalarından farklı olarak literatürdeki sezgisel yöntemler ve kesin çözücüler kullanılarak aynı problem setleri çözülmektedir. Ayrıca Tabu arama algoritması değiştirilmeden, yalnızca klasik başlangıç çözümü üretim yaklaşımları (Clarke & Wright, Greedy) üzerine aynı tabu ve komşuluk arama stratejileri eklenerek aynı problem setleri çözülmüştür ve Bölüm 5'in altında performans karşılaştırması yapılmıştır. İlerleyen araştırmalar için kuantumdan ilham alan başlangıç çözüm üretimlerini alternatif hibritlerle değerlendirmek gerekebilir. Bu konuda en iyi adaylardan birisi olarak kuantumdan ilham alan modellerin ürettiği başlangıç atamalarını yine metasezgisel algoritmalardan birisi olan genetik algoritma veya baskın olmayan sıralama genetik algoritması II gibi alternatif metasezgiselleri birleştiren hibrit uygulamalarla desteklenebilir ve performans ölçümleri yapılabilir. Sonuç olarak geliştirilen yöntemler göstermektedir ki, veri setlerinin yapısına göre değişiklik göstermek kaydıyla kuantumdan ilham alan hibrit algoritmalar; geleneksel kesin çözücüler, sezgisel ve metasezgisel yöntemler karşısında büyük oranda üstünlük göstermektedir. Ayrıca gelecekte artacak olan kuantum altyapılarıyla hibrit olarak tasarlanabilecek optimizasyon programları birçok açıdan esnek olacaktır. Bunun yanısıra, kuantum Hilbert uzayında temsil edilen düğüm özelliklerinin yalnızca CVRP gibi problem tipleriyle sınırlı kalmayarak gelecekteki çalışmalarda farklı veri özelliklerinin kolaylıkla ifade edilebilmesi de sağlanabilir.
Özet (Çeviri)
The increasing integration of quantum computing into daily operational fields such as logistics, artificial intelligence, and financial systems has accelerated the comparative analysis of these technologies, underscoring the growing significance of quantum-inspired optimization in future industrial frameworks. In line with future needs, there will be an increasing demand for quantum-inspired enhanced models of problems with various challenges, such as CVRP and MDCVRP, along with metaheuristic algorithms. The increasing dynamism and stochasticity in the logistics sector have led to a rise in quantum-inspired research. Numerous studies exist in the literature focusing on identifying the potential advantages of methods developed for solving logistic problems using quantum algorithms. In addition to studies utilizing quantum mechanisms in all steps of the problem, hybrid quantum and metaheuristic approaches also exist, with varying roles of quantum mechanics in these methods. In light of these developments, this study presents a perspective that evaluates the natural capabilities of quantum mechanics, such as clustering and stochasticity generation. Furthermore, it proposes mechanisms that generate successful initial solutions to the CVRP literature by developing five different quantum-inspired models that are open to innovation in many aspects for the future of quantum optimization studies. By applying a Quantum-Inspired Hybrid Optimization approach to NP-hard class optimization problems like CVRP, the characteristics of the problem type are encoded into nonlinear trigonometric rotation angles, and sequential energy scores are derived through Hamiltonian expectation scores using a state vector simulator, leading to a solution. All of the Quantum-Inspired algorithms mentioned here have been tested on simulations created using the Qiskit (version 2.3) library in the Python (version 3.12.3) environment with an AMD Ryzen 7 3750H and CPU 2.3 GHz. The CVRP feature list consists of customer coordinates and demand values. Since stochastic initial route assignments will be valuable, a hybrid structure is created that uses tabu search and local optimization heuristic methods (OR-opt, relocate, crossover swap, tailswap) following“flow-preserving”sequential-based initial solutions while maintaining system dynamism. The proposed methods are tested with case studies divided into two groups. The first group of datasets consists of randomly generated datasets using 100% vehicle capacity for small and large-scale problems. Small and large-scale problems are compared using different solvers with the PYTHON framework (CPLEX/PULP). The second group of datasets includes Augerat sets, which are literature benchmark sets. The basic approach proposed for these two separate problem sets can be replicated with different feature sets in future studies.
Benzer Tezler
- Bounding and dominance approaches in improving the efficiency of branch and bound type solution to the“SCLS”problems
Başlık çevirisi yok
KUDRET DEMİRLİ
Yüksek Lisans
İngilizce
1988
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiYRD. DOÇ. DR. SİNAN KAYALIGİL
- Algorithms for multi-level capacitated lot-sizing problem with set-up times
Başlık çevirisi yok
E.İFFET ŞAHİN
Yüksek Lisans
İngilizce
1989
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiDOÇ. DR. ÖMER KIRCA
- A Polynomially bounded dual simplex algorithm for capacitated minimum cost flow problem
Başlık çevirisi yok
AYŞEGÜL ALTABAN
Yüksek Lisans
İngilizce
1990
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. CANAN A. SEPİL
- Efficient procedures for multi-item lot sizing problems based on tight formulations
Başlık çevirisi yok
MELİH KÖKTEN
Yüksek Lisans
İngilizce
1990
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ÖMER KIRCA