tarihinde yayınlandı Yorum yapın

IBM CPLEX MSSQL Database Connection

Eğer bu yazıyı okuyorsanız CPLEX’in ne olduğu hakkında bir fikriniz vardır. Ama eğer bilmiyorsanız, Wikipedia ve IBM sitelerindeki açıklamaları inceleyebilirsiniz.

CPLEX bir optimizasyon çözüm yazılımı. CPLEX’i çok uzun süredir severek kullansam da, ne yazık ki dünya çapında çok yaygın bir kullanımı olmamasından dolayı ekosistemi çok gelişmemiş durumda. Kendi dokumantasyonu ve örnekleri dışında bir yardıma ihtiyacınız olduğunda ya da bir hata ile karşılaştığınızda zor anlar yaşayabiliyorsunuz. Neyseki, Alex Fleischer ve Eray Çakıcı gibi CPLEX’e gönül vermiş kişiler var da, sorunlarımızı kısa sürede çözebiliyoruz.

CPLEX Aralık 2020’de yeni bir sürüm çıkardı. Hatta versiyon sistemini değiştirdiği için, 12.10’dan bir anda 20.1’e geçiş yaptı. Eski versiyonlama sisteminde, büyük değişiklikler major versiyonu, geliştirmeler ve iyileştirmeler için de minor versiyonu artıyordu. Alınan karar doğrultusunda, yeni versiyonun çıktığı sene major ve o sene içindeki geliştirme ve iyileştirmeler de minor arttırma olarak yapılmasına karar verildi.

Versiyondur değişir. Peki bunun konumuzla ne alakası var? CPLEX versiyon atladıkça, çözücünün gücünü arttırmaya devam ediyor. Süreler kısalıyor, çözümler iyileşiyor. Fakat, bizim gibi CPLEX’i bir ürünün içine konumlandıran kişiler için önemli bir handikap ortaya çıkıyor. Veritabanı bağlantı metotlarının değişmesi. 12.5 ve öncesinde kullanılan veritabanı bağlanma metotu, 12.6 sürümünde kullanılamamaya başlanmıştı. Bu çok büyük bir problem olmuştu. 12.6’da kullanılan metot güvenlik açısından daha iyi olduğu iddia edilse de, fonksiyonel olarak sıkıntıları da beraberinde getirmişti. 20.1 sürümü ile bu sıkıntılar giderildi ve artık çok daha kolay bir şekilde veritabanı bağlantı yapılabilmektedir. (12.6’da kullanılan metot 20.1’de hala kullanılıyor fakat yenisini öğrenip uygulamanızı tavsiye ediyorum)

Bu yazımda, 12.5 ve öncesi, 12.6 ve sonrası, 20.1 için MSSQL veritabanı bağlantılarını nasıl yapacağınızı anlatacağım. Benim gibi internette kaynak arayıp bulamayanlara gelsin 🙂

Authentication

SQL Server’a bağlanmanın 2 temel yöntemi vardır. Bunlar:

1- Windows Authentication

2- SQL Server Authentication

Bu yazımızda SQL Server Authentication anlatacağız. Eğer OPL Studio üzerinde yazdığınız bir modeli, zamanlanmış bir görev ile çalıştırmayı hedefliyorsanız ya da bir uygulamaya bağlayacaksanız tavsiyem SQL Server Authentication. Nedeni de, Windows Authentication ile bağlantı kurmuşsanız, CPLEX kurulu sunucunun restart olması durumunda ilgili kullanıcı ile o makinaya login olmadığınızdan dolayı o model çalışmayacaktır. Ya da sizin kullanıcız logout olduysa da aynı problemle karşılaşırsınız. Çalıştığınız şirkette SQL Server Authentication için yetki almanız zor olsa da sadece ilgili SQL sunucuya ve ilgili tablolara yetki isteyerek bunu çözebilirsiniz.

Örnek Veritabanı

