Tối ưu hóa Sơ đồ Sàn
Hình học Bố trí Kho hàng: Lưu trữ & Chuyển động
Một kho hàng là một bài toán tối ưu hóa hình học. Mỗi foot vuông là lưu trữ (giá chứa sản phẩm) hoặc chuyển động (lối đi cho người & xe nâng). Sự đánh đổi là cơ bản: lối đi rộng hơn có nghĩa là chuyển động dễ dàng hơn nhưng lưu trữ ít hơn. Lối đi hẹp hơn có nghĩa là lưu trữ nhiều hơn nhưng bạn cần thiết bị chuyên dụng (& đắt tiền).
Chiều rộng lối đi tiêu chuẩn:
- Xe nâng thông thường: 11-13 feet (xe nâng cần không gian để quay với pallet)
- Xe nâng tới: 8-10 feet (cánh tay kéo dài để tới giá)
- Lối đi cực hẹp (VNA): 5-6 feet (xe turret chuyên dụng, đắt tiền nhưng tối đa hóa lưu trữ)
Chiến lược đường đi hàng: con đường hình học mà một công nhân đi để lấy hàng:
- Mẫu S (hình rắn): Đi vào mỗi lối, đi toàn bộ chiều dài của nó, thoát ra đầu kia. Đơn giản nhưng ghé thăm mỗi lối thậm chí nếu chỉ có một hàng cần lấy ở đó.
- Khoảng trắng lớn nhất: Chỉ đi vào lối nếu nó có hàng để lấy. Bỏ qua lối không có hàng để lấy. Trong một lối, quay lại ở khoảng trắng lớn nhất giữa các hàng thay vì đi toàn bộ chiều dài.
- Cross-dock: Đối với hàng đi thẳng từ nhận hàng đến gửi hàng: bỏ qua lưu trữ hoàn toàn. Bố trí cross-dock đặt cửa nhận hàng & gửi hàng ở hai bên đối diện, với một con đường rõ ràng giữa chúng.
Tính toán Mật độ Lưu trữ
Một kho hàng rộng 200 feet & dài 400 feet (tổng cộng 80.000 foot vuông). Bố trí hiện tại sử dụng xe nâng thông thường với lối đi 12 feet. Giá là 4 feet sâu (chiều sâu pallet đơn) ở mỗi bên của mỗi lối. Bố trí xen kẽ: giá, lối, giá, lối.
Mỗi đơn vị giá-lối-giá là: 4 (giá) + 12 (lối) + 4 (giá) = 20 feet rộng.
Tận dụng Cube & Xếp Bin
Xếp chồng: Hình học 3D trong Mỗi Rơmooc
Một pallet tiêu chuẩn ở Bắc Mỹ là 48 inch x 40 inch (pallet GMA). Đây là đơn vị cơ bản của hình học logistics.
Tận dụng cube đo lường bạn lấp đầy không gian bao hiệu quả: thể tích sản phẩm thực tế chia cho thể tích khả dụng. Một rơmooc đầy theo trọng lượng nhưng nửa trống theo thể tích có tận dụng cube kém. Một rơmooc gói đến trần nhà có tận dụng cube xuất sắc.
Xếp cột: mỗi lớp giống hệt nhau, hộp trực tiếp trên đầu nhau. Yếu về kết cấu nhưng sử dụng không gian hiệu quả.
Xếp khóa (pinwheel): lớp xen kẽ xoay 90 độ. Ổn định hơn nhiều nhưng tạo khoảng trống ở các cạnh, lãng phí 5-15% của chân pallet.
Tải vào vùng chứa là thách thức hình học thực sự: xếp hộp hình chữ nhật có kích thước khác nhau vào vùng chứa vận chuyển 40 feet (kích thước bên trong xấp xỉ 39'5" x 7'8" x 7'10"). Đây là xếp bin 3D: một trong những bài toán cổ điển NP-hard trong khoa học máy tính. Không có thuật toán nào có thể đảm bảo giải pháp tối ưu trong thời gian hợp lý cho các trường hợp lớn.
Trong thực tế, các công ty logistics sử dụng các cách tiếp cận heuristic: hàng lớn trước, lấp diện tích sàn trước khi xếp chồng chiều cao, nhóm hàng theo đích đến để hiệu quả dỡ hàng.
Hiệu quả Tải Pallet
Bạn cần tải các hộp dài 12 inch, rộng 10 inch & cao 8 inch lên một pallet tiêu chuẩn 48" x 40". Chiều cao xếp chồng tối đa là 48 inch.
Tại sao Tối ưu hóa Tuyến đường Trở nên Khó
Bài toán Người Bán Hàng Du Lịch (TSP)
Giả sử bạn phải ghé thăm 10 khách hàng & quay lại kho của bạn. Con đường nào là ngắn nhất? Đây là Bài toán Người Bán Hàng Du Lịch: một trong những bài toán được nghiên cứu nhiều nhất trong toán học & khoa học máy tính.
Khó khăn là sự bùng nổ tổ hợp. Với N điểm dừng, có (N-1)!/2 tuyến đường duy nhất (chia cho 2 vì chiều kim đồng hồ & ngược chiều kim đồng hồ có cùng khoảng cách).
- 5 điểm dừng: 12 tuyến đường: kiểm tra tất cả trong vài phần nghìn giây
- 10 điểm dừng: 181.440 tuyến đường: vẫn quản lý được cho máy tính
- 15 điểm dừng: 43,6 tỷ tuyến đường: mất hàng giờ
- 20 điểm dừng: 60,8 tứ tỷ tuyến đường: mất hàng thế kỷ
- 50 điểm dừng: nhiều tuyến đường hơn nguyên tử trong vũ trụ quan sát được
TSP là NP-hard: không có thuật toán nào được biết có thể giải quyết nó trong thời gian đa thức. Khi N lớn lên, những giải pháp chính xác trở nên không thể & chúng ta phải sử dụng heuristics: những thuật toán tìm giải pháp tốt (nhưng không được đảm bảo tối ưu) một cách nhanh chóng.
Những heuristics phổ biến:
- Hàng xóm gần nhất: Từ vị trí hiện tại, luôn đi đến điểm dừng chưa được thăm gần nhất. Nhanh nhưng thường tạo ra các tuyến đường có những chỗ giao cắt xấu xí.
- Chèn bao lồi: Bắt đầu với các điểm dừng ngoài cùng (bao lồi: ranh giới hình học). Sau đó chèn các điểm trong một cách một, nơi chúng thêm khoảng cách ít nhất.
- Cải thiện 2-opt: Lấy một tuyến đường hoàn thành & thử hoán đổi các cặp cạnh. Nếu xóa hai cạnh & kết nối lại khác nhau làm cho tuyến đường ngắn hơn, giữ hoán đổi. Lặp lại cho đến khi không có cải thiện nào được tìm thấy.
Heuristics so với Giải pháp Chính xác
Một công ty giao hàng có 12 điểm dừng hôm nay. Tài xế của họ sử dụng heuristic hàng xóm gần nhất: ở mỗi điểm, lái xe đến điểm dừng chưa được thăm gần nhất.
Vùng, Mật độ & Bài toán Định Tuyến Phương tiện
Giao hàng Chân cuối: Nơi Hình học Gặp Kinh tế
Chân cuối: từ trung tâm phân phối đến cửa khách hàng: chiếm 40-50% tổng chi phí vận chuyển. Đây là phần bị ràng buộc hình học nhiều nhất của chuỗi cung ứng.
Tuyến đường hình quạt từ kho: Xe giao hàng quạt ra từ một trung tâm phân phối trung tâm. Tuyến đường của mỗi xe nên bao phủ một vùng địa lý nén chặt: không có hai xe nào nên cắt ngang lãnh thổ của nhau.
Mật độ giao hàng quyết định mọi thứ. Trong một khu vực thành phố dày đặc, một xe có thể thực hiện 150 lần giao hàng trong một ca 8 giờ. Trong các khu vực nông thôn, xe tương tự có thể quản lý 20-30. Lý do hình học: điểm dừng ở thành phố gần nhau (lái xe ngắn giữa các điểm dừng) trong khi điểm dừng ở nông thôn cách xa nhau.
Định tuyến dựa trên vùng chia khu vực phục vụ thành các cụm địa lý. Mỗi vùng được gán cho một phương tiện. Những vùng tốt nén chặt (xấp xỉ tròn hoặc vuông) & liên tục (không có khoảng trống hoặc túi cô lập). Mục tiêu: giảm thiểu tổng khoảng cách trong khi giữ mỗi tuyến đường dưới giới hạn thời gian/công suất.
Bài toán Định Tuyến Phương tiện (VRP) khái quát TSP thành nhiều phương tiện. Với kho, N khách hàng, & K xe tải (mỗi chiếc có công suất & ràng buộc thời gian), gán khách hàng cho xe tải & sắp xếp thứ tự tuyến đường của mỗi xe để giảm thiểu tổng khoảng cách. VRP cũng là NP-hard.
Một bản đồ vùng được thiết kế tốt tạo ra các tuyến đường mà con đường của mỗi tài xế tạo thành một hình dạng nén chặt về mặt hình học: một vòng tròn hoặc búp xấp xỉ kéo dài từ kho. Nếu bạn thấy một tuyến đường cắt ngang chính nó hoặc chồng lên với vùng của tài xế khác, định tuyến không hiệu quả.
Thiết kế Vùng
Một công ty giao hàng hoạt động từ một kho ở trung tâm của một thành phố. Họ có 4 tài xế & 200 lần giao hàng lan tỏa trên một khu vực phục vụ xấp xỉ hình tròn với bán kính 10 dặm.