Tiêu đề Chương 02 ✅

CHƯƠNG 2: HOẠCH ĐỊNH TUYẾN ĐƯỜNG MỤC LỤC: 1. Vấn đề định tuyến xe (VRP) 2. Phương pháp giải cho bài toán TSP đối xứng 3. Phương pháp giải cho bài toán VRP cơ bản PHẦN 1: VẤN ĐỀ ĐỊNH TUYẾN XE (VRP) 1. Định nghĩa - Vấn đề định tuyến xe VRP là một trong những thách thức tối ưu hóa phức tạp trong lĩnh vực vận hành và quản lý vận tải, phân phối và logistics. Mục tiêu của VRP là tối ưu hóa các tuyến đường cho một số lượng lớn phương tiện vận chuyển, phục vụ cho việc điều phối hàng hóa giữa các địa điểm nhận hàng, giao hàng và các điểm dừng khác nhau. - Việc lập kế hoạch để xác định nhân viên thực hiện dịch vụ, loại hàng hóa giao, số lượng cần vận chuyển và lộ trình di chuyển cụ thể không chỉ giúp tối ưu hóa hoạt động vận chuyển mà còn giảm thiểu tổng chi phí liên quan đến vận tải. 2. Ai cần giải quyết vấn đề VRP? - Các bên liên quan đến vấn đề định tuyến xe VRP bao gồm: + Chủ hàng: Bao gồm những tổ chức như nhà bán lẻ, nhà phân phối và nhà sản xuất (retailers, distributors, manufacturers). + Chủ xe: Các doanh nghiệp điều hành đội xe vận chuyển, bao gồm cả vận chuyển hàng lẻ (LTL) và vận chuyển hàng toàn bộ (FTL) (2PL). + Các công ty cung cấp dịch vụ giao nhận (3PL) 3. Các vấn đề thực tế trong vận tải - Lấy hàng/ gom hàng tại nhiều kho (Multiple Depot VRP – MDVRP) + Trong MDVRP, việc lấy và gom hàng từ nhiều kho đặt ra các ràng buộc cụ thể. Mọi phương tiện phải được tải đầy trước khi rời kho và dỡ hàng trước khi quay trở lại kho. Với chỉ hai bến tải có sẵn, tối đa chỉ có thể tải hoặc dỡ hai xe cùng một lúc. Điều này có nghĩa là một số phương tiện có thể phải chờ đợi để được tải, dẫn đến trì hoãn trong việc xuất phát từ kho. Thách thức ở đây là tìm ra các tuyến đường tối ưu cho MDVRP và đồng thời đáp ứng được các ràng buộc về tải và dỡ hàng tại kho. - Nhiều loại hàng hóa (Multi-commodity – VRP) + Đặc tính hàng hoá: Trong vận tải FTL, nguyên tắc không trộn lẫn hàng hoá là quan trọng (ví dụ: gỗ và bóng đèn, nước đóng chai và thực phẩm dễ mất nước). + Kích thước hàng hoá: Ảnh hưởng đến việc xếp dỡ, chất xếp, và trọng lượng của xe vận chuyển. - Vấn đề định tuyến xe với nhận và giao hàng (Vehicle Routing Problem with Pick-up and Delivering – VRPPD)
+ Mục tiêu: Tối ưu hóa độ dài của lộ trình. Tìm lộ trình ngắn nhất cho mỗi phương tiện là khá dễ dàng, nhưng khi có nhiều địa điểm nhận và giao hàng, việc này trở nên phức tạp hơn. + Mỗi chiếc xe nhận/giao hàng tại các địa điểm khác nhau và giao chúng ở các nơi khác nhau. Xác định lộ trình để nhận và giao tất cả hàng hóa, đồng thời giảm thiểu chiều dài của lộ trình dài nhất. - Năng lực vận tải hạn chế (The capacitated vehicle routing problem – CVRP) + Xe vận chuyển có hạn chế về khả năng cần phải nhận hoặc cung cấp hàng hóa tại các địa điểm khác nhau. Các mặt hàng có số lượng, ví dụ như trọng lượng hoặc kích thước, và các phương tiện có giới hạn về công suất mà chúng có thể chở. + Mục tiêu của việc vận chuyển hàng hóa là tối thiểu hóa chi phí, với điều kiện không bao giờ vượt quá khả năng của các phương tiện (được gọi là việc vượt quá trọng tải). - Ràng buộc khung giờ (VRP with time windows – VRPTW) + Nhiều vấn đề định tuyến xe liên quan đến việc lên lịch cho các khách hàng chỉ có sẵn trong các khung thời gian cụ thể. Mục tiêu là để giảm thiểu tổng thời gian di chuyển của các phương tiện. + Ví dụ, tại vị trí 9, Time (0,3) là một khung thời gian, có nghĩa là phương tiện phải đến đó trong khoảng thời gian từ 2 đến 3 để tuân thủ lịch trình. - Vấn đề định tuyến xe ngẫu nhiên (Stochastic VRP – SVRP) + Stochastic VRP (SVRP) hoặc Vấn đề định tuyến xe ngẫu nhiên là một dạng của vấn đề định tuyến xe (VRP) mà nhu cầu hoặc điều kiện vận chuyển của các khách hàng là ngẫu nhiên hoặc không chắc chắn. Trong SVRP, các yếu tố như thời gian giao hàng, số lượng hàng hoá cần vận chuyển, hoặc điều kiện địa hình có thể biến đổi ngẫu nhiên trong quá trình thực hiện các tuyến đường vận chuyển. + Mục tiêu của SVRP là tối ưu hóa việc sử dụng phương tiện vận chuyển và giảm thiểu tổng thời gian hoặc chi phí vận chuyển trong bối cảnh các yếu tố ngẫu nhiên. Điều này đòi hỏi sự linh hoạt trong quyết định vận chuyển và sự đánh giá đúng đắn về rủi ro và xác suất. - VRP động (Dynamic VRP) + Có một số ngành hàng thường có xuất hiện nhiều đơn đặt hàng phát sinh trong ngày, ví dụ ngành phân phối dược phẩm. Các nhà thuốc thường yêu cầu thời gian giao hàng ngắn hơn dẫn đến các vấn đề về định tuyến và lập lịch trình xe trở nên phức tạp. Ngoài ra, các nhà thuốc thường đặt hàng liên tục trong ngày, điều này có nghĩa là tại mọi thời điểm có các nhóm đơn đặt hàng khác nhau đang chờ được giao hàng. Điều này cũng ngụ ý rằng trong một ngày, một số hiệu thuốc có thể cần phải được phục vụ nhiều lần. + Vì vậy, cách tiếp cận truyền thống dựa trên các tuyến đường cố định thường không thể đáp ứng được yêu cầu linh hoạt này và có thể
không hiệu quả cho các nhà phân phối. Ngoài ra, các tuyến đường đã được lập kế hoạch thường xuyên không thể hoàn thành đầy đủ, và đôi khi xe phải rời kho hàng chỉ để giao một hoặc hai đơn đặt hàng. - Vấn đề định tuyến xe với Backhaul (Vehicle Routing Problem with Backhaul – VRPB) + Đây là một tình huống phổ biến trong quản lý vận tải, đặc biệt là trong các hệ thống phân phối hoặc logistics. Ví dụ, một công ty vận tải có thể giao hàng từ kho đến các cửa hàng, và sau đó, sau khi hoàn thành giao hàng đến các cửa hàng, xe vận chuyển cần thu thập hàng hóa trả về kho hoặc điểm xuất phát để tối ưu hóa việc sử dụng xe và giảm thiểu chi phí vận chuyển. + Trong VRPB, một số ràng buộc thường được xem xét, bao gồm: _ Ràng buộc định tuyến, _ Ràng buộc thời gian, _ Ràng buộc về công suất. PHẦN 2: PHƯƠNG PHÁP GIẢI CHO BÀI TOÁN TSP ĐỐI XỨNG - Chọn giá trị nhỏ nhất trong cột (chọn xong gạch bỏ cho đỡ nhầm) - Nhìn theo hàng ngang, tìm số nhỏ nhất tiếp theo