Məqalədə necə həyata keçiriləcəyi təsvir olunur WMS-sistem, biz qeyri-standart klaster problemini həll etmək ehtiyacı ilə qarşılaşdıq və onu həll etmək üçün hansı alqoritmlərdən istifadə etdik. Problemin həllinə sistemli, elmi yanaşmanı necə tətbiq etdiyimizi, hansı çətinliklərlə qarşılaşdığımızı və hansı dərsləri öyrəndiyimizi sizə xəbər verəcəyik.
Bu nəşr anbar proseslərində optimallaşdırma alqoritmlərinin tətbiqi üzrə uğurlu təcrübəmizi paylaşdığımız bir sıra məqalələrə başlayır. Məqalələr silsiləsinin məqsədi auditoriyanı demək olar ki, hər hansı bir orta və böyük anbarda yaranan anbar əməliyyatlarının optimallaşdırılması problemlərinin növləri ilə tanış etmək, eləcə də bu cür problemlərin həllində təcrübəmizdən və bu yolda rast gəlinən tələlərdən danışmaqdır. . Məqalələr anbar logistika sənayesində işləyənlər üçün faydalı olacaq, həyata keçirir WMS-sistemlər, o cümlədən riyaziyyatın biznesdə tətbiqi və müəssisədə proseslərin optimallaşdırılması ilə maraqlanan proqramçılar.
Proseslərdə darboğaz
2018-ci ildə həyata keçirmək üçün bir layihəni tamamladıq WMS-Çelyabinskdəki "LD Ticarət Evi" şirkətinin anbarında sistemlər. Biz 1 iş yeri üçün “3C-Logistics: Anbar İdarəetmə 20” məhsulunu tətbiq etdik: operatorlar WMS, anbardarlar, forklift sürücüləri. Orta anbar təxminən 4 min m2, hücrələrin sayı 5000 və SKU sayı 4500-dür. Anbarda 1 kq-dan 400 kq-a qədər müxtəlif ölçülü öz istehsalımız olan kürə klapanları saxlanılır. Anbardakı inventar partiyalarda saxlanılır, çünki FIFO-ya uyğun olaraq malların seçilməsinə ehtiyac var.
Anbar proseslərinin avtomatlaşdırılması sxemlərini tərtib edərkən biz inventarların qeyri-optimal saxlanması ilə bağlı mövcud problemlə qarşılaşdıq. Kranların saxlanması və yığılmasının xüsusiyyətləri elədir ki, bir vahid saxlama kamerasında yalnız bir partiyadan olan əşyalar ola bilər. Məhsullar anbara gündəlik gəlir və hər gəliş ayrı partiyadır. Ümumilikdə, 1 aylıq anbar istismarı nəticəsində hər birinin ayrıca kamerada saxlanmasına baxmayaraq, 30 ayrı partiya yaradılır. Məhsullar çox vaxt bütöv paletlərdə deyil, parçalarla seçilir və nəticədə bir çox hüceyrədə parça seçim zonasında aşağıdakı şəkil müşahidə olunur: həcmi 1 m3-dən çox olan bir hücrədə bir neçə kran parçası var. hüceyrə həcminin 5-10%-dən azını tutur.
Şək 1. Hüceyrədəki bir neçə mal parçasının şəkli
Aydındır ki, saxlama qabiliyyəti optimal şəkildə istifadə edilmir. Fəlakətin miqyasını təsəvvür etmək üçün rəqəmlər verə bilərəm: orta hesabla, anbarın fəaliyyətinin müxtəlif dövrlərində həcmi 1 m3-dən çox olan "kiçik" balanslı belə hüceyrələrin 100-dən 300-ə qədər hüceyrəsi var. Anbar nisbətən kiçik olduğundan, anbarın məşğul olduğu mövsümlərdə bu amil “darboğaz”a çevrilir və anbar proseslərini xeyli ləngidir.
Problemin həlli ideyası
Fikir yarandı: ən yaxın tarixləri olan qalıqların partiyaları bir partiyaya endirilməli və vahid partiya ilə belə qalıqlar kompakt şəkildə bir kamerada və ya bir kamerada kifayət qədər yer yoxdursa, bir neçə yerə yerləşdirilməlidir. qalıqların bütün miqdarı.
Şəkil 2. Hüceyrələrdə qalıqların sıxılması sxemi
Bu, yerləşdirilən yeni mallar üçün istifadə ediləcək işğal edilmiş anbar sahəsini əhəmiyyətli dərəcədə azaltmağa imkan verir. Anbar tutumunun həddindən artıq yükləndiyi bir vəziyyətdə belə bir tədbir son dərəcə zəruridir, əks halda yeni malların yerləşdirilməsi üçün kifayət qədər boş yer olmaya bilər ki, bu da anbarın yerləşdirilməsi və doldurulması proseslərinin dayanmasına səbəb olacaqdır. Əvvəllər həyata keçirilməzdən əvvəl WMS-sistemlər bu əməliyyatı əl ilə yerinə yetirirdilər, bu da səmərəsiz idi, çünki hüceyrələrdə uyğun qalıqların axtarışı prosesi kifayət qədər uzun idi. İndi WMS sisteminin tətbiqi ilə biz prosesi avtomatlaşdırmaq, sürətləndirmək və ağıllı etmək qərarına gəldik.
Belə bir problemin həlli prosesi 2 mərhələyə bölünür:
- birinci mərhələdə sıxılma tarixinə yaxın olan qrup qruplarını tapırıq;
- ikinci mərhələdə, hər bir partiya qrupu üçün hüceyrələrdə qalan malların ən yığcam yerləşdirilməsini hesablayırıq.
Hazırkı məqalədə alqoritmin birinci mərhələsinə diqqət yetirəcəyik və ikinci mərhələnin əhatə dairəsini növbəti məqaləyə buraxacağıq.
Problemin riyazi modelini axtarın
Kod yazmaq və çarxımızı yenidən ixtira etmək üçün əyləşməzdən əvvəl biz bu problemə elmi yanaşmaq qərarına gəldik, yəni: onu riyazi şəkildə formalaşdırmaq, onu tanınmış diskret optimallaşdırma probleminə endirmək və həll etmək üçün effektiv mövcud alqoritmlərdən istifadə etmək və ya bu mövcud alqoritmləri götürmək. əsas kimi və onları həll olunan praktiki problemin xüsusiyyətlərinə uyğunlaşdırın.
Çoxluqlarla məşğul olduğumuz problemin işgüzar formalaşdırılmasından aydın şəkildə nəticələndiyi üçün biz belə bir problemi çoxluq nəzəriyyəsi baxımından tərtib edəcəyik.
Qoy – anbarda müəyyən bir məhsulun qalan hissəsinin bütün partiyalarının dəsti. Qoy – günlərin sabiti verilmişdir. Qoy – alt dəstədəki bütün partiya cütləri üçün tarixlərdəki fərq sabitdən çox olmayan partiyaların alt çoxluğu . Biz ayrılmış alt çoxluqların minimum sayını tapmalıyıq , belə ki, bütün alt çoxluqlar birlikdə alınsa çox şey verəcək .
Başqa sözlə desək, oxşarlıq meyarının sabitlə müəyyən edildiyi oxşar tərəflərin qruplarını və ya qruplarını tapmalıyıq. . Bu tapşırıq bizə məlum klasterləşmə problemini xatırladır. Qeyd etmək lazımdır ki, baxılan problem klasterləşmə problemindən onunla fərqlənir ki, problemimiz sabitlə müəyyən edilən klaster elementlərinin oxşarlıq meyarı üçün ciddi şəkildə müəyyən edilmiş şərtə malikdir. , lakin klasterləşmə problemində belə bir şərt yoxdur. Klasterləşmə probleminin ifadəsi və bu problem haqqında məlumat əldə etmək olar
Beləliklə, biz problemi formalaşdıra bildik və oxşar tənzimləmə ilə klassik problem tapdıq. İndi təkəri yenidən ixtira etmək deyil, ən yaxşı təcrübələri götürmək və tətbiq etmək üçün onu həll etmək üçün məşhur alqoritmləri nəzərdən keçirmək lazımdır. Klasterləşmə problemini həll etmək üçün ən populyar alqoritmləri nəzərdən keçirdik, yəni: - deməkdir -vasitələr, əlaqəli komponentləri müəyyən etmək üçün alqoritm, minimum əhatə edən ağac alqoritmi. Belə alqoritmlərin təsviri və təhlili tapıla bilər
Problemimizi həll etmək üçün alqoritmlərin klasterləşdirilməsi - deməkdir və -vasitələr ümumiyyətlə tətbiq edilmir, çünki klasterlərin sayı əvvəlcədən bilinmir və belə alqoritmlər sabit gün məhdudiyyətini nəzərə almır. Bu cür alqoritmlər əvvəlcə nəzərdən keçirilmədi.
Problemimizi həll etmək üçün əlaqəli komponentləri müəyyən etmək üçün alqoritm və minimum əhatəli ağac alqoritmi daha uyğundur, lakin məlum oldu ki, onları həll olunan problemə "baş-üstə" tətbiq etmək və yaxşı bir həll əldə etmək mümkün deyil. Bunu izah etmək üçün problemimizlə bağlı belə alqoritmlərin işləmə məntiqini nəzərdən keçirək.
Qrafiki nəzərdən keçirin , burada təpələri tərəflər çoxluğudur , və təpələr arasındakı kənar и partiyalar arasında gün fərqinə bərabər çəkiyə malikdir и . Bağlı komponentləri müəyyən etmək üçün alqoritmdə giriş parametri göstərilir Hara , və qrafikdə çəkisi daha böyük olan bütün kənarlar çıxarılır . Yalnız ən yaxın obyekt cütləri bağlı qalır. Alqoritmin məqsədi belə bir dəyəri seçməkdir , burada qrafik bir neçə əlaqəli komponentə "parçalanır", burada bu komponentlərə aid olan tərəflər sabitlə müəyyən edilmiş oxşarlıq meyarımıza cavab verir. . Nəticə komponentlər klasterlərdir.
Minimum əhatə edən ağac alqoritmi əvvəlcə qrafik üzərində qurulur minimum yayılan ağac və sonra qrafik bir neçə əlaqəli komponentə "dağılana qədər" ən yüksək çəkiyə malik kənarları ardıcıl olaraq silir, burada bu komponentlərə aid olan tərəflər də bizim oxşarlıq meyarımıza cavab verəcəkdir. Nəticə komponentlər klasterlər olacaqdır.
Baxılan problemi həll etmək üçün belə alqoritmlərdən istifadə edərkən Şəkil 3-də olduğu kimi vəziyyət yarana bilər.
Şək 3. Həll olunan məsələyə klasterləşdirmə alqoritmlərinin tətbiqi
Deyək ki, toplu günləri arasındakı fərq üçün sabitimiz 20 gündür. Qrafik vizual qavrayış asanlığı üçün məkan formasında təsvir edilmişdir. Hər iki alqoritm ayrı-ayrı qruplara yerləşdirilən partiyaları bir-biri ilə birləşdirərək asanlıqla təkmilləşdirilə bilən 3-klaster həlli istehsal etdi! Aydındır ki, belə alqoritmlər həll olunan məsələnin xüsusiyyətlərinə uyğun olaraq dəyişdirilməlidir və onların xalis formada məsələmizin həllinə tətbiqi zəif nəticələr verəcəkdir.
Beləliklə, tapşırığımız üçün dəyişdirilmiş qrafik alqoritmləri üçün kod yazmağa və öz velosipedimizi yenidən ixtira etməyə başlamazdan əvvəl (siluetlərində kvadrat təkərlərin konturlarını ayırd edə bildik), biz yenə də belə bir problemə elmi yanaşmaq qərarına gəldik, yəni: həlli üçün mövcud alqoritmlərin heç bir dəyişiklik edilmədən tətbiq oluna biləcəyi ümidi ilə onu başqa bir diskret problemin optimallaşdırılmasına endirməyə çalışın.
Bənzər bir klassik problem üçün başqa bir axtarış uğurlu oldu! Biz diskret optimallaşdırma problemi tapmağa müvəffəq olduq, onun tərtibi problemimizin tərtibi ilə 1-də 1 üst-üstə düşür. Bu vəzifə ortaya çıxdı örtük problemi. Spesifikasiyamızla əlaqədar olaraq problemin tərtibini təqdim edək.
Sonlu bir çoxluq var və ailə onun bütün ayrı-ayrı tərəflər alt çoxluqlarının, belə ki, hər bir alt dəstənin bütün tərəf cütləri üçün tarixlərdəki fərq ailədən sabitləri keçmir . Bir örtüyə ailə deyilir elementləri aid olan ən az gücdən , belə ki, çoxluqlar birliyi ailədən bütün tərəflərin dəstini verməlidir .
Bu problemin ətraflı təhlilini tapa bilərsiniz и Örtmə probleminin praktik tətbiqi və onun modifikasiyaları üçün digər variantları tapmaq olar
Problemin həlli alqoritmi
Həll ediləcək məsələnin riyazi modelinə qərar verdik. İndi isə onun həlli alqoritminə baxaq. Alt çoxluqlar ailədən aşağıdakı prosedurla asanlıqla tapıla bilər.
- Bir dəstdən partiyaları təşkil edin tarixlərinin azalma ardıcıllığı ilə.
- Minimum və maksimum toplu tarixləri tapın.
- Hər gün üçün minimum tarixdən maksimuma qədər tarixləri fərqli olan bütün partiyaları tapın -dən çox deyil (dəyər Cüt ədədi götürmək daha yaxşıdır).
Dəstlər ailəsinin formalaşdırılması prosedurunun məntiqi da günlər Şəkil 4-də təqdim olunur.
Şəkil 4. Partiyaların alt qruplarının formalaşması
Bu prosedur hər kəs üçün lazım deyil bütün digər partiyalardan keçin və tarixlərindəki fərqi yoxlayın və ya cari dəyərdən tarixi fərqli olan partiya tapana qədər sola və ya sağa hərəkət edin sabitin dəyərinin yarıdan çoxu ilə. Bütün sonrakı elementlər, həm sağa, həm də sola hərəkət edərkən, bizim üçün maraqlı olmayacaq, çünki massivdəki elementlər əvvəlcə sifariş edildiyi üçün onlar üçün gün fərqi yalnız artacaq. Bu yanaşma partiyaların sayı və onların tarixlərinin yayılması əhəmiyyətli dərəcədə böyük olduqda vaxta əhəmiyyətli dərəcədə qənaət edəcəkdir.
Set örtüyü problemidir -çətin, yəni sürətli (giriş məlumatlarının polinomuna bərabər işləmə vaxtı ilə) və onun həlli üçün dəqiq alqoritm yoxdur. Buna görə də, əhatə dairəsi problemini həll etmək üçün sürətli acgöz alqoritm seçilmişdir, bu, əlbəttə ki, dəqiq deyil, lakin aşağıdakı üstünlüklərə malikdir:
- Kiçik ölçülü problemlər üçün (və bu, bizim vəziyyətimizdir) optimala olduqca yaxın olan həlləri hesablayır. Problemin ölçüsü artdıqca, həllin keyfiyyəti pisləşir, lakin hələ də kifayət qədər yavaş;
- Tətbiq etmək çox asandır;
- Sürətli, çünki onun işləmə müddəti təxminidir .
Acgöz alqoritm aşağıdakı qaydaya əsasən dəstləri seçir: hər mərhələdə hələ əhatə olunmayan elementlərin maksimum sayını əhatə edən çoxluq seçilir. Alqoritmin və onun psevdokodunun ətraflı təsviri tapıla bilər
Həll olunan məsələnin test məlumatlarında belə bir acgöz alqoritmin dəqiqliyinin digər məlum alqoritmlərlə, məsələn, ehtimal tamah alqoritmi, qarışqa koloniyası alqoritmi və s. ilə müqayisəsi aparılmamışdır. Yaradılmış təsadüfi verilənlər üzərində belə alqoritmlərin müqayisəsinin nəticələrinə rast gəlmək olar
Alqoritmin icrası və icrası
Bu alqoritm dildə həyata keçirilmişdir 1S və bağlı olan "Qalıq sıxılma" adlı xarici emal daxil edilmişdir WMS-sistem. Dildə alqoritmi həyata keçirməmişik C ++ və kodun sürəti aşağı olduğu üçün onu xarici Native komponentdən istifadə edin, bu daha düzgün olardı C + + dəfə və bəzi nümunələrdə oxşar kodun sürətindən hətta onlarla dəfə daha sürətli 1S. Dildə 1S Alqoritm müştərinin istehsal bazasında işlənmə vaxtına qənaət və sazlama asanlığı üçün həyata keçirilmişdir. Alqoritmin nəticəsi Şəkil 5-də təqdim olunur.
Şəkil 5. Qalıqların "sıxılması" üçün emal
Şəkil 5-də göstərilir ki, göstərilən anbarda saxlama kameralarında malların cari qalıqları qruplara bölünür, onların daxilində mal partiyalarının tarixləri bir-birindən 30 gündən çox olmayan fərqlə fərqlənir. Müştəri anbarda saxlama müddəti illərlə hesablanan metal top klapanları istehsal edib saxladığından, belə bir tarix fərqinə laqeyd yanaşmaq olar. Qeyd edək ki, bu cür emal hazırda istehsalatda və operatorlarda sistemli şəkildə istifadə olunur WMS partiya qruplaşmasının yaxşı keyfiyyətini təsdiqləyin.
Nəticələr və davamı
Belə bir praktiki problemin həllindən əldə etdiyimiz əsas təcrübə paradiqmadan istifadənin effektivliyinin təsdiqidir: riyaziyyat. problem bəyanat məşhur döşək. model məşhur alqoritm problemin spesifikasını nəzərə alan alqoritm. Diskret optimallaşdırma 300 ildən çoxdur ki, mövcuddur və bu müddət ərzində insanlar bir çox problemi nəzərdən keçirməyə və onların həllində çoxlu təcrübə toplamağa nail olublar. İlk növbədə, bu təcrübəyə müraciət etmək daha məqsədəuyğundur və yalnız bundan sonra təkərinizi yenidən kəşf etməyə başlayın.
Növbəti məqalədə optimallaşdırma alqoritmləri haqqında hekayəni davam etdirəcəyik və ən maraqlı və daha mürəkkəbinə baxacağıq: toplu klaster alqoritmindən alınan məlumatları giriş kimi istifadə edən hüceyrə qalıqlarının optimal "sıxılması" alqoritmi.
Məqaləni hazırladı
Roman Şangin, layihələr şöbəsinin proqramçısı,
İlk BIT şirkəti, Çelyabinsk
Mənbə: www.habr.com