🥇Toán rời rạc trong việc triển khai hệ thống WMS: Phân nhóm nhiều hàng hóa trong kho

Bài viết mô tả cách thực hiện WMS-system, chúng tôi phải đối mặt với nhu cầu giải quyết một vấn đề phân cụm không chuẩn và chúng tôi đã sử dụng thuật toán nào để giải quyết vấn đề đó. Chúng tôi sẽ cho bạn biết chúng tôi đã áp dụng cách tiếp cận khoa học, có hệ thống như thế nào để giải quyết vấn đề, những khó khăn chúng tôi gặp phải và những bài học chúng tôi rút ra.

Ấn phẩm này bắt đầu một loạt bài viết trong đó chúng tôi chia sẻ kinh nghiệm thành công của mình trong việc triển khai các thuật toán tối ưu hóa trong quy trình kho hàng. Mục đích của loạt bài viết là giúp khán giả làm quen với các loại vấn đề tối ưu hóa hoạt động kho hàng phát sinh ở hầu hết các nhà kho vừa và lớn, cũng như kể về kinh nghiệm của chúng tôi trong việc giải quyết các vấn đề đó và những cạm bẫy gặp phải trong quá trình thực hiện. . Bài viết sẽ hữu ích cho những ai làm trong ngành logistics kho bãi, thực hiện WMS-systems, cũng như các lập trình viên quan tâm đến việc ứng dụng toán học vào kinh doanh và tối ưu hóa các quy trình trong doanh nghiệp.

Điểm nghẽn trong quy trình

Năm 2018, chúng tôi đã hoàn thành dự án triển khai WMS-hệ thống tại nhà kho của công ty “Nhà giao dịch “LD” ở Chelyabinsk. Chúng tôi đã triển khai sản phẩm “1C-Logistics: Quản lý kho 3” cho 20 nơi làm việc: nhân viên vận hành WMSthủ kho, tài xế xe nâng. Kho trung bình khoảng 4 nghìn m2, số lượng ô là 5000 và số lượng SKU là 4500. Kho chứa các loại van bi do chúng tôi tự sản xuất với nhiều kích cỡ khác nhau từ 1 kg đến 400 kg. Hàng tồn kho trong kho được lưu trữ theo lô, do đó cần phải lựa chọn hàng hóa theo FIFO.

Khi thiết kế các chương trình tự động hóa quy trình kho hàng, chúng tôi phải đối mặt với vấn đề hiện tại là lưu trữ hàng tồn kho không tối ưu. Đặc điểm cụ thể của việc lưu trữ và xếp dỡ cần cẩu là một ô lưu trữ đơn vị chỉ có thể chứa các mặt hàng của một lô. Sản phẩm về kho hàng ngày và mỗi lần về là một lô riêng biệt. Tổng cộng, sau 1 tháng vận hành kho, 30 lô riêng biệt đã được tạo ra, mặc dù thực tế là mỗi lô phải được lưu trữ trong một ô riêng biệt. Các sản phẩm thường được chọn không phải theo toàn bộ pallet mà theo từng mảnh, và kết quả là trong vùng chọn mảnh ở nhiều ô, người ta quan sát được hình ảnh sau: trong một ô có thể tích lớn hơn 1 m3 có một số mảnh cần cẩu. chiếm ít hơn 5-10% thể tích tế bào.

Hình 1. Hình ảnh một số hàng hóa trong một ô

Rõ ràng là dung lượng lưu trữ chưa được sử dụng một cách tối ưu. Để hình dung quy mô của thảm họa, tôi có thể đưa ra số liệu: trung bình có từ 1 đến 3 ô như vậy với thể tích hơn 100 m300 với số dư “rất nhỏ” trong các giai đoạn hoạt động khác nhau của nhà kho. Vì kho tương đối nhỏ nên trong những mùa kho đông đúc, yếu tố này trở thành “nút cổ chai” và làm chậm đáng kể quy trình kho.

Ý tưởng giải quyết vấn đề

Một ý tưởng nảy sinh: những lô hàng còn sót lại có ngày gần nhất nên được giảm xuống còn một lô duy nhất, và những lô hàng còn sót lại với một lô thống nhất nên được đặt gọn gàng cùng nhau trong một ô hoặc thành nhiều ô, nếu không có đủ chỗ trong một ô để chứa. toàn bộ số tiền còn sót lại.

Hình 2. Sơ đồ nén cặn trong tế bào

Điều này cho phép bạn giảm đáng kể không gian kho bị chiếm dụng sẽ được sử dụng để đặt hàng hóa mới. Trong tình huống sức chứa kho quá tải, biện pháp như vậy là vô cùng cần thiết, nếu không có thể không có đủ không gian trống để chứa hàng mới, điều này sẽ dẫn đến việc dừng lại quá trình bố trí và bổ sung kho. Trước khi thực hiện WMS-systems thực hiện thao tác này một cách thủ công nhưng không hiệu quả vì quá trình tìm kiếm dư lượng phù hợp trong tế bào khá dài. Giờ đây, với sự ra đời của hệ thống WMS, chúng tôi quyết định tự động hóa quy trình, tăng tốc và làm cho quy trình trở nên thông minh hơn.