Aşağıda bağlantı yollarını (connection string) paylaşacağım kodlar için CPLEX’in içinde gelen Oil örneğindeki veri setlerini kullanacağım. SQL’de input (girdi) tablosu ve bir tane de örnek çıktıları yazacağım boş bir tablo oluşturuyorum. Denemek isterseniz diye bu tabloları oluşturduğum scriptleri de yazıyorum.

--Input tablosu
CREATE TABLE dbo.OilData(
capacity int NULL,
price float NULL,
octane float NULL,
lead float NULL
)
INSERT INTO dbo.OilData (capacity, price, octane, lead) 
SELECT 5000, 45, 12, 0.5
INSERT INTO dbo.OilData (capacity, price, octane, lead) 
SELECT 5000, 35, 6, 2
INSERT INTO dbo.OilData (capacity, price, octane, lead) 
SELECT 5000, 25, 8, 3
--Output Tablosu
CREATE TABLE dbo.OilResult(
capacity int NULL,
price float NULL,
octane float NULL,
lead float NULL,
result float NULL
)

.mod dosyası

OPL tarafında bir model oluşturduğunuzda 1 zorunlu 2 opsiyonel dosya oluşturursunuz. Zorunlu olan mod (model) dosyasıdır. dat (data) ve ops (settings) ise opsiyoneldir. Eğer modeliniz, bir veritabanı, excel ya da başka bir veri kaynağına bağlı ise dat dosyası da zorunlu hale gelmiş olur.

Aşağıda her bir sürüm için dat dosyası içinde nasıl MSSQL veritabanına bağlayacağımızı yazacağız. Bunun öncesinde mod dosyasında, bağlayacağımız tuple nasıl olacak onu da yazalım.

tuple oilData {
int capacity;
float price;
float octane;
float lead;
}
{oilData} OilDatas = …;

Veritabanından okuduğumuz tabloyu bu tuple içine atacağız. Sonrasında modelimiz çalışacak ve sonucu da tekrar veritabanında bir tabloya yazmak istiyoruz. Çıktı tablomuzu da oluşturalım

tuple oilResult {
int capacity;
float price;
float octane;
float lead;
}
{oilResult} OilResults = …;

12.5 ve öncesi

Veritabanı bağlantısı açmak için .dat dosyamıza şu cümleyi yazıyoruz

DBConnection db(“oledb”,”kullaniciAdi/sifre/database/server”);

db” artık bizim bağlantı anahtarımız. Bunu kullanarak, okuma ve yazma işlemleri yapacağız. Hatta MSSQL’de bulunan stored procedureleri bile çalıştırabiliriz.

DBRead → Okuma
DBUpdate → Yazma ve Execute etme

Önce okuyalım ve input tuple dolduralım.

OilDatas from DBRead(db,”select capacity, price, octane, lead from dbo.OilData”);

Artık input tablomuz doldu. Sonrasında modelimiz çalıştı ve sonuçlar OilResults tupleında bulunuyor. Bunu MSSQL’de bulunan dbo.OilResult tablosuna yazmak için de aşağıdaki kodları kullanıyoruz.

OilResults to DBUpdate(db,”INSERT INTO dbo.OilResult(capacity, price, octane, lead, result) VALUES(?,?,?,?,?)”);

Son hali nasıl oldu ona da bakalım:

DBConnection db(“oledb”,”kullaniciAdi/sifre/database/server”);
OilDatas from DBRead(db,”select capacity, price, octane, lead from dbo.OilData”);
OilResults to DBUpdate(db,”INSERT INTO dbo.OilResult(capacity, price, octane, lead, result) VALUES(?,?,?,?,?)”);

12.6 sonrası

12.5 ve öncesindeyken herşey bu kadar kolaydı. Fakat 12.6 ile birlikte DBConnection kullanılmamaya başlandı. Bunun yerine JDBC üzerinden veritabanı bağlanma zorunluluğu getirildi. Bunun için öncelikle deveye hendek atlatmanız gerekiyordu. Hendek de şu, Java driverlarını indirmeniz gerekiyor ve bu driverları modelinizin bulunduğu klasörde tutmanız gerekiyordu.

