مقاله نحوه پیاده سازی را شرح می دهد WMS-سیستم، با نیاز به حل یک مسئله خوشه بندی غیر استاندارد و اینکه از چه الگوریتم هایی برای حل آن استفاده کردیم، مواجه شدیم. ما به شما خواهیم گفت که چگونه یک رویکرد سیستماتیک و علمی را برای حل مشکل به کار بردیم، با چه مشکلاتی مواجه شدیم و چه درس هایی آموختیم.
این نشریه مجموعه ای از مقالات را آغاز می کند که در آن تجربه موفق خود را در پیاده سازی الگوریتم های بهینه سازی در فرآیندهای انبار به اشتراک می گذاریم. هدف از مجموعه مقالات آشنایی مخاطب با انواع مسائل بهینه سازی عملیات انبار است که تقریباً در هر انبار متوسط و بزرگی به وجود می آید و همچنین بیان تجربیات خود در حل چنین مشکلاتی و مشکلاتی است که در این مسیر با آنها مواجه می شویم. . مقالات برای کسانی که در صنعت لجستیک انبار کار می کنند مفید خواهد بود WMS-سیستم ها و همچنین برنامه نویسانی که علاقه مند به کاربردهای ریاضیات در تجارت و بهینه سازی فرآیندها در یک شرکت هستند.
گلوگاه در فرآیندها
در سال 2018 پروژه ای را برای اجرا به پایان رساندیم WMS-سیستم ها در انبار شرکت "تجاری خانه "LD" در چلیابینسک. ما محصول "1C-Logistics: Warehouse Management 3" را برای 20 محل کار اجرا کردیم: اپراتورها WMS، انبارداران، رانندگان لیفتراک. میانگین انبار حدود 4 هزار متر مربع، تعداد سلول ها 2 و تعداد SKU ها 5000 عدد است. این انبار شیرهای توپی تولید خودمان را در اندازه های مختلف از 4500 کیلوگرم تا 1 کیلوگرم ذخیره می کند. موجودی در انبار به صورت دسته ای ذخیره می شود، زیرا نیاز به انتخاب کالا طبق FIFO وجود دارد.
هنگام طراحی طرح‌های اتوماسیون فرآیند انبار، با مشکل موجود ذخیره‌سازی غیربهینه موجودی مواجه بودیم. مشخصات نگهداری و انبار کردن جرثقیل ها به گونه ای است که یک سلول ذخیره سازی واحد فقط می تواند اقلامی از یک دسته داشته باشد. محصولات روزانه به انبار می رسد و هر ورود یک دسته جداگانه است. در مجموع در نتیجه 1 ماه فعالیت انبار، 30 دسته مجزا ایجاد می شود، علیرغم اینکه هر کدام باید در یک سلول جداگانه ذخیره شوند. محصولات اغلب نه در پالت های کامل، بلکه به صورت قطعه انتخاب می شوند و در نتیجه در منطقه انتخاب قطعه در بسیاری از سلول ها تصویر زیر مشاهده می شود: در سلولی با حجم بیش از 1 متر مکعب چندین قطعه جرثقیل وجود دارد که کمتر از 3-5 درصد از حجم سلول را اشغال می کند.
شکل 1. عکس چند قطعه کالا در یک سلول
واضح است که از ظرفیت ذخیره سازی به نحو مطلوب استفاده نمی شود. برای تصور مقیاس فاجعه، می توانم ارقامی را ارائه دهم: به طور متوسط، از 1 تا 3 سلول از چنین سلول هایی با حجم بیش از 100 متر مکعب با تعادل "کوچک" در طول دوره های مختلف عملیات انبار وجود دارد. از آنجایی که انبار نسبتاً کوچک است، در فصول شلوغ انبار، این عامل به یک "گلوگاه" تبدیل می شود و فرآیندهای انبار را بسیار کند می کند.
ایده حل مشکل
ایده ای مطرح شد: دسته های باقی مانده با نزدیک ترین تاریخ ها باید به یک دسته کاهش یابد، و این گونه باقیمانده ها با یک دسته یکپارچه باید به طور فشرده در یک سلول قرار گیرند، یا در چند سلول، اگر فضای کافی در یک سلول وجود نداشته باشد برای قرار دادن سلول ها. کل مقدار باقی مانده
شکل 2. طرحی برای فشرده سازی باقی مانده ها در سلول ها
این به شما امکان می دهد تا فضای اشغال شده انبار را که برای قرار دادن کالاهای جدید استفاده می شود، به میزان قابل توجهی کاهش دهید. در شرایطی که ظرفیت انبار بیش از حد بارگیری می شود، چنین اقدامی بسیار ضروری است، در غیر این صورت ممکن است فضای خالی کافی برای قرار دادن کالاهای جدید وجود نداشته باشد، که منجر به توقف فرآیندهای قرار دادن و تکمیل انبار می شود. قبلا قبل از اجرا WMS-سیستم ها این عملیات را به صورت دستی انجام دادند که بی اثر بود، زیرا روند جستجوی باقی مانده های مناسب در سلول ها بسیار طولانی بود. اکنون با معرفی سیستم WMS، تصمیم گرفتیم فرآیند را خودکار کرده، سرعت آن را افزایش داده و هوشمند کنیم.
روند حل چنین مشکلی به 2 مرحله تقسیم می شود:
- در مرحله اول ما گروه هایی از دسته ها را در تاریخ فشرده سازی نزدیک می یابیم.
- در مرحله دوم، برای هر گروه از دسته ها، فشرده ترین قرارگیری کالاهای باقی مانده در سلول ها را محاسبه می کنیم.
در مقاله حاضر به مرحله اول الگوریتم می پردازیم و پوشش مرحله دوم را برای مقاله بعدی می گذاریم.
جستجوی مدل ریاضی مسئله
قبل از اینکه بخواهیم کد بنویسیم و چرخ خود را دوباره اختراع کنیم، تصمیم گرفتیم به صورت علمی به این مسئله بپردازیم، یعنی: آن را به صورت ریاضی فرموله کنیم، آن را به یک مسئله بهینه سازی گسسته شناخته شده تقلیل دهیم و از الگوریتم های موجود موثر برای حل آن استفاده کنیم، یا از الگوریتم های موجود استفاده کنیم. به عنوان مبنا و اصلاح آنها بر اساس مشخصات مسئله عملی در حال حل.
از آنجایی که از فرمول بندی تجاری مسئله به وضوح برمی آید که ما با مجموعه ها سر و کار داریم، چنین مسئله ای را از نظر تئوری مجموعه ها فرمول بندی خواهیم کرد.
بگذار - مجموعه ای از تمام دسته های باقی مانده از یک محصول خاص در یک انبار. اجازه دهید - ثابت روزهای داده شده اجازه دهید - زیر مجموعه ای از دسته ها، که در آن تفاوت در تاریخ برای همه جفت دسته های زیر مجموعه از یک ثابت تجاوز نمی کند. . ما باید حداقل تعداد زیرمجموعه های ناهمسان را پیدا کنیم ، به طوری که تمام زیر مجموعه ها جمع آوری شده با هم بسیاری را می دهد .
به عبارت دیگر، ما باید گروه ها یا خوشه هایی از احزاب مشابه را پیدا کنیم، جایی که معیار شباهت با ثابت تعیین می شود. . این وظیفه ما را به یاد مشکل شناخته شده خوشه بندی می اندازد. مهم است که بگوییم مشکل مورد بررسی با مشکل خوشه بندی متفاوت است زیرا مشکل ما دارای یک شرط کاملاً تعریف شده برای معیار شباهت عناصر خوشه است که توسط ثابت تعیین می شود. ، اما در مشکل خوشه بندی چنین شرطی وجود ندارد. بیان مسئله خوشه بندی و اطلاعات مربوط به این مشکل را می توان یافت
بنابراین، ما موفق شدیم مسئله را فرموله کنیم و یک مسئله کلاسیک با فرمول مشابه پیدا کنیم. اکنون لازم است الگوریتم های شناخته شده ای را برای حل آن در نظر بگیریم تا چرخ را دوباره اختراع نکنیم، بلکه بهترین شیوه ها را در نظر بگیریم و آنها را به کار بگیریم. برای حل مشکل خوشه بندی، ما محبوب ترین الگوریتم ها را در نظر گرفتیم، یعنی: -به معنای -میانگین، الگوریتم شناسایی اجزای متصل، الگوریتم درخت پوشا حداقل. شرح و تجزیه و تحلیل چنین الگوریتم هایی را می توان یافت
برای حل مشکل ما، الگوریتم های خوشه بندی -یعنی و -از آنجایی که تعداد خوشه ها هرگز از قبل مشخص نیست، به هیچ وجه قابل استفاده نیستند و چنین الگوریتم هایی محدودیت روز ثابت را در نظر نمی گیرند. چنین الگوریتم‌هایی در ابتدا از بررسی کنار گذاشته شدند.
برای حل مشکل ما، الگوریتم شناسایی اجزای متصل و الگوریتم حداقل درخت پوشا مناسب تر است، اما، همانطور که مشخص شد، نمی توان آنها را "سر به سر" برای مشکل حل شده اعمال کرد و راه حل خوبی به دست آورد. برای توضیح این موضوع، اجازه دهید منطق عملکرد چنین الگوریتم هایی را در رابطه با مسئله خود در نظر بگیریم.
نمودار را در نظر بگیرید ، که در آن رئوس مجموعه احزاب هستند ، و لبه بین رئوس и وزنی برابر با اختلاف روز بین دسته ها دارد и . در الگوریتم شناسایی اجزای متصل، پارامتر ورودی مشخص شده است جایی که ، و در نمودار تمام لبه هایی که وزن آنها بیشتر است حذف می شوند . فقط نزدیکترین جفت اشیاء متصل باقی می مانند. هدف الگوریتم انتخاب چنین مقداری است ، که در آن نمودار به چندین مؤلفه متصل «تجزیه» می شود، جایی که طرف های متعلق به این مؤلفه ها معیار شباهت ما را برآورده می کنند که توسط ثابت تعیین می شود. . اجزای حاصل خوشه هستند.
الگوریتم حداقل درخت پوشا ابتدا بر روی یک نمودار ساخته می شود حداقل درخت پوشا، و سپس به طور متوالی یال هایی با بیشترین وزن را حذف می کند تا زمانی که نمودار به چندین مؤلفه متصل «از هم بپاشد»، جایی که طرف های متعلق به این مؤلفه ها نیز معیار شباهت ما را برآورده می کنند. اجزای حاصل خوشه خواهند بود.
هنگام استفاده از چنین الگوریتم هایی برای حل مسئله مورد بررسی، ممکن است وضعیتی مانند شکل 3 ایجاد شود.
شکل 3. استفاده از الگوریتم های خوشه بندی برای مسئله در حال حل
فرض کنید ثابت ما برای تفاوت بین روزهای دسته ای 20 روز است. نمودار برای سهولت درک بصری به شکل فضایی به تصویر کشیده شد. هر دو الگوریتم یک راه حل 3 خوشه ای تولید کردند که با ترکیب دسته های قرار داده شده در خوشه های جداگانه با یکدیگر به راحتی می توان آن را بهبود بخشید! بدیهی است که چنین الگوریتم هایی نیاز به اصلاح دارند تا با ویژگی های مسئله حل شده مطابقت داشته باشند و کاربرد آنها در شکل خالص آن برای حل مسئله ما نتایج ضعیفی به همراه خواهد داشت.
بنابراین، قبل از اینکه شروع به نوشتن کد برای الگوریتم‌های گراف اصلاح‌شده برای کارمان کنیم و دوچرخه خود را دوباره اختراع کنیم (که قبلاً می‌توانستیم طرح‌های چرخ‌های مربعی را تشخیص دهیم)، دوباره تصمیم گرفتیم به طور علمی به چنین مشکلی نزدیک شویم، یعنی: سعی کنید آن را به یک بهینه سازی مسئله گسسته دیگر تقلیل دهید، به این امید که الگوریتم های موجود برای حل آن را بتوان بدون تغییر اعمال کرد.
جستجوی دیگری برای مشکل کلاسیک مشابه موفقیت آمیز بوده است! ما موفق شدیم یک مسئله بهینه سازی گسسته را پیدا کنیم که فرمول آن 1 در 1 با فرمول مسئله ما منطبق است. این وظیفه معلوم شد مشکل پوشش مجموعه. اجازه دهید فرمول مسئله را در رابطه با مشخصات خود ارائه کنیم.
یک مجموعه محدود وجود دارد و خانواده از تمام زیرمجموعه های مجزای احزاب آن، به طوری که تفاوت در تاریخ برای همه جفت احزاب هر زیر مجموعه از خانواده از ثابت تجاوز نمی کند . پوشش را خانواده می گویند از کمترین قدرت، که عناصر آن متعلق به ، به گونه ای که اتحاد مجموعه ها از خانواده باید مجموعه ای از همه احزاب بدهد .
تجزیه و تحلیل دقیق این مشکل را می توان یافت и گزینه های دیگری برای کاربرد عملی مشکل پوشش و اصلاحات آن را می توان یافت
الگوریتم برای حل مسئله
ما در مورد مدل ریاضی مسئله تصمیم گرفته ایم که حل شود. حالا بیایید الگوریتم حل آن را بررسی کنیم. زیر مجموعه ها از خانواده با روش زیر می توان به راحتی پیدا کرد.
- دسته ها را از یک مجموعه مرتب کنید به ترتیب نزولی تاریخ آنها.
- حداقل و حداکثر تاریخ دسته را پیدا کنید.
- برای هر روز از حداقل تاریخ تا حداکثر، همه دسته هایی را که تاریخ آنها متفاوت است را پیدا کنید نه بیشتر از (پس ارزش بهتر است عدد زوج را بگیرید).
منطق رویه تشکیل یک خانواده از مجموعه ها در روز در شکل 4 ارائه شده است.
شکل 4. تشکیل زیر مجموعه احزاب
این روش برای همه ضروری نیست تمام دسته های دیگر را مرور کنید و تفاوت تاریخ آنها یا از مقدار فعلی را بررسی کنید به چپ یا راست حرکت کنید تا زمانی که دسته ای را پیدا کنید که تاریخ آن متفاوت است بیش از نصف مقدار ثابت است. همه عناصر بعدی، هنگام حرکت به سمت راست و چپ، برای ما جالب نخواهند بود، زیرا برای آنها تفاوت در روزها فقط افزایش می یابد، زیرا عناصر موجود در آرایه در ابتدا مرتب شده بودند. این رویکرد زمانی که تعداد مهمانی ها و گسترش تاریخ آنها به طور قابل توجهی زیاد باشد، به میزان قابل توجهی در زمان صرفه جویی می کند.
مشکل پوشش مجموعه است -difficult، یعنی الگوریتم سریع (با زمان عملیاتی برابر با چند جمله ای از داده های ورودی) و الگوریتم دقیقی برای حل آن وجود ندارد. بنابراین برای حل مشکل پوشش مجموعه، یک الگوریتم سریع حریص انتخاب شد که البته دقیق نیست، اما دارای مزایای زیر است:
- برای مسائل کوچک (و این دقیقاً مورد ما است)، راه حل هایی را محاسبه می کند که کاملاً نزدیک به بهینه هستند. همانطور که اندازه مشکل افزایش می یابد، کیفیت راه حل بدتر می شود، اما همچنان به آرامی.
- اجرای بسیار آسان؛
- سریع، زیرا تخمین زمان اجرای آن است .
الگوریتم حریص مجموعه ها را بر اساس قانون زیر انتخاب می کند: در هر مرحله، مجموعه ای انتخاب می شود که حداکثر تعداد عناصری که هنوز پوشش داده نشده اند را پوشش می دهد. شرح مفصلی از الگوریتم و شبه کد آن را می توان یافت
مقایسه دقت چنین الگوریتم حریصی در داده‌های آزمایشی مسئله در حال حل با سایر الگوریتم‌های شناخته‌شده، مانند الگوریتم احتمالی حریص، الگوریتم کلونی مورچه‌ها و غیره انجام نشده است. نتایج مقایسه چنین الگوریتم هایی بر روی داده های تصادفی تولید شده را می توان یافت
پیاده سازی و پیاده سازی الگوریتم
این الگوریتم در زبان پیاده سازی شد 1S و در یک پردازش خارجی به نام "فشرده سازی باقی مانده" گنجانده شد که به آن متصل شد WMS-سیستم. ما الگوریتم را در زبان پیاده سازی نکردیم C ++ و از یک کامپوننت Native خارجی استفاده کنید، که درست تر است، زیرا سرعت کد کمتر است ++C بارها و در برخی نمونه ها حتی ده ها برابر سریعتر از سرعت کدهای مشابه روی آن است 1S. روی زبان 1S این الگوریتم برای صرفه جویی در زمان توسعه و سهولت رفع اشکال در پایگاه تولید مشتری پیاده سازی شد. نتیجه الگوریتم در شکل 5 ارائه شده است.
شکل 5. پردازش برای "فشرده سازی" باقی مانده ها
شکل 5 نشان می دهد که در انبار مشخص شده، موجودی های جاری کالا در سلول های ذخیره سازی به خوشه هایی تقسیم می شود که در آنها تاریخ دسته های کالا با یکدیگر بیش از 30 روز تفاوت ندارند. از آنجایی که مشتری شیرهای توپی فلزی را در انبار تولید و ذخیره می کند که عمر مفید آنها بر حسب سال محاسبه می شود، می توان از چنین تفاوت تاریخی چشم پوشی کرد. توجه داشته باشید که چنین پردازشی در حال حاضر به طور سیستماتیک در تولید و اپراتورها استفاده می شود WMS کیفیت خوب خوشه بندی احزاب را تایید می کند.
نتیجه گیری و ادامه
تجربه اصلی که ما از حل چنین مسئله عملی به دست آوردیم، تأیید اثربخشی استفاده از پارادایم: ریاضی است. بیان مسأله تشک معروف مدل الگوریتم معروف الگوریتم با در نظر گرفتن ویژگی های مسئله. بهینه سازی گسسته بیش از 300 سال است که وجود داشته است و در این مدت افراد موفق شده اند مشکلات زیادی را در نظر بگیرند و تجربه زیادی در حل آنها جمع آوری کنند. اول از همه، بهتر است به این تجربه روی آورید و تنها پس از آن شروع به اختراع مجدد چرخ خود کنید.
در مقاله بعدی، داستان الگوریتم‌های بهینه‌سازی را ادامه می‌دهیم و به جالب‌ترین و بسیار پیچیده‌تر نگاه می‌کنیم: الگوریتمی برای «فشرده‌سازی» بهینه باقیمانده‌های سلول، که از داده‌های دریافتی از الگوریتم خوشه‌بندی دسته‌ای به عنوان ورودی استفاده می‌کند.
مقاله را آماده کرد
رومن شانگین، برنامه نویس بخش پروژه ها،
اولین شرکت BIT، چلیابینسک
منبع: www.habr.com