Trang chủ » Ứng dụng » Ứng dụng

Vận trù học và bài toán giao sữa

Thứ bảy - 04/07/2015 02:17 - Đã xem: 2981
Vận trù học và bài toán giao sữa

Vận trù học và bài toán giao sữa

Vấn đề hoạch định tuyến xe (Vehicle Routing Problem – hay gọi tắt là VRP) có lẽ là một trong những bài toán kinh điển nhất của Vận trù học. Bài toán được phát biểu một cách đơn giản như sau: tại một kho hàng chúng ta có một tập hợp M xe giống nhau phải giao hàng cho N khách hàng, mỗi khách hàng yêu cầu một lượng hàng nhất định. Yêu cầu của bài toán là tìm đường đi ngắn nhất cho M xe sao cho tất cả khách hàng đều được phục vụ.
Bài toán VRP là một bài toán khó. Để minh họa cho độ phức tạp của nó chúng ta hãy cùng xét một trường hợp đơn giản hơn khi chỉ có 1 xe (M = 1), lúc đó bài toán được gọi là bài toán người đưa thư (Traveling Salesman Problem – TSP). Để giải chính xác TSP, một cách dễ thấy nhất là đếm tất cả các đường đi có thể và chọn đường đi ngắn nhất. Với N khách hàng, chúng ta có (N-1)! đường đi. Giả sử máy tính chúng ta đang sử dụng có thể tính được MỘT TRIỆU đường đi trong một giây, thì với N = 10 chúng ta mất chưa đầy nửa giây để tìm ra kết quả, N = 11 mất 4 giây, N = 12 mất 40 giây, N = 15 mất khoảng một ngày, và N = 20 chúng ta mất hơn MỘT TRIỆU NĂM!

Các vấn đề hoạch định tuyến xe trong thực tế còn phức tạp hơn bài toán VRP cơ bản rất nhiều. Ví dụ sau đây là một vấn đề thực tế của Vinamilk được tìm thấy trong luận văn Thạc sĩ có tên “Thuật giải Large Neighborhood Search và Simulated Annealing cho một biến thể thực tế của bài toán Vehicle Routing” của Đặng Thị Thanh Nguyên dưới sự hướng dẫn của Tiến sĩ Đinh Bá Tiến trường đại học Quốc gia TP. HCM:

“Đề tài này tập trung nghiên cứu và giải quyết một bài toán VRP thực tế: bài toán giao hàng lạnh trong thành phố của công ty Cổ phần sữa Việt Nam (Vinamilk), cơ sở TP.HCM. Hiện nay, Vinamilk thực hiện việc điều phối xe giao hàng bằng tay với quy trình như sau: mỗi ngày, công ty sẽ nhận các đơn đặt hàng của khách hàng (số lượng đơn hàng từ vài trăm đến dưới hai ngàn), đến cuối ngày, nhân viên điều phối sẽ tổng hợp lại toàn bộ các đơn đặt hàng đã nhận trong ngày, và bộ phận điều phối thường phải mất khoảng 6 đến 8 tiếng (đôi khi phải thức cả đêm) để thực hiện việc phân bổ đơn hàng lên xe và xác định đường đi cho các xe vào ngày hôm sau. Cách làm này tốn rất nhiều thời gian và công sức mà đôi khi lời giải thu được lại chưa hẳn tốt. Do đó, vấn đề tự động hóa trong khâu điều phối xe là một nhu cầu rất cần thiết.

Bài toán giao hàng của công ty Cổ phần sữa Việt Nam Vinamilk, 
cơ sở TP.HCM là một biến thể thực tế (kết hợp của nhiều biến thể) của bài toán VRP. Ngoài các ràng buộc thường thấy trong các bài toán VRP lý thuyết, bài toán này còn có một số ràng buộc rất đặc trưng, xuất phát từ yêu cầu của thực tế. Một số khái niệm và đặc trưng của bài toán: Trạm xuất phát (home depot) và các kho hàng(depot) : Vào đầu ngày, tất cả các xe của công ty đều khởi hành từ một trạm xuất phát duy nhất (Xí Nghiệp Kho Vận Vinamilk – TP.HCM) và quay trở lại trạm xuất phát này sau khi đã giao hết số hàng được phân. Trong quá trình đi, xe sẽ đến các kho hàng để lấy hàng đem đi giao cho các khách hàng. Hiện nay, Vinamilk TP.HCM có 2 kho hàng: - Kho thứ nhất: Kho Trường Thọ (TRF) và kho Thống Nhất (TNF) – Quận Thủ Đức (2 kho này có vị trí rất gần nhau nên có thể xem như 1 kho duy nhất) - Kho thứ hai: Kho Sài Gòn (SGF) – Quận 12 Các kho hàng này chỉ mở cửa cho xe lấy hàng trong khoảng thời gian từ 6:30 đến 15:00. Do ràng buộc về kích thước mặt bằng của kho, tại cùng một thời điểm, chỉ có tối đa 3 xe một kho cùng một lúc. Các loại mặt hàng lạnh của Vinamilk bao gồm hai nhóm: - Nhóm kem – gồm các sản phẩm kem các loại. - Nhóm sữa chua - gồm các sản phẩm: sữa chua các loại, fromage, provi. Các xe chở hàng lạnh đều yêu cầu phải có máy lạnh, nhưng nhóm kem yêu cầu nhiệt độ thấp hơn nhóm sữa chua và mặt hàng khác. Do đó, xe chở được kem thì cũng có thể chở được các mặt hàng thuộc nhóm sữa chua, nhưng điều ngược lại thì không đúng. Đội xe lạnh của Vinamilk TP.HCM hiện nay gồm 23 chiếc (thuộc tổ xe Lạnh Phố), với sức chứa và khả năng chở khác nhau. Trong đó, có 11 xe có thể chở được cả kem và sữa chua. Các xe còn lại chỉ có thể chở sữa chua. Tại một thời điểm, mỗi xe chỉ có thể chở một nhóm mặt hàng. Ở đây, chi phí vận chuyển của các xe được xem là như nhau (mặc dù sức chứa khác nhau)...”

Bài toán giao sữa của Vinamilk rất phức tạp. Số lượng khách hàng lớn tới gần hai ngàn (Lưu ý rằng các thuật toán chính xác tốt nhất hiện nay cũng chỉ có thể giải bài toán VRP cơ bản với vài trăm khách hàng). Ngoài ra, bài toán còn có thêm nhiều ràng buộc khác như: các xe trong đội xe không giống nhau (heterogeneous fleet), đa sản phẩm (multi-product) và các ràng buộc về thời gian (time constraints and time windows) ...

Phải nói rằng đây là một đề tài nghiên cứu “tròn trịa”, “khá đẹp” và có tính ứng dụng cao. Đề tài xứng đáng làm luận văn Tiến sĩ chứ không chỉ dừng lại ở Thạc sĩ. Một điều đáng tiếc là không thấy các tác giả công bố kết quả nghiên cứu trên các tạp chí quốc tế chuyên ngành về Vận trù học. Nhưng qua đây cũng cho chúng ta thấy, các doanh nghiệp, tổ chức ở Việt Nam đã bắt đầu quan tâm tới các vấn đề về Vận trù học, tối ưu để giảm chi phí, tăng chất lượng dịch vụ, hiệu quả hoạt động, lợi nhuận cũng như khả năng cạnh tranh. 

Tác giả bài viết: Hà Minh Hoàng

Tổng số điểm của bài viết là: 10 trong 2 đánh giá
Click để đánh giá bài viết

Những tin mới hơn

Những tin cũ hơn

 

Thăm dò ý kiến

Bạn từng phải giải quyết các bài toán tối ưu của vận trù học trong thực tế?

Rất nhiều lần

Thỉnh thoảng

Chưa bao giờ

Tôi không biết VTH là gì.

Thông tin học bổng