Quá trình giải quyết vấn đề như vậy được chia thành 2 giai đoạn:

ở giai đoạn đầu tiên, chúng tôi tìm thấy các nhóm lô đã đến hạn để nén;
ở giai đoạn thứ hai, đối với mỗi nhóm lô, chúng tôi tính toán vị trí nhỏ gọn nhất của hàng hóa còn lại trong các ô.

Trong bài viết hiện tại, chúng tôi sẽ tập trung vào giai đoạn đầu tiên của thuật toán và đề cập đến giai đoạn thứ hai cho bài viết tiếp theo.

Tìm kiếm mô hình toán học của bài toán

Trước khi bắt đầu viết mã và phát minh lại bánh xe của mình, chúng tôi đã quyết định tiếp cận vấn đề này một cách khoa học, cụ thể là: xây dựng nó về mặt toán học, biến nó thành một vấn đề tối ưu hóa rời rạc phổ biến và sử dụng các thuật toán hiệu quả hiện có để giải quyết nó hoặc sử dụng các thuật toán hiện có này làm cơ sở và sửa đổi chúng cho phù hợp với đặc thù của vấn đề thực tế đang được giải quyết.

Vì nó rõ ràng xuất phát từ việc hình thành vấn đề kinh doanh mà chúng ta đang giải quyết với các tập hợp, nên chúng ta sẽ hình thành một vấn đề như vậy dưới dạng lý thuyết tập hợp.

Hãy – tập hợp tất cả các lô còn lại của một sản phẩm nhất định trong kho. Cho phép - cho trước hằng số ngày. Cho phép – một tập hợp con của các lô, trong đó chênh lệch về ngày tháng của tất cả các cặp lô trong tập hợp con không vượt quá một hằng số . Chúng ta cần tìm số lượng tập hợp con rời rạc tối thiểu , sao cho tất cả các tập con gộp lại sẽ cho nhiều .

Nói cách khác, chúng ta cần tìm các nhóm hoặc cụm gồm các bên tương tự nhau, trong đó tiêu chí về sự tương đồng được xác định bởi hằng số . Nhiệm vụ này nhắc nhở chúng ta về vấn đề phân cụm nổi tiếng. Điều quan trọng cần phải nói là bài toán đang xem xét khác với bài toán phân cụm ở chỗ bài toán của chúng ta có một điều kiện được xác định chặt chẽ cho tiêu chí về độ tương tự của các phần tử cụm, được xác định bởi hằng số , nhưng trong bài toán phân cụm không có điều kiện như vậy. Tuyên bố về vấn đề phân cụm và thông tin về vấn đề này có thể được tìm thấy đây.

Vì vậy, chúng tôi đã cố gắng hình thành bài toán và tìm ra một bài toán cổ điển với cách thức tương tự. Bây giờ cần phải xem xét các thuật toán nổi tiếng để giải quyết nó, để không phát minh lại bánh xe mà áp dụng các phương pháp hay nhất và áp dụng chúng. Để giải quyết vấn đề phân cụm, chúng tôi đã xem xét các thuật toán phổ biến nhất, cụ thể là: -có nghĩa -means, thuật toán xác định các thành phần liên thông, thuật toán cây khung nhỏ nhất. Một mô tả và phân tích các thuật toán như vậy có thể được tìm thấy đây.

Để giải quyết vấn đề của chúng tôi, các thuật toán phân cụm -có nghĩa là và - phương tiện hoàn toàn không được áp dụng vì số lượng cụm không bao giờ được biết trước và các thuật toán như vậy không tính đến ràng buộc ngày không đổi. Các thuật toán như vậy ban đầu đã bị loại bỏ khỏi quá trình xem xét.
Để giải quyết vấn đề của chúng tôi, thuật toán xác định các thành phần liên thông và thuật toán cây bao trùm tối thiểu phù hợp hơn, nhưng hóa ra, chúng không thể được áp dụng “trực tiếp” cho vấn đề đang được giải và thu được giải pháp tốt. Để giải thích điều này, chúng ta hãy xem xét logic hoạt động của các thuật toán như vậy liên quan đến vấn đề của chúng ta.