Aklınızın karıştığını görüyorum. Bu sebeple daha detaylı anlatacağım.

Öncelikle IBM tarafından hazırlanan GitHub Repository’e bakmanızı öneririm. Tüm gerekli dosyaları buraya yüklemişler. Sadece açıklamaları yetersiz yapmışlar.

İlk olarak bilgisayarınızda Java’nın (Java SE Development Kit) kurulu olduğundan emin olmalısınız. Kurulu değilse şu likten indirip kurulumu gerçekleştiriyorsunuz. Kurduktan sonra command pencersinde şunu yazıp test edebilirsiniz.

java -version

İkinci aşamada, java.js ve jdbc-custom-data-source.jar dosyalarını indirmeniz gerekiyor. IBM github reposunda bunlara da yer vermiş. Şu linkten bunları da indiriyorsunuz.

Son olarak, MSSQL için gerekli olan JDBC Driverını indirmek. Microsoft’un sitesinden de indirmeniz için gerekli linki buraya bırakıyorum.

Evet, Java SDK kurulu ve gerekli olan dosyalar elimizde. Bu gerekli olan dosyaları, CPLEX projemizin bulunduğu klasöre koyuyoruz. Yani .oplproject, .project, dat ve opl dosyalarınızın bulunduğu klasöre.

Gerekli dosyaları son kez kontrol edelim:

jdbc.js
jdbc-custom-data-source.jar
mssql-jdbc-7.4.1.jre8.jar

Şimdi .dat dosyasını yazmaya başlayabiliriz. (Hendekten atlamak üzereyiz. Çok mutluyuz)

ODBC bağlantısındna farklı olarak, JDBC üzerinden bağlantıyı prepare{} içinde yazmamız gerekiyor. Aşağıda adım adım yazıyorum, son halini en altta bulabilirsiniz.

