Optimizasyon Model ve Sezgisel Yaklaşımla Atama Problemi
Kendi lojistik deposu olan bir tekstil firmasının 100 mağazası vardır. Bu firma, mağazalarına günde 100 bin adet ürün sevk ediyor. Firmanın deposuna gelen ürünlerin akışı ve örnek bir depo yerleşimi sırasıyla Şekil 1 ve 2’de gösterilmiştir. Burada gösterilen her bir akış ayrı bir süreçtir. Kısaca süreçler hakkında bilgi verecek olursak; ürün kabul, firmanın ürettirdiği ve tedarikçi tarafından gönderilen ürünlerin firmaya ait depoya kabul edilme aşamasını gösterir. Burada ürünler, denetimden geçerek (tedarikçinin belirtilen kalite ve özelliklere göre ürünü üretip üretmediğini tespit etme), deponun boş alanlarına stoklanır. Stoklanan ürünlerden mağazalara gönderilecek olanlar belirlenir.
Bu ürünler, deponun toplanabilir alanlarına stoklanır ve buradan toplatılarak sevkiyat noktasına iletilir. Sevkiyat noktasında araçlara yüklenen ürünler, mağazalara gönderilir. Görüldüğü üzere, ürünlerin sevkiyatından önce, mağazaların günlük taleplerine göre depolardan ürün toplatma işlemi yapılıyor. Bu toplatma işleminde, işçilere bir emir listesi veriliyor ve işçiler bu listeye göre ürünleri toplayıp sevkiyat noktasına iletiyor. Bu yazı, işçilerin toplayacağı emir listelerinin işçilere atanmasını konu alıyor.
Problem Tanımı:
Bu şirketin elinde toplamda 25 emir listesi ve 5 işçi bulunuyor ve bir haftada bu işleri bitirmek istiyor. Her bir emir listesi, depo içerisinde ardıl sırada ürün toplama işlemini kapsadığı için birer tur olarak adlandırılır. Her işçinin her bir turu yapma süresi ile maliyeti farklılaşıyor. Tablo 1 ve 2’de işçilerin sırasıyla her bir iş için maliyet ve iş yapma süresi gösterilmiştir.
Ayrıca her bir işçinin haftalık çalışma kapasitesi (saat) de bellidir ve Tablo 3’te gösterilmiştir.
Şirketin temel olarak istediği şey, en düşük maliyetle tüm turları bu beş işçiye yaptıracak atamanın yapılmasıdır.
Şirketin Analitik departmanına gelen bu iş için iki türlü çözüm yaklaşımı ortaya çıkmıştır. İlk yaklaşım, bir matematiksel modelin kurulmasıyla en iyi çözümün aranmasıdır. İkinci çözüm yolu ise sezgisel algoritma tasarlayarak oluşturulan çözümdür.
Çözüm Yaklaşımı 1:
İşçi-tur ikililerinin belirlenmesi için bir atama modeli kurulmuştur. Bu modele ait kümeler ve parametreler aşağıdaki gibidir. I kümesi işçileri ve T kümesi de gerçekleştirilecek turları nitelendiriyor.
Bu modelde karar verilecek şey, hangi işçinin hangi tura atanmasıdır.
Şirketin amacı minimum maliyetle işçilere turların atanması olduğundan, modele ait amaç fonksiyonu ve kısıtlar aşağıdaki gibi tanımlanır.
İlk kısıt, bir işçinin maksimum kapasitesine göre atamasına belirtir. (2) numaralı kısıt, her işin sadece bir işçiye atanmasını garanti eder. Son kısıt ise xit’nin sadece 0 veya 1 değerini alabileceğini ifade eder.
Bu model Python PuLP kütüphanesi yardımıyla kodlanarak çözüldü. Küme ve parametrelere ilişkin kod blokları aşağıdaki gibidir.
# kütüphaneler
import pandas as pd
from pulp import *
import openpyxl# kümeler
isci=list(range(1,6))
tur=list(range(1,26))# parametreler
maliyet = pd.read_excel(r'C:/Users/xy/Desktop/veri/cap3.xlsx', sheet_name='maliyet',engine='openpyxl',index_col=0)süre = pd.read_excel(r'C:/Users/xy/Desktop/veri/cap3.xlsx', sheet_name='saat',engine='openpyxl',index_col=0)kapasite = pd.read_excel(r'C:/Users/xy/Desktop/veri/cap3.xlsx', sheet_name='kapasite',engine='openpyxl',index_col=0)
Karar değişkeni, modeli ve amaç fonksiyonunu tanımlayan kod blokları aşağıdaki gibidir.
# karar değişkeni
x=LpVariable.dicts('AtandiMi_',[(i,t) for i in isci for t in tur], cat='Binary')# model ve amaç fonksiyonu
model=LpProblem("Minimum Maliyet",LpMinimize)
model += (lpSum([x[(i,t)]*maliyet.loc[i,t] for i in isci for t in tur]))
Kısıtların bulunduğu kod bloğu da aşağıda paylaşılmıştır.
#işçinin haftalık kapasitesine göre atama yapılmalı
for i in isci:
model += (lpSum([x[(i,t)]*sure.loc[i,j] for t in tur]) <=kapasite.loc[i,'Kapasite']# her tur bir işçiye atanmalı
for t in tur:
model += (lpSum([x[(i,t)] for i in isci]))>=1
model += (lpSum([x[(i,t)] for i in isci]))<=1
Bu model çözdürülmesine ait kod bloğu aşağıda verilmiştir.
model.solve()
print("Çözülen Model : {}".format(LpStatus[model.status]))
print("Toplam Maliyet = ", value(model.objective))Bu blok sonrasında çözdürülen modelin optimal olduğu ve toplam maliyetin 438 TL olduğu bulunmuştur. Hangi işçiye hangi turun atandığı bulmak için aşağıdaki kod bloğundan yararlanılır.
var_name= []
var_value=[]
for v in model.variables():
if v.varValue>0:
var_name.append(v.name)
var_value.append(v.varValue)# sonuçlar dataframe olarak oluşturulur.
df_result=pd.DataFrame(zip(var_name,var_value), columns=['Değişken','Değer'])
df_result
Sonuçlar Tablo 4’te gösterilmiştir. Bu tabloya göre, 1 numaralı işçiye 4, 11, 12, 14, 16 ve 20 numaralı turlar atanmıştır. Bir numaralı işçinin kapasitesi 58 saat olduğu Tablo 3’ten kolayca görülür. Bu işçinin atandığı turları tamamlamak için toplamda ne kadar bir süreye ihtiyacı olduğunu hesaplayalım. Böylelikle, atamanın doğru yapılıp yapılmadığı kontrol edilecektir. Tablo 2’de her bir işçinin her bir turu tamamlama süresi verilmişti. Bu tabloya göre, 1. İşçinin 4 numaralı tur için 13, 11 için 5, 12 için 6, 14 için 14, 16 için 9 ve 20 için 8 saate ihtiyacı vardır. Toplamda 55 saate ihtiyaç var olup, 58 saatlik kapasiteyi aşmamaktadır. Diğer işçiler için de bu kontrol yapıldığında, kapasiteyi aşmayan doğru atamalar yapıldığı anlaşılacaktır.
Çözüm Yaklaşımı 2:
Birinci yaklaşımda işçi sayısı ve tamamlanacak tur sayısı arttıkça modelin çalışma ve çözüme ulaşma süresi uzamaktadır.
Özellikle NP-hard problemlerde çözüm süreleri yılları bile bulmaktadır.
Bu durumlarda, sezgisel algoritmalar veya yaklaşımlar geliştirilerek çözüme ulaşma denenir. Bu yöntemle elde edilecek çözüm sonuçları, optimum çözümü vermeyebilir ancak optimuma çok yakın sonuçlar verebilir ve hız açısından optimizasyon modellerine tercih edilir.
Sezgisel yöntemleri klasik sezgiseller ve meta sezgiseller olarak ikiye ayırabiliriz.
Bu yazıdaki problemi klasik sezgisel yöntemlerle çözmeye çalışacağız. Çözümümüze geçmeden önce birkaç cümle ile klasik ve meta sezgisellerin farkını belirtmemiz gerekirse ikisi de problem için optimale yakın çözümler bulmaya çalışır fakat klasik sezgiseller daha problem bağımlıyken meta sezgiseller problemin yapısından bağımsızdır. Diğer bir deyişle, klasik sezgiseller problemi çözmek için problemin karakteristik özelliklerinden yararlanırken meta sezgisel metodlar (benzetimli tavlama, genetik algoritma vb.) problemin yapısından bağımsızdır. Ek olarak klasik sezgiseller greedy (açgözlü) özellikleri nedeniyle local optimalarda takılabilirken meta sezgiseller bu sorunu çözmek için çeşitli metotlara başvururlar.
Klasik sezgiselleri de iki parçaya ayırabiliriz.
- “construction heuristic” (yapım-inşa sezgiseli) olarak geçen ve genellikle greedy bir mantık çerçevesinde olası ilk çözümü bulan kısımdır.
- “improvement heuristic” (iyileştirme sezgiseli) bulduğumuz bu çözümü çeşitli local search metodlarıyla (flip, 2-opt,move vb.) iyileştirmeye çalıştığımız kısımdır.
Sezgisel metotlar için bir tane doğru yöntem yoktur. Farklı yöntemler denenebilir fakat önemli olan farklı veri kümelerinde de sonuçların iyi olması ve çözüme ulaşmanın hızlı olmasıdır.
Bu problemin construction heuristic kısmı için önce bir öncelik matrisi oluşturuldu. Bu matris 5X25'lik bir matris olup her bir elemanı aşağıdaki formül ile hesaplanmıştır.
Üstteki formüle göre o iş için en küçük değere sahip olan işçiye o iş atanır. Bu şekilde tüm işler her biri sadece bir işçiye olmak üzere işçilere atanır. Bu kısmı yapan Python kod bloğu aşağıdaki gibidir.
CH= np.zeros((5,25))for i in range(5):
for j in range(25):
CH[i][j]=C[i][j]*R[i][j]/K[i]
print(CH)B= np.zeros((5,25))
for j in range (25):
A=CH[0][j]
for i in range (5):
if CH[i][j]<=A:
B[i][j]=1
A=CH[i][j]
for k in range (i+1):
if k==0:
continue
else:
B[k-1][j]=0
else:B[i][j]==0
print(B)
Bu kod bloğunda iş ve işçi eşleşmesini yapıyoruz fakat atamanın feasible olduğunu kontrol etmeden bu atamaları yaptık. Çözümü feasible yapmak için kapasite kontrolünü de sağladık. Kapasitesi aşılan işçilerin işlerini diğer işçilere kaydırma yöntemiyle sonucu feasible yapmaya çalışıyoruz. Aşağıdaki Python bloğu ile bunu gerçekleştiriyoruz ve sonucu kontrol ettiğimizde her işçiye bir iş düşen, dışarıda eşleşmemiş iş kalmayan bir ilk olası çözüm üretiyoruz ve böylece construction heuristic kısmını tamamlamış oluyoruz.
for i in range(m):
cap=0
for j in range(n):
cap=cap+R[i][j]*B[i][j]
if cap>K[i]:
if i<m-1:
B[i][j]=0
B[i+1][j]=1
cap=cap-R[i][j]
else:
B[i][j]=0
print(B)Improvement heuristic kısmında ise construction heuristicte ürettiğimiz olası ilk çözümü geliştirmeye çalışacağız. Bu kısımda izlediğimiz yol ise diğer tüm işleri sabit tutarak bir işi atandığı işçiden alarak sırayla diğer tüm işçilere atamak ve sonuç iyileşiyor ise ilk olası çözümümüzü bununla güncellemektir.
Burada yaptığımız şey aslında çözümün komşularını kontrol etmek ve daha iyi sonuç var ise onu yeni çözümümüz yapmak. Bu işlemi tüm işler için yaparak sonuçları iyileştirerek ilerlediğimiz kod bloğunu aşağıda görebilirsiniz.
for j in range(n):
Copy[:,j]=0
for i in range(m):
M=0
Count=0
P=0
Copy[i][j]=1
for a in range(m):
for b in range(n):
M = M+Copy[a][b]*C[a][b]
for t in range(m):
if sum(Copy[t][:]*R[t][:])<=K[t]:
Count=Count+1
else: Count=Count
for k in range(i):
P=P+Copy[k][j]*C[k][j]
M=M-P
if S>=M and Count==m:
S=M
Copy[:i,j]=0
else:
Copy[i][j]=0İlk olası çözümümüzün sonucu 489 idi. Improvement heuristicten sonra sonucumuzu 478 olarak iyileştirdik. Modelde bulduğumuz optimal sonuç ise 438 idi. Çok basit sezgisel yöntemler uygulayarak kısa sürede 478 sonucuna ulaşabildik. Bu da optimalden %9 uzaklıkta bir sonuç. Bu sonucu farklı yöntemler de deneyerek aradaki fark tabi ki daha da küçültülebilir.
Örneği verilen işçi-tur atamada işçi ve tur sayısı arttıkça problemin optimizasyon modeli kullanılarak çözülmesi saatler, günler, haftalar sürebilmektedir. Sürekli çevik olan bir iş ortamında bu tip problemlerin çözümü de aynı çevikle talep ediliyor. Böyle bir ortamda, çözüm için kurulan bir optimizasyon modelinin her zaman kısa sürede sonuç vermesi beklenir ancak bu bazı problemlerin yapısı gereği (np-hard) bazen mümkün değildir. Bu tip durumlarda sezgisel veya kural tabanlı yöntemlere başvurulur ve optimumdan belli bir oran feragat edilerek nihai çözüm bulunur. Böylelikle, iş hayatındaki problemlerin uygun bir çözümü bulunmuş olur.
Akın ÖĞRÜK
Bogazici University Operations Management Dep. Ph.D. & Business Analytics Specialist
Şükrü İMRE
İTÜ Management Engineering, Ph.D. & Business Analytics Specialist