Hãy xem xét biểu đồ , trong đó các đỉnh là tập hợp các bên , và cạnh giữa các đỉnh и có trọng lượng bằng chênh lệch số ngày giữa các lô и . Trong thuật toán xác định các thành phần kết nối, tham số đầu vào được chỉ định Đâu , và trong biểu đồ tất cả các cạnh có trọng số lớn hơn sẽ bị loại bỏ . Chỉ những cặp đối tượng gần nhất vẫn được kết nối. Mục đích của thuật toán là chọn một giá trị như vậy , trong đó đồ thị “phân tách” thành nhiều thành phần liên thông, trong đó các bên thuộc các thành phần này sẽ thỏa mãn tiêu chí về độ tương tự của chúng tôi, được xác định bởi hằng số . Các thành phần kết quả là các cụm.

Thuật toán cây bao trùm tối thiểu trước tiên được xây dựng trên biểu đồ cây bao trùm tối thiểu, sau đó loại bỏ tuần tự các cạnh có trọng số cao nhất cho đến khi đồ thị “tách rời” thành một số thành phần được kết nối, trong đó các bên thuộc các thành phần này cũng sẽ đáp ứng tiêu chí tương tự của chúng tôi. Các thành phần kết quả sẽ là cụm.

Khi sử dụng các thuật toán như vậy để giải bài toán đang xét có thể xảy ra tình huống như trong Hình 3.

Hình 3. Ứng dụng thuật toán phân cụm vào bài toán đang giải

Giả sử hằng số của chúng tôi về chênh lệch giữa các ngày trong đợt là 20 ngày. đồ thị được mô tả dưới dạng không gian để dễ nhận biết bằng hình ảnh. Cả hai thuật toán đều tạo ra giải pháp 3 cụm, có thể dễ dàng cải thiện bằng cách kết hợp các lô được đặt trong các cụm riêng biệt với nhau! Rõ ràng là các thuật toán như vậy cần phải được sửa đổi để phù hợp với đặc thù của vấn đề đang được giải quyết và việc áp dụng chúng ở dạng thuần túy để giải quyết vấn đề của chúng ta sẽ cho kết quả kém.

Vì vậy, trước khi bắt đầu viết mã cho các thuật toán đồ thị được sửa đổi cho nhiệm vụ của mình và phát minh lại chiếc xe đạp của riêng mình (trong hình bóng mà chúng tôi đã có thể phân biệt được đường viền của bánh xe vuông), một lần nữa, chúng tôi quyết định tiếp cận vấn đề như vậy một cách khoa học, cụ thể là: cố gắng giảm nó thành một sự tối ưu hóa vấn đề riêng biệt khác, với hy vọng rằng các thuật toán hiện có để giải quyết nó có thể được áp dụng mà không cần sửa đổi.

Một cuộc tìm kiếm khác cho một bài toán cổ điển tương tự đã thành công! Chúng tôi đã tìm ra được một bài toán tối ưu hóa rời rạc, công thức của nó trùng khớp 1 trong 1 với công thức của bài toán của chúng tôi. Nhiệm vụ này hóa ra là đặt vấn đề bao gồm. Hãy để chúng tôi trình bày công thức của vấn đề liên quan đến chi tiết cụ thể của chúng tôi.

Có một tập hữu hạn và gia đình của tất cả các tập hợp con rời rạc của các bên, sao cho sự khác biệt về ngày tháng của tất cả các cặp bên của mỗi tập hợp con từ gia đình không vượt quá hằng số . Một lớp phủ được gọi là một gia đình có quyền lực thấp nhất, các yếu tố thuộc về , sao cho hợp của các tập hợp từ gia đình nên đưa ra tập hợp của tất cả các bên .

Một phân tích chi tiết về vấn đề này có thể được tìm thấy đây и đây. Có thể tìm thấy các lựa chọn khác cho ứng dụng thực tế của bài toán che phủ và các sửa đổi của nó đây.

Thuật toán để giải quyết vấn đề

Chúng tôi đã quyết định mô hình toán học của vấn đề cần giải quyết. Bây giờ chúng ta hãy xem thuật toán để giải quyết nó. Tập hợp con từ gia đình có thể dễ dàng tìm thấy bằng thủ tục sau.

Sắp xếp các lô từ một bộ theo thứ tự giảm dần của ngày của họ.
Tìm ngày lô tối thiểu và tối đa.
Cho mỗi ngày từ ngày tối thiểu đến ngày tối đa, tìm tất cả các lô có ngày khác với không nhiều hơn (do đó giá trị Tốt hơn nên lấy số chẵn).

Logic của thủ tục hình thành một họ các tập hợp khi ngày được trình bày trong Hình 4.

Hình 4. Hình thành các tập hợp con của các bên

