Chương 1 - BÀI TOÁN LỘ TRÌNH VẬN TẢI (VRP) Bài toán VPR là bài toán về việc vận chuyển hàng hóa từ kho chứa hàng đến khách hàng bằng một đoàn xe vận tải. Rất nhiều vấn đề trong cuộc sống có thể quy về bài toán này, ví dụ như đưa thư, phân phối gas đến các đại lý, phân phối hàng hóa đến các siêu thị, xe buýt đưa đón nhân viên… Nói chung, giải quyết bài toán VRP tức là phải tìm ra tuyến đường tốt nhất để phục vụ tất cả khách hàng sử dụng một đoàn xe nhất định. Ngoài việc đảm bảo tất cả mọi khách hàng được phục vụ, lời giải bài toán còn phải chú ý đến nhiều vấn đề ràng buộc như: trọng tải của xe, thời gian làm việc của lái xe và tối thiểu hóa chi phí vận chuyển. Bài toán VRP có thể đưa về dạng một bài toán quy hoạch tuyến tính, định nghĩa bằng một hàm mục tiêu và một tập các ràng buộc.
Những đặc trưng cơ bản của bài toán VRP Cũng giống như những bài toán quy hoạch tuyến tính những đặc trưng cơ bản của bài toán VRP là hàm mục tiêu, các ràng buộc và các phương án. Mục tiêu của bài toán là tìm ra lời giải thích hợp nhất. Trong thực tế, mục tiêu của bài toán VRP có thể rất phức tạp và đôi khi mâu thuẫn lẫn nhau. Mục tiêu chung nhất là tối thiểu hóa chi phí vận chuyển.
Mục tiêu này được biểu diễn như là một hàm của khoảng cách hay thời gian vận chuyển, chi phí này phụ thuộc vào chi phí cho việc vận hành xe và cho tài xế do đó nói chung cần phải tối thiểu số lượng xe. Một số mục tiêu khác có thể tính đến như là hiệu quả của xe, tính bằng tỷ lệ sử dụng của trọng tải xe (tỷ lệ càng cao thì hiệu quả sử dụng xe càng cao). Bên cạnh đó, cũng có thể có những hàm mục tiêu phức tạp hơn liên quan đến những ràng Trang 12 buộc mà nếu vi phạm phải trả một cái giá nào đó, ví dụ như xe đến chậm làm khách hàng phải chờ, khi đó, một khoản phí đền bù phải trả tùy theo hợp đồng. Trong những bài toán thực tế, có thể phải tính đến chi phí phụ thuộc vào loại đường đi: ví dụ như đi trong thành phố tốn thời gian và chi phí hơn so với đường cao tốc.
Hàm mục tiêu là một hàm số bao gồm những biến tự do (biến quyết định), được quyết định bởi người lập kế hoạch: ví dụ như biến biểu diễn đoạn đường giữa hai khách hàng có trong lộ trình hay không, và biến phụ thuộc là kết quả của các quyết định trong quá trình tính toán. Lời giải của bài toán được biểu diễn dựa trên tập các biến quyết định cho đánh giá tốt nhất của hàm mục tiêu. Trong trường hợp của bài toán VRP, quyết định được đưa ra là thứ tự đưa hàng tới khách hàng, tức là tập các tuyến đường. Một tuyến đường bắt đầu từ kho chứa hàng và là một dãy có thứ tự của ghé thăm các khác hàng và thực hiện yêu cầu của họ.
Một phương án phải thỏa mãn tính khả thi tức là không vi phạm các ràng buộc như ràng buộc về số lượng hàng không được vượt quá trọng tải xe. Để tìm giá trị của các biến quyết định, chúng ta cần một mô hình tín toán cho bài toán. Mô hình này được xây dựng dựa trên các ràng buộc biểu diễn mối quan hệ giữa các biến tự do và biến phụ thuộc và tập hợp các giá trị có thể nhận của các biến. Với bài toán VRP, mô hình này gồm có các thành phần chính như: hệ thống đường mô tả sự liên kết giữa các khách hàng và các kho chứa; tập xe vận tải và các khách hàng người đưa ra yêu cầu và nhận hàng.
Mạng lưới đường đi Mạng lưới đường được biểu diễn như là một đồ thị với các kho và các khách hàng là các đỉnh, và các cạnh biểu diễn khoảng cách (theo thời gian, không gian hoặc cả hai) giữa các đỉnh. Mô hình mạng lưới đường đi này có thể xây dựng dựa trên một bản đồ thực tế của khu vực chứa các kho và khách hàng. Một thuật toán tìm đường đi ngắn nhất có thể được sử dụng để tìm tất cả các đường đi ngắn nhất giữa các cặp đỉnh (theo thời gian hoặc không gian), dựa trên đó xây dựng ma trận Trang 13 khoảng cách. Tùy theo cách xây dựng khoảng cách giữa các đỉnh chúng ta có thể phát triển nhiều dạng khác nhau của bài toán VRP.
Ví dụ như khi chi phí đi lại giữa các đỉnh thay đổi theo thời gian (đặc điểm phổ biến trong các thành phố như Hà Nội) ta có dạng bài toán VRP với chi phí phụ thuộc thời gian (TDVRP). Các xe vận tải Các xe vận tải và các đặc tính của chúng được thể hiện trong các ràng buộc của mô hình bài toán. Đội xe này có thể là đồng nhất nếu tất cả xe là giống nhau về tính chất. Tuy nhiên trên thực tế hầu hết đặc tính của các xe là khác nhau do đó các xe vận nói chung là không đồng nhất.
Ngoài các đặc tính quan trọng về trọng tải, giá vận chuyển, các đặc tính về máy móc như: chiều cao, khối lượng, chiều rộng, số trục… đều có thể được tính đến như là các ràng buộc cho xe. Ví dụ như xe tải có tải trọng lớn không thể đi vào thành phố vào giờ cao điểm. Ngoài ra cũng có thể có những phụ kiện trên xe dùng để tháo dỡ hàng cho những loại hàng đặc biệt theo yêu cầu của khách hàng. Tải trọng của xe có thể được biểu diễn theo tùy theo loại hàng hóa được vận chuyển (ví dụ như lít với xăng dầu, kilogram hoặc mét khối).
Các khách hàng Khách hàng là trung tâm của bài toán VRP. Một phương án chấp nhận được của bất kỳ dạng nào bài toán đều phải phục vụ được tất cả các khách hàng. Bằng việc khai thác các đặc điểm khác nhau của mỗi khách hàng ta có thể xây dựng rất nhiều bài toán VRP khác nhau. Ví dụ như khi mỗi khách hàng yêu cầu phải được giao (delivery) một lượng hàng hóa hay thu gom hàng (pick-up) tại địa điểm của khách hàng rồi vận chuyển đến nơi khác ta có bài toán VRP với nhận và chuyển hàng kết hợp (VRPPD).
Khi tính đến koảng thời gian mà khách hàng có thể được phục vụ (time windows) ta có bài toán VRP với hạn chế thời điểm phục vụ (VRPTW). Đối với bài toán VRP có giới hạn thời điểm phục vụ, bài toán cần nhiều thêm rất nhiều xử lý, vì khi đó xe không thể đến muộn hơn thời gian cho phép nhưng nó có thể đến sớm và đợi cho đến giờ để phục vụ khách hàng. Trong trường Trang 14 hợp này, một khoản phí phạt có thể được tính đến khi xe đến chậm hơn giờ quy định. Khi đó hàm mục tiêu phải thay đổi để tính đến khoản tiền phạt này.
Ngoài ra, đối với mỗi khách hàng còn cần phải tính đến thời gian bốc dỡ hoặc xếp hàng hóa, thời gian này phụ thuộc vào loại hàng hóa, số lượng khi đặt hàng và người bốc dỡ. Thời gian phụ vụ này được dùng để tính toán thời gian mà mỗi xe cần trước khi đi đến chỗ khách hàng kế tiếp. Những yếu tố không xác định trong bài toán VRP Trong những dạng bài toán VRP trình bày ở trên, ta chưa nhắc đến vai trò của những yếu tố chưa xác định. Trong nhiều trường hợp hàm mục tiêu phụ thuộc vào nhiều yếu tố chưa xác định, khi đó hàm mục tiêu sẽ có tính biến thiên rất lớn.
Lớp bài toán dạng này được gọi là VRP không xác định (stochastic VRP). Những yếu tố chưa biết có thể là có khách hàng hoặc không, khối lượng hàng hóa khách hàng yêu cầu hay thời gian di chuyển và thời gian phục vụ. Trong thực tế, các yếu tố chưa xác định thường là khách hàng hoặc lượng hàng hóa yêu cầu. Đặc biệt là trong trường hợp người lập kế hoạch kinh doanh muốn lập kế hoạch cho khoảng thời gian xa hơn so với dữ liệu hiện có.
Thông thường, một công ty thường muốn lập kế hoạch vận chuyển trong một vài tháng sắp tới nhằm xây dựng chiến lược kinh doanh phù hợp. Các tuyến đường được lập trước này sẽ được sử dụng vào thực tế khi các yêu cầu của khách hàng xuất hiện. Vì tính ứng dụng thực tiễn cao như vậy nên lớp bày toán dạng này được nghiên cứu rất nhiều trong thời gian gần đây. Ví dụ như những nghiên cứu của M.
S´eguin và của Bianchi. F 0 1 2 F 1 Ngoài ra các yếu tố chưa biết có thể là thời gian vận chuyển và thời gian phục vụ. Những yế tố này, đặc biệt là thời gian vận chuyển, thường xuất hiện trong 1 Xem thêm tại: M. Stochastic vehicle routing.
European Journal of Operational Research, 88(1):3–12, 1996 2 Xem thêm tại: L. Bianchi và các cộng sự. Metaheuristics for the vehicle routing problem with stochastic demands. Technical Report TR-12-04, IDSIA, Galleria 2, Manno, 6928, Switzerland, 2004 Trang 15 thực tế tại các thành phố lớn và có mật độ giao thông cao như Hà Nội và TP.
Hồ Chí Minh. Trên thực tế, sự biến đổi của thời gian vận chuyển này có thể ảnh hưởng rất lớn đến kết quả của các phương án đã được xây dựng cho bài toán. Sự ảnh hưởng của việc thời gian vận chuyển chưa xác định có thể được làm đơn giản hóa nếu chúng ta có thể giả sử là thời gian di chuyển gần như là hằng số trong những khoảng thời gian trong ngày. Điều này là hoàn toàn hợp lý do mật độ giao thông tại các thành phố thường rất cao ở giờ cao nhưng lại bình thường ở những khung giờ khác.
Bài toán tiêu biểu cho những bài toán dạng này, VRP với chi phí phụ thuộc thời gian (TDVRP) sẽ được giới thiệu ở phần 1. Cuối cùng, trong nhiều trường hợp, yếu tố chưa xác định cần phải tính đến là do sai số trong mô hình bài toán. Vấn đề này xuất hiện do sai số tính toán khoảng cách giữa các khách hàng. Vì chi phí để tính toán chính xác khoảng cách giữa các khách thường là rất cao đối với một lượng khách hàng lớn, nên trong nhiều trường hợp, một mô hình bài toán được xây dựng dựa trên khoảng cách xấp xỉ giữa các đỉnh.
Do đó khi áp dụng vào thực tế, thời gian vận chuyển có thể lớn hơn hoặc nhỏ hơn so với thời gian tính toán lý thuyết. Hơn nữa thời gian di chuyển còn phụ thuộc vào tài xế. Khi tuyến đường vận chuyển là cố định, tài xế sẽ “thạo đường” hơn và thời gian di chuyển nhanh hơn.