prepare {
includeScript(“jdbc.js”);

var db = JDBCConnector(“jdbc:sqlserver://server;databaseName=database;user=kullaniciadi;password=sifre”);
}

Bağlantımızı oluşturduk. Süslü parantezi kapatmadan okuyacağımız tabloyu yazıyoruz.

db.read(“OilDatas”, “select capacity, price, octane, lead from dbo.OilData”);

Ardından, modelden çıkan sonucu tabloya yazıyoruz.

db.update(“OilResults”, “INSERT INTO dbo.OilResult(capacity, price, octane, lead, result) VALUES(?,?,?,?,?)”);

İşte oldu. Son halini de paylaşalım.

prepare {
includeScript(“jdbc.js”);

var db = JDBCConnector(“jdbc:sqlserver://server;databaseName=database;user=kullaniciadi;password=sifre”);
db.read(“OilDatas”, “select capacity, price, octane, lead from dbo.OilData”);
db.update(“OilResults”, “INSERT INTO dbo.OilResult(capacity, price, octane, lead, result) VALUES(?,?,?,?,?)”);
}

Sadece connection string olarak mı problem var? Neden bu kadar deve ve hendek dedin bize diyebilirsin. Aslında sadece bağlantı için yazdıklarımız değil. Asıl problem, model içinden sql tarafında yapmak istediklerinizi istediğiniz sırayla yapmanıza engel oluyor. Mesela önce oku, sonra model sonuçlarını yaz en sonda da gidip sql tarafındaki bir tabloda bir flagi update etmeniz gerekiyorsa gidip ilk başta update edebiliyor. prepare içine çok müdahale edemiyorsunuz.

Ben bunu nasıl çözdüm. Flow ile çözdüm. Başka bir yazıda daha detaylı anlatırım. Fakat yaptığım, Ana bir mod dosyası üzerinden, alt (sub) mod ve dat dosyalarını çalıştırarak ilerledim. Bu sayede, WarmStart’ı da OPL üzerinden başarılı bir şekilde uygulamış oldum.

20.1 ve sonrası

Günümüze geldik 🙂 IBM 12.6 ve sonrası yaşanan sıkıntılardan çok başı ağrımış olacak ki, 20.1 ile birlikte ODBC bağlantı öelliğini geri getirmiş. Biz de açıkçası bu durumdan çok memnun olduk. Fakat, baktığımızda konu hakkında bilgi veren içerik olmadığını gördük ve üzüldük.

İlk olarak şunu söyleyelim. IBM CPLEX versiyonlarını geliştirmesinin temel amacı, çözücünün performansının arttırmaktır. Arkada çalışan modellerin, sezgisel algoritmaların, parametrelerin ve bilgisayar gücünün verimli kullanılmasının geliştirilmesi ile yeni versiyonları ortaya çıkmaktadır.

Aşağıda CPLEX sürümlerinin model çözüm sürelerinin karşılaştırılmasını görebilirsiniz.

https://medium.com/@AlainChabrier/cplex-12-10-on-wml-79b2c64f25b3

12.5 sürümünü kullanan ve MSSQL bağlantısı ile modellemiş bir kullanıcı, lisans yenileme yaptıktan sonra 12.6’da modelinin çalışmadığını görmek büyük bir probleme sebep olmuştu. ODBC bağlantılarını JDBC’ye çevirmek, veri okuma performansları ile başetmek üzmüştü.

Neyseki, 12.6 ve sonrasında kullanılan JDBC connectorları 20.1 sürümünde de kullanabiliyorsunuz. Buna ek olarak, 12.5’te bulunan ODBC bağlantıları tekrar geri geldi. Daha doğrusu, CPLEX’in yeni sürümünde bu driver yüklü olarak geldiği için, herhangi ek bir driver kurulumuna ihtiyaç olmadan çalıştırabiliyorsunuz. Sadece syntax biraz değişti. Gelin isterseniz buna bakalım.

Öncelikle bizim de bu bağlantıları yaparken faydalandığımız linki paylaşalım. Yine IBM’in kendi sitesinde CPLEX dokumantasyonunda da gün geçtikçe bilgiler artıyor. (Gözler yaşlı 🙁 )

Veritabanı bağlantısı için ilk cümlemizi yazıyoruz.

ODBCConnection db(“Driver={SQL Server};Server=server;Database=database;Uid=kullaniciadi;Pwd=sifre;”, “”);

Bağlantı cümlemizin sonunda bulunan “” içine her çalışan sorgunun öncesinde çalışmasını istediğiniz bir sorgu varsa bunu yazabiliyorsunuz. Örneğin, her yazma öncesinde bir sp exec etmek isterseniz onu yazabilirsiniz. Bunu ben boş bırakıyorum.

Tuple için okuma cümlesine geçiyoruz.

OilDatas from ODBCRead(db, “select capacity, price, octane, lead from dbo.OilData”);

Gördüğünüz üzere, ODBCRead komutunu okumak için kullanıyoruz. Yazmak için de aşağıdaki cümleyi kullanıyoruz.

OilResults to ODBCPublish(db, “INSERT INTO dbo.OilResult(capacity, price, octane, lead, result) VALUES(?,?,?,?,?)”);

Tupleda bulunan verileri de ODBCPublish ile tekrar veritabanına yazmış oluyoruz.

Burada bahsetmem gereken bir konu daha var. 20.1 sürümünde, iki farklı connection açabiliyoruz. (Önceki sürümlerde bu özellik var mı bilmiyorum) Yayınlalan örneklerde, okumak için bir connection, yazmak için bir connection açılmış. Bu sayede, yazmak için açılan connection özelleştirilerek yazılan tablonun yazılmadan önce boşaltılması sağlanabiliyor.

.dat dosyasının son halini yazalım.

ODBCConnection db(“Driver={SQL Server};Server=server;Database=database;Uid=kullaniciadi;Pwd=sifre;”, “”);
OilDatas from ODBCRead(db, “select capacity, price, octane, lead from dbo.OilData”);
OilResults to ODBCPublish(db, “INSERT INTO dbo.OilResult(capacity, price, octane, lead, result) VALUES(?,?,?,?,?)”);

Güncel Problemler

13.04.2021 tarihi itibari ile 20.1 sürümünü çok yoğun bir şekilde henüz kullanmadığım için testlerimi tamamlamadım. Fakat şu ana kadar yaşadığım sıkıntıları siz yaşamayın diye burada yazıyorum. Kullandıkça yazının bu kısmını güncelleyeceğim. Buradan takip edebilirsiniz.

Karakter uyumsuzlukları

CPLEX 20.1 sürümü veri tipi seçiyor. Veritabanı katmanındaki tablolarınızdaki bazı veri tiplerini CPLEX’deki tuplelara alamıyorsunuz. nvarchar ve decimal veri tiplerini CPLEX kabul etmiyor. Bu sebeple, ya tablodaki formatlarınızı değiştirmeniz gerekiyor ya da okurken CAST() yaparak nvarchar → varchar ve decimal() →float dönüşümlerini yapmanız gerekiyor. Konu ile ilgili IBM forumundaki başlığa şu linkten ulaşabilirisiniz.

Performans Çekinceleri

Önceki sürümlerde olduğu gibi, bu sürümde de veritabanından okuduğunuz tabloların kolon ve satır sayısına göre timeout alma ihtimaliniz ne yazık ki bulunuyor. Yaptığım testlerde kolon sayısı 30’u geçen bir tablonun satır sayısı 1000’i geçtiğinde timeout alıyordu. Bu gibi durumların yaşanmaması için sadece ihtiyacımız olan kolonların modele alınması faydalı olacaktır.

Ek Bilgi

IBM CPLEX için hazırlanmış dokumanlarda çok kısa bahsedilen ama benim çıkış noktam olan, bir ayrıntıya da yer vermek istiyorum.

20.1 sürümünün örnek klasöründe bulunan ve yeni bağlantı özelliklerini tanıtan dosyalar çok faydalı. Çoğu veritabanı için bağlantı cümlecikleri için birer örneğe yer verilmiş. Başlamadan önce bir göz atmanızı tavsiye ederim.

C:\Program Files\IBM\ILOG\CPLEX_Studio201\opl\examples\opl\tabledata

Son Sözler

Bir yazımızın daha sonuna gelirken CPLEX’in tüm sürümlerinde MSSQL bağlantısını incelemiş bulunuyoruz. Umarım, CPLEX kullanan kişiler için faydalı bir yazı olmuştur.

CPLEX’i OPL üzerinden değil de Python kütüphanesi DOCPLEX ile kullanmayı düşünüyorsanız Eray Çakıcı’nın GitHub hesabına göz atabilirsiniz.

Doğrusal programlama hakkında yakın zamanda çok güzel bir yazı yayınlayan Orkun Berk Yüzbaşıoğlu’nun blogunu da okuyabilirsiniz.

Son olarak, HBR’de hem sektör hem de optimizasyon hakkında yazılar yazan Şükrü İmre’yi de takip etmenizi öneririm.

Herkese iyi modellemeler 🙂

tarihinde yayınlandı 2 Yorum

Rota Planlama – Optimizasyon – Bölüm 1

Araç Rotalama Problemi (ARP), bir merkezden coğrafi olarak dağılmış çeşitli talep noktalarına dağıtım veya toplama rotalarının, araç filosunun kat ettiği toplam mesafeyi minimize edilecek şekilde bulunmasdir. Araç Rotalama Problemi, Tedarik Zincirinde ve aynı zamanda Tedarik Zincirinin parçası olarak Lojistikte yer alan ana karar alanlarından olan taşıma ile doğrudan ilişkilidir. Gerçek dünya uygulamalarında birçok değişik kısıtlar ve farklılıklar Araç Rotalama Problemlerinde çeşitliliği de beraberinde getirmiş, literatürde ve uygulamalarda farklı özellik ve kısıtlara sahip Araç Rotalama Problemlerinin incelenmesine yol açmıştır.

Araç Rotalama Problemi, en az maliyetle verilen belirli sayıda noktayı dolaşmayı sağlamayı hedefleyen bir kombinasyonel eniyileme problemidir. Çözümü için birçok alanda kullanılmakta olan çok sayıda sezgisel algoritma geliştirilmiştir. Sezgisel algoritmaların geliştirilmesinin nedeni Araç Rotalama probleminin NP-hard (herhangi bir algoritmayla optimal sonuca ulaşılamayan problem) olmasından kaynaklanmaktadır. Rota Planlamayı polinom zamanda optimize etmek güçtür ve sezgisel algoritmalar yardımıyla optimum yakın sonuçlar bulunabilmektedir.

Aslında Rota Planlama probleminin optimum sonucunu bulmak teorik olarak mümkündür. Fakat problem kombinasyonel  olduğu için talep noktalarının 15-20’yi geçmesi durumunda optimuma ulaşmak mevcut teknoloji ile zorlaşmaktadır.

Araç Rotalama Problemleri şirketlerin ihtiyaçlarına göre farklılık göstermektedir. En büyük farklılık, problemin Açık ve Kapalı uçlu olmasıdır. Yani yollanan aracın tekrar merkeze geri dönmesi ya da dönmemesidir. Diğer bir farklılık, Geri Toplaması olan Rotalama Problemidir. Literatürde Milk Run olarak geçer. Milk Run, dağıtımla birlikte aynı zamanda aynı yerden toplama yapılmasıdır.

Bunun dışında, Araçların farklı kapasitelere sahip olması, birden fazla merkez deponun bulunması, aynı mağaza/müşteriye birden fazla aracın gitmesi, talebin belirsiz olması (marketler) gibi durumlar da söz konusudur.

Bir Araç Rotalama Probleminde çeşitli amaç fonksiyonları olabilir?
Minimum Kilometre : Araçların en kısa mesafeyi kat ederek ürün ya da hizmeti müşteri/mağazaya ulaştırmasıdır.
Minimum Zaman : En kısa mesafeye çok benzerdir. Çoğu durumda en kısa mesafeyle aynı sonucu verir. Fakat mikro dağıtım yapılıyorsa bu değişkenlik gösterebilir.
Minimum CO2 emisyonu: Minimum kilometreye çok benzerdir. Kullanılan araçların hepsi aynı ise aynı sonucu verir. Araçlar değişiklik gösterirse farklılaşır.
Minimum Araç Sayısı : Araçların kapasitelerinin (hacim ya da ağırlık) en verimli şekilde kullanarak en az sayıda araç kullanılmasını sağlar. Genelde araç başına ücret verildiği ya da boş gitmenin cezası olduğu durumlarda kullanılır.

Rota Planlama probleminin temel bileşenleri aşağıdaki gibidir.

  • Kaç kamyon kullanılmalı?
  • Hangi mağazalara hangi kamyon atanmalı?
  • Her kamyonun mağaza sıralaması nasıl olmalı?
rotalama

Bir işletme ve bu işletmenin 40 mağazası olduğunu varsayalım. Bu mağazalara maksimum 7 araç kullanarak günlük sevkiyat yapıldığını ve araçların rota planlamasının optimizasyonla yapılmak istendiğini düşünelim.

depovemagazalar

Hangi mağazalara hangi kamyon atanmalı?
Bu işletmede ortalama her bir araç 5-6 mağazaya sevkiyat yapmaktadır. Eğer tüm araçlar 5 mağazaya  sevkiyat dağıttığını düşünürsek her bir aracın hangi mağazaları içereceği 40’ın 5’li kombinasyonu şeklinde olacaktır.

Kombinasyon bir nesne grubu içerisinden sıra gözetmeksizin yapılan seçimlerdir. Nesne grubunun tekabül ettiği kümenin alt kümeleri olarak da tanımlanabilir. Çünkü alt kümelerde sıra önemli değildir.
Bir A kümesinin herhangi bir alt kümesine A kümesinin bir kombinasyonu denir. Mesela 52 iskambil kartı arasından seçilen dört kart, kartları seçme sırası önemli olmadığından bir kombinasyon problemidir. (Wikipedia)

kombinasyon

Bizim problemimizdeki tüm ihtimaller C(40,5) şeklinde olacaktır.
Birkaç örnek yazacak olursak,

komb_tablo

komb_sonuc

Bu yaptığımız hesaplamalar neden bir rotalama probleminin optimizasyon ile çözülmesinin çok zor olduğunu anlatmak içindir.
Kombinasyon her bir araç için 5 mağaza olması durumundaki tüm ihtimalleri verir. Bu aşamada klasik ARP’de olan kısıtları hatırlamakta fayda vardır.

Araç kapasiteleri : Her bir aracın bir kapasitesi vardır. Kapasiteyi en verimli kullanmak gerekir. Bazı durumlarda boş göndermeniz durumunda ceza ödemek zorunda kalırsınız.
Zaman kısıtları : Mağazaların, müşterilerin gönderdiğiniz ürün ya da hizmeti almak için zaman kısıtları mevcuttur. Örneğin bir AVM’de ise saat 10:00’dan önce ürünleri kabul etmek isteyecektir.
Yol kısıtları (Köprü Kısıtları) : Kullanılmayan yollar, saatlik kapalı yollar (Köprüler vs.), belli araçların giremeyeceği yollar gibi.
Araç kullanım süreleri: Aracın bir günde maksimum kaç saat kullanılabilecğeini gösterir.

Bu kısıtlara göre yukarıda hesapladığımız ihtimaller azalabilir. Örneğin; 3, 4, 7, 8, 9 nolu mağazaların demandlerinin toplamı bir kamyonun kapasitesinden büyük ise bu rut otomatik olarak elenir.

Her kamyonun mağaza sıralaması nasıl olmalı?
Elemlerin ardından elimizdeki ihtimaller sadece hangi kamyona hangi mağazaların konu olacağını vermektedir. Bu araç dolulukları ile ilgilidir. ARP’deki en önemli amaç fonksiyonlarından biri olan minumum kilometrenin sağlanması için her bir ihtimalin içindeki mağazaların sıralamalarının denenmesi gerekir.
Bu da Permütasyon anlamına gelmektedir.

Matematikte permütasyon, her sembolün sadece bir veya birkaç kez kullanıldığı sıralı bir dizidir.
1’den 10’a kadar olan doğal sayıları içeren n elemanlı kümede r = 4 olarak alınırsa permütasyonların sayısı {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} kümesinden sırayı da gözetmek suretiyle oluşturulabilecek dört değişik elemanlı kümelerin sayısını ifade eder. (Wikipdia)

permutasyon

Bizim yukarıda oluşturduğumuz her bir 40’ın 5’li kombinasyonların permütasyonlarını bulmalı ve bunların mesafelerini ölçmeli ve bunların da en düşük mesafeli olanlarını seçmeliyiz.

Örneğin yukarıda oluşturduğumuz kombinasyonlardan 1, 2, 3, 4, 5’in permütasyonlarını bulalım.

perm_tablo

perm_sonuc

Sonuç olarak bu problemde 40 mağazanın 5’erli olarak araçlara yerleştirilmesi sonucundaki değişken sayısı;

sonuc

Bu durumda bile problemin bir çözümü olabilir. Fakat aynı araca 5’ten fazla mağaza/müşteri konu olabilir. Aşağıda bir araca konu olan mağaza/müşteri sayısı bulunmaktadır. Rakamları gördükten sonra neden bu problemin optimizasyonla çözülemeyeceğini siz de anlayacaksınız.

40magaza

Mağaza sayısı arttığı zaman problem çok daha zorlaşmakta ve karar değişken sayısı çözülemeyecek kadar artmaktadır.

80magaza

Bu sebeple ARP probleminin çözümü için, literatürde optimizasyon yerine çeşitli heuristic (sezgisel) ve metaheuristic (ileri-sezgisel) yöntemler ortaya çıkmıştır. Bu yöntemler doğru uygulandığında optimuma çok yakın sonuçlar verebilmektedir.

Bir sonraki yazımızda bu yöntemleri ve LC Waikiki’nin Rota Planlama problemini nasıl çözdüğünü anlatmaya çalışacağım.