Thủ tục này không cần thiết đối với tất cả mọi người xem qua tất cả các lô khác và kiểm tra sự khác biệt về ngày tháng của chúng hoặc so với giá trị hiện tại di chuyển sang trái hoặc phải cho đến khi bạn tìm thấy một lô có ngày khác với hơn một nửa giá trị của hằng số. Tất cả các phần tử tiếp theo, khi di chuyển sang phải và sang trái, sẽ không gây hứng thú cho chúng ta, vì đối với chúng, sự khác biệt về số ngày sẽ chỉ tăng lên, vì ban đầu các phần tử trong mảng đã được sắp xếp. Cách tiếp cận này sẽ tiết kiệm đáng kể thời gian khi số lượng các bên và số lượng ngày hẹn hò của họ lớn đáng kể.

Bài toán bao phủ tập hợp là -khó, nghĩa là không có thuật toán nhanh (với thời gian thực hiện bằng đa thức của dữ liệu đầu vào) và thuật toán chính xác để giải nó. Vì vậy, để giải bài toán bao phủ tập hợp, một thuật toán tham lam nhanh đã được chọn, thuật toán này tất nhiên không chính xác nhưng có những ưu điểm sau:

Đối với các bài toán có quy mô nhỏ (và đây chính xác là trường hợp của chúng tôi), nó tính toán các giải pháp khá gần với mức tối ưu. Khi quy mô của vấn đề tăng lên, chất lượng của giải pháp sẽ giảm đi, nhưng vẫn khá chậm;
Rất dễ thực hiện;
Nhanh chóng, vì ước tính thời gian chạy của nó là .

Thuật toán tham lam chọn các tập hợp dựa trên quy tắc sau: ở mỗi giai đoạn, một tập hợp được chọn bao gồm số phần tử tối đa chưa được đề cập. Có thể tìm thấy mô tả chi tiết về thuật toán và mã giả của nó đây.

Việc so sánh độ chính xác của thuật toán tham lam như vậy trên dữ liệu thử nghiệm của bài toán đang được giải với các thuật toán đã biết khác, chẳng hạn như thuật toán tham lam xác suất, thuật toán đàn kiến, v.v., vẫn chưa được thực hiện. Kết quả so sánh các thuật toán như vậy trên dữ liệu ngẫu nhiên được tạo ra có thể được tìm thấy tại nơi làm việc.

Triển khai và thực hiện thuật toán

Thuật toán này được thực hiện bằng ngôn ngữ 1S và được đưa vào quá trình xử lý bên ngoài gọi là "Nén dư" được kết nối với WMS-hệ thống. Chúng tôi đã không triển khai thuật toán bằng ngôn ngữ C ++ và sử dụng nó từ một thành phần gốc bên ngoài, điều này sẽ chính xác hơn vì tốc độ mã thấp hơn C + + lần và trong một số ví dụ thậm chí còn nhanh hơn hàng chục lần so với tốc độ của mã tương tự trên 1S. Trên lưỡi 1S Thuật toán được triển khai để tiết kiệm thời gian phát triển và dễ dàng gỡ lỗi tại cơ sở sản xuất của khách hàng. Kết quả của thuật toán được trình bày trong Hình 5.

Hình.5. Xử lý để “nén” cặn

Hình 5 cho thấy trong kho quy định, số dư hàng hóa hiện tại trong các ô lưu trữ được chia thành các cụm, trong đó ngày của các lô hàng cách nhau không quá 30 ngày. Vì khách hàng sản xuất và lưu trữ van bi kim loại trong kho có thời hạn sử dụng được tính bằng năm nên có thể bỏ qua sự khác biệt về ngày tháng như vậy. Lưu ý rằng quá trình xử lý như vậy hiện đang được sử dụng một cách có hệ thống trong sản xuất và người vận hành WMS khẳng định chất lượng tốt của việc phân cụm đảng.

Kết luận và tiếp tục

Kinh nghiệm chính mà chúng tôi thu được từ việc giải một bài toán thực tế như vậy là sự xác nhận tính hiệu quả của việc sử dụng mô hình: toán học. báo cáo vấn đề chiếu nổi tiếng. người mẫu thuật toán nổi tiếng thuật toán có tính đến các chi tiết cụ thể của vấn đề. Tối ưu hóa rời rạc đã tồn tại hơn 300 năm và trong thời gian này con người đã cố gắng xem xét rất nhiều vấn đề và tích lũy nhiều kinh nghiệm trong việc giải quyết chúng. Trước hết, tốt hơn hết bạn nên chuyển sang trải nghiệm này và chỉ sau đó mới bắt đầu phát minh lại bánh xe của mình.

Trong bài viết tiếp theo, chúng ta sẽ tiếp tục câu chuyện về các thuật toán tối ưu hóa và xem xét điều thú vị nhất và phức tạp hơn nhiều: một thuật toán để “nén” tối ưu các phần còn lại của tế bào, sử dụng dữ liệu nhận được từ thuật toán phân cụm hàng loạt làm đầu vào.

Đã chuẩn bị bài viết
Roman Shangin, lập trình viên phòng dự án,
Công ty BIT đầu tiên, Chelyabinsk

Nguồn: www.habr.com