Makalede nasıl uygulanacağı açıklanıyor WMS-sistemde standart olmayan bir kümeleme problemini çözme ihtiyacı ve bunu çözmek için hangi algoritmaları kullandığımızla karşı karşıya kaldık. Sorunun çözümünde sistematik, bilimsel bir yaklaşımı nasıl uyguladığımızı, ne gibi zorluklarla karşılaştığımızı, hangi dersleri çıkardığımızı size anlatacağız.
Bu yayın, depo süreçlerinde optimizasyon algoritmalarının uygulanmasındaki başarılı deneyimimizi paylaştığımız bir dizi makalenin başlangıcıdır. Makale serisinin amacı, izleyicileri hemen hemen her orta ve büyük depoda ortaya çıkan depo operasyonlarının optimizasyon sorunları hakkında bilgilendirmek ve bu tür sorunları çözme konusundaki deneyimimizi ve bu süreçte karşılaşılan tuzakları anlatmaktır. . Makaleler depo lojistiği sektöründe çalışanlara faydalı olacak, uygulayacak WMS-sistemlerin yanı sıra matematiğin iş dünyasındaki uygulamaları ve bir kuruluştaki süreçlerin optimizasyonu ile ilgilenen programcılar.
Süreçlerde darboğaz
2018 yılında hayata geçirmek üzere bir proje tamamladık. WMS-Chelyabinsk'teki “Trading House “LD” şirketinin deposundaki sistemler. “1C-Logistics: Depo Yönetimi 3” ürününü 20 işyerinde (operatörler) hayata geçirdik. WMS, mağaza sahipleri, forklift sürücüleri. Ortalama depo alanı yaklaşık 4 bin m2, hücre sayısı 5000 ve SKU sayısı 4500'dür. Depoda 1 kg'dan 400 kg'a kadar farklı boyutlarda kendi imalatımız olan küresel vanalar depolanmaktadır. Malların FIFO'ya göre seçilmesi gerektiğinden depodaki envanter partiler halinde depolanır.
Depo süreç otomasyon şemalarını tasarlarken, mevcut optimal olmayan envanter depolama sorunuyla karşı karşıya kaldık. Depolama ve istifleme vinçlerinin özellikleri, bir birim depolama hücresinin yalnızca bir partiden ürünleri içerebileceği şekildedir. Ürünler depoya günlük olarak gelir ve her varış ayrı bir partidir. Toplamda 1 aylık depo operasyonu sonucunda her birinin ayrı bir hücrede depolanması gerekmesine rağmen 30 ayrı parti oluşturuluyor. Ürünler genellikle tüm paletler halinde değil, parçalar halinde seçilir ve sonuç olarak, birçok hücredeki parça seçim bölgesinde aşağıdaki resim gözlenir: hacmi 1 m3'ten fazla olan bir hücrede, birkaç adet vinç vardır. Hücre hacminin %5-10'undan daha azını kaplar.
Şekil 1. Bir hücredeki birkaç parça ürünün fotoğrafı
Depolama kapasitesinin en iyi şekilde kullanılmadığı açıktır. Felaketin ölçeğini hayal etmek için rakamlar verebilirim: ortalama olarak, deponun farklı operasyon dönemlerinde "küçük" bakiyelerle 1 m3'ten fazla hacme sahip bu tür hücrelerin 100 ila 300 hücresi vardır. Depo nispeten küçük olduğundan, deponun yoğun olduğu sezonlarda bu faktör bir "darboğaz" haline gelir ve depo süreçlerini büyük ölçüde yavaşlatır.
Sorun çözüm fikri
Bir fikir ortaya çıktı: en yakın tarihlere sahip kalan partiler tek bir partiye indirilmeli ve birleşik bir partiye sahip olan bu tür artıklar, bir hücrede veya bir hücrede yeterli alan yoksa birkaç hücrede kompakt bir şekilde birlikte yerleştirilmelidir. kalan miktarın tamamı.
İncir. 2. Hücrelerdeki kalıntıları sıkıştırmak için şema
Bu, yeni malların yerleştirilmesi için kullanılacak olan depo alanını önemli ölçüde azaltmanıza olanak tanır. Depo kapasitesinin aşırı yüklendiği bir durumda, böyle bir önlem son derece gereklidir, aksi takdirde yeni malları yerleştirmek için yeterli boş alan olmayabilir, bu da depo yerleştirme ve yenileme süreçlerinin durmasına yol açacaktır. Daha önce uygulamadan önce WMS-sistemler bu işlemi manuel olarak gerçekleştirdi ancak hücrelerde uygun kalıntıları arama süreci oldukça uzun olduğundan etkisiz kaldı. Artık WMS sisteminin kullanıma sunulmasıyla süreci otomatikleştirmeye, hızlandırmaya ve akıllı hale getirmeye karar verdik.
Böyle bir sorunu çözme süreci 2 aşamaya ayrılır:
- ilk aşamada, sıkıştırma tarihi yakın olan parti gruplarını buluyoruz;
- ikinci aşamada, her parti grubu için kalan malların hücrelere en kompakt şekilde yerleştirilmesini hesaplıyoruz.
Bu yazıda algoritmanın ilk aşamasına odaklanacağız ve ikinci aşamayı bir sonraki makaleye bırakacağız.
Sorunun matematiksel modelini arayın
Kod yazmaya ve tekerleğimizi yeniden icat etmeye başlamadan önce, bu soruna bilimsel olarak yaklaşmaya karar verdik: onu matematiksel olarak formüle edin, onu iyi bilinen bir ayrık optimizasyon problemine indirgeyin ve çözmek için mevcut etkili algoritmaları kullanın veya bu mevcut algoritmaları kullanın. temel olarak alın ve bunları çözülmekte olan pratik problemin özelliklerine göre değiştirin.
Kümelerle uğraştığımız problemin iş formülasyonundan açıkça çıktığı için, böyle bir problemi küme teorisi açısından formüle edeceğiz.
Let – bir depodaki belirli bir ürünün geri kalan kısmının tüm partilerinden oluşan set. İzin vermek – günlerin sabiti verilmiştir. İzin vermek - alt kümedeki tüm parti çiftleri için tarih farkının sabit bir değeri aşmadığı bir parti alt kümesi . Minimum ayrık alt küme sayısını bulmamız gerekiyor öyle ki tüm alt kümeler birlikte ele alındığında çok şey verirdi .
Başka bir deyişle, benzerlik kriterinin sabit tarafından belirlendiği benzer partilerin gruplarını veya kümelerini bulmamız gerekiyor. . Bu görev bize iyi bilinen kümeleme problemini hatırlatıyor. Söz konusu problemin, kümeleme probleminden farklı olduğunu söylemek önemlidir; çünkü problemimiz, sabit tarafından belirlenen, küme elemanlarının benzerliği kriteri için kesin olarak tanımlanmış bir koşula sahiptir. ancak kümeleme probleminde böyle bir durum yoktur. Kümeleme sorununun açıklaması ve bu soruna ilişkin bilgiler burada bulunabilir.
Böylece problemi formüle etmeyi ve benzer formülasyona sahip klasik bir problem bulmayı başardık. Artık tekerleği yeniden icat etmek için değil, en iyi uygulamaları alıp uygulamak için sorunu çözmek için iyi bilinen algoritmaları dikkate almak gerekiyor. Kümeleme problemini çözmek için en popüler algoritmaları göz önünde bulundurduk: -araç, -bağlı bileşenleri tanımlama algoritması, minimum yayılan ağaç algoritması anlamına gelir. Bu tür algoritmaların bir açıklaması ve analizi bulunabilir.
Sorunumuzu çözmek için kümeleme algoritmaları -anlamına gelir ve -küme sayısı hiçbir zaman önceden bilinmediğinden araçlar hiçbir şekilde uygulanamaz ve bu tür algoritmalar sabit gün kısıtlamasını hesaba katmaz. Bu tür algoritmalar başlangıçta değerlendirme dışı bırakıldı.
Sorunumuzu çözmek için, bağlı bileşenleri belirlemeye yönelik algoritma ve minimum yayılan ağaç algoritması daha uygundur, ancak bunların çözülmekte olan soruna "birdenbire" uygulanamayacağı ve iyi bir çözüm elde edilemeyeceği ortaya çıktı. Bunu açıklamak için bu tür algoritmaların çalışma mantığını problemimize göre ele alalım.
Grafiği göz önünde bulundurun burada köşeler taraflar kümesidir ve köşeler arasındaki kenar и partiler arasındaki gün farkına eşit bir ağırlığa sahiptir и . Bağlı bileşenleri tanımlamaya yönelik algoritmada giriş parametresi belirtilir Nerede ve grafikte ağırlığın daha büyük olduğu tüm kenarlar kaldırılır . Yalnızca en yakın nesne çiftleri bağlı kalır. Algoritmanın amacı böyle bir değeri seçmektir grafiğin birkaç bağlantılı bileşene "ayrıldığı", bu bileşenlere ait tarafların sabit tarafından belirlenen benzerlik kriterimizi karşılayacağı . Ortaya çıkan bileşenler kümelerdir.
Minimum yayılan ağaç algoritması ilk olarak bir grafik üzerine kuruludur minimum yayılan ağaç ve ardından grafik birkaç bağlantılı bileşene "ayrılana" kadar en yüksek ağırlığa sahip kenarları sırayla kaldırır; burada bu bileşenlere ait taraflar da benzerlik kriterimizi karşılayacaktır. Ortaya çıkan bileşenler kümeler olacaktır.
Söz konusu problemi çözmek için bu tür algoritmalar kullanıldığında, Şekil 3'teki gibi bir durum ortaya çıkabilir.
Şekil 3. Kümeleme algoritmalarının çözülmekte olan probleme uygulanması
Toplu iş günleri arasındaki farka ilişkin sabitimizin 20 gün olduğunu varsayalım. Grafik Görsel algı kolaylığı açısından mekansal formda tasvir edilmiştir. Her iki algoritma da ayrı kümelere yerleştirilen partilerin birbiriyle birleştirilmesiyle kolayca geliştirilebilecek 3 kümeli bir çözüm üretti! Bu tür algoritmaların çözülmekte olan problemin özelliklerine uyacak şekilde değiştirilmesi gerektiği açıktır ve bunların saf haliyle problemimizin çözümüne uygulanması kötü sonuçlar verecektir.
Dolayısıyla, görevimiz için değiştirilmiş grafik algoritmaları için kod yazmaya ve kendi bisikletimizi (siluetlerinde zaten kare tekerleklerin ana hatlarını görebildiğimiz) yeniden keşfetmeye başlamadan önce, böyle bir soruna yine bilimsel olarak yaklaşmaya karar verdik: Bunu çözmek için mevcut algoritmaların değişiklik yapılmadan uygulanabileceği umuduyla, onu başka bir ayrık problem optimizasyonuna indirgemeye çalışın.
Benzer bir klasik problem için yapılan başka bir araştırma da başarılı oldu! Formülasyonu problemimizin formülasyonuyla 1'e 1 örtüşen ayrı bir optimizasyon problemi bulmayı başardık. Bu görev ortaya çıktı set kaplama problemi. Sorunun formülasyonunu spesifikasyonlarımıza göre sunalım.
Sonlu bir küme var ve aile her bir alt kümenin tüm taraf çiftleri için tarihlerdeki fark olacak şekilde, tüm ayrık taraf alt kümelerinin aileden sabitleri aşmaz . Bir örtüye aile denir unsurları ait olan en az güçten öyle ki kümelerin birleşimi aileden tüm tarafların setini vermeli .
Bu sorunun ayrıntılı bir analizini burada bulabilirsiniz. и Kaplama probleminin pratik uygulaması ve modifikasyonları için diğer seçenekler bulunabilir.
Sorunu çözmek için algoritma
Çözülecek problemin matematiksel modeline karar verdik. Şimdi bunu çözmek için algoritmaya bakalım. Alt kümeler aileden aşağıdaki prosedürle kolayca bulunabilir.
- Grupları bir setten düzenleyin tarihlerine göre azalan sırada.
- Minimum ve maksimum parti tarihlerini bulun.
- Her gün için minimum tarihten maksimuma kadar tarihleri farklı olan tüm partileri bulun den fazla değil (yani değer Çift sayıyı almak daha iyidir).
Bir küme ailesi oluşturma prosedürünün mantığı at gün sayısı Şekil 4'te gösterilmektedir.
Şekil 4. Partilerin alt kümelerinin oluşumu
Bu prosedür herkes için gerekli değildir diğer tüm partileri gözden geçirin ve tarihlerindeki veya mevcut değerdeki farkı kontrol edin tarihi farklı olan bir parti bulana kadar sola veya sağa hareket edin sabitin değerinin yarısından fazlası. Hem sağa hem de sola hareket ederken sonraki tüm öğeler bizim için ilginç olmayacak, çünkü dizideki öğeler başlangıçta sıralandığı için onlar için gün farkı yalnızca artacaktır. Bu yaklaşım, parti sayısı ve tarihlerinin dağılımı önemli ölçüde fazla olduğunda önemli ölçüde zaman tasarrufu sağlayacaktır.
Küme kaplama problemi -zor, yani çözmek için hızlı (giriş verilerinin polinomuna eşit çalışma süresiyle) ve doğru bir algoritma olmadığı anlamına gelir. Bu nedenle, küme kapsama problemini çözmek için, elbette doğru olmayan ancak aşağıdaki avantajlara sahip olan hızlı açgözlü bir algoritma seçildi:
- Küçük boyutlu problemler için (ki bizim durumumuz da tam olarak budur) optimuma oldukça yakın çözümler hesaplar. Sorunun boyutu arttıkça çözümün kalitesi bozulur, ancak yine de oldukça yavaş bir şekilde;
- Uygulaması çok kolay;
- Hızlı, çünkü çalışma süresi tahmini .
Açgözlü algoritma, kümeleri aşağıdaki kurala göre seçer: her aşamada, henüz kapsanmayan maksimum sayıda öğeyi kapsayan bir küme seçilir. Algoritmanın ve sözde kodunun ayrıntılı bir açıklaması burada bulunabilir.
Böyle bir açgözlü algoritmanın çözülmekte olan problemin test verileri üzerindeki doğruluğunun olasılıksal açgözlü algoritma, karınca kolonisi algoritması vb. gibi bilinen diğer algoritmalarla karşılaştırılması yapılmamıştır. Bu tür algoritmaları oluşturulan rastgele verilerle karşılaştırmanın sonuçları bulunabilir.
Algoritmanın uygulanması ve uygulanması
Bu algoritma dilde uygulandı 1S ve "Kalıntı Sıkıştırma" adı verilen harici bir işleme dahil edildi. WMS-sistem. Algoritmayı dilde uygulamadık C ++ ve kodun hızı daha düşük olduğundan onu harici bir Yerel bileşenden kullanın; bu daha doğru olur C + + kez ve bazı örneklerde benzer kodun hızından onlarca kat daha hızlıdır. 1S. Dil üzerinde 1S Algoritma, geliştirme süresinden tasarruf etmek ve müşterinin üretim üssünde hata ayıklamayı kolaylaştırmak için uygulandı. Algoritmanın sonucu Şekil 5'te sunulmaktadır.
Şekil 5. Kalıntıları “sıkıştırmak” için işleme
Şekil 5, belirtilen depoda, depolama hücrelerindeki mevcut mal bakiyelerinin, mal partilerinin tarihlerinin birbirinden en fazla 30 gün farklı olmadığı kümelere bölündüğünü göstermektedir. Müşteri, raf ömrü yıllarla hesaplanan metal küresel vanaları depoda üretip sakladığından bu tür bir tarih farkı ihmal edilebilir. Bu tür işlemlerin şu anda üretimde sistematik olarak kullanıldığını ve operatörlerin WMS Parti kümelenmesinin kalitesinin teyit edilmesi.
Sonuçlar ve devam
Böyle pratik bir problemi çözerek edindiğimiz temel deneyim, matematik paradigmasını kullanmanın etkililiğinin doğrulanmasıdır. Sorun bildirimi ünlü mat. modeli ünlü algoritma Sorunun özelliklerini dikkate alan algoritma. Ayrık optimizasyon 300 yılı aşkın bir süredir var ve bu süre zarfında insanlar birçok sorunu dikkate almayı ve bunları çözme konusunda çok fazla deneyim biriktirmeyi başardılar. Her şeyden önce, bu deneyime yönelmeniz ve ancak o zaman tekerleğinizi yeniden icat etmeye başlamanız daha tavsiye edilir.
Bir sonraki makalede, optimizasyon algoritmaları hakkındaki hikayeye devam edeceğiz ve en ilginç ve çok daha karmaşık olana bakacağız: toplu kümeleme algoritmasından alınan verileri girdi olarak kullanan, hücrelerdeki artıkları en iyi şekilde "sıkıştırmak" için bir algoritma.
Makaleyi hazırladım
Roman Shangin, proje departmanı programcısı,
İlk BIT şirketi Chelyabinsk
Kaynak: habr.com