Chương 1 Định nghĩa và một số kí hiệu Trong chương này, chúng ta sẽ đưa ra định nghĩa chính tắc cho lớp các bài toán định tuyến xe. Các định nghĩa này được xây dựng theo ngôn ngữ của lý thuyết đồ thị được đưa ra bởi P. Các bài toán được mô tả thuộc lớp VRP (vehicle routing problem) bao gồm định tuyến xe với ràng buộc tải trọng - CVRP (capacitated VRP ), định tuyến xe với ràng buộc khung thời gian - VRPTW (VRP with time windows), định tuyến xe với lấy và giao hàng - VRPPD (VRP with pickup and delivery).1: Các bài toán, biến thể của VRP.1 Định nghĩa bài toán 1.1 CVRP Trước hết, ta xem xét mô hình cho bài toán nguyên bản: bài toán định tuyến xe với ràng buộc tải trọng. Bài toán nguyên bản là CVRP mà không phải là VRP (không ràng buộc).
Ta thấy rằng nếu không có bất kì ràng buộc nào thì một xe có thể phục vụ tất cả các yêu cầu và bài toán VRP sẽ trở thành TSP (travelling salesman problem). Ít nhất ràng buộc về tải trọng là thực tế và giữ cho mỗi xe chỉ phục vụ 5 được một số yêu cầu nhất định (trong trường hợp số yêu cầu không quá nhỏ cũng như tải trọng của xe là quá lớn). Gọi G = (V, A) là một độ thị đầy đủ với V = {0, ., n} là tập nút và A là tập các cung., n đại diện cho các yêu cầu hay khách hàng cần phục vụ, nút 0 là kho hàng. Đôi khi, kho hàng cũng được biểu diễn bằng nút n + 1.
Một số không âm được gọi là chi phí cij đại diện cho mỗi cung (i, j) ∈ A. Nói cách khác, cij là chi phí cần bỏ ra để di chuyển từ nút i tới nút j. Trong bài toán này và hầu hết các bài toán định tuyến, ta không định nghĩa cạnh (i, i) nên có thể gán cii = ∞ với i ∈ V. Nếu đồ thị là có hướng thì ma trận chi phí c là bất đối xứng, khi đó ta có bài toán CVRP bất đối xứng ACVRP (asymetric CVRP ).
Ngược lại, nếu cij = cji với mọi (i, j) ∈ A ta có bài toán CVRP đối xứng SCVRP (symetric CVRP ) và các cung của A được thay thế bằng tập cách cạnh vô hướng E. Với một cạnh e ∈ E, ta gọi α(e) và β(e) là nút bắt đầu và kết thúc của cạnh. Đồ thị G phải là đồ thị liên thông và nhìn chung ta giả thiết đồ thị G là đầy đủ. Với một nút i, gọi ∆+ (i) là tập ra của i (forward star ), được định nghĩa là tập các nút j mà cung (i, j) ∈ A, nói cách khác, đây là tập các nút có thể tiếp cận trực tiếp từ nút i.
Tương tự như vậy, ∆− (i) là tập vào của i (backward star ), được định nghĩa là tập các nút j mà cung (j, i) ∈ A hay là tập các nút tiếp cận trực tiếp tới nút i. Với một tập nút con S ⊆ V , gọi δ(S) là tập các cạnh e ∈ E chỉ có một hoặc cả hai đầu mút thuộc S. Để thuận tiện, khi xét một nút i ∈ V , ta viết δ(i) thay cho δ({i}). Trong hầu hết các bài toán thực tế, ma trận chi phí thỏa mãn bất đẳng thức tam giác cij + cjk ≥ cik , ∀i, j, k ∈ V.1) Nói cách khác, việc đi trực tiếp từ nút i tới nút j luôn tốn ít chi phí hơn là đi gián tiếp.
Với nhiều thuật toán, bất đẳng thức tam giác là điều kiện cần, điều này có thể được đảm bảo bằng cách thêm một đại lượng dương lớn (hợp lý) vào chi phí của mỗi cung. Ta chú ý thêm rằng, nếu chi phí của mỗi cung thuộc đồ thị bằng với chi phí của đường đi ngắn nhất giữa hai đầu mút của cung thì mà trận chi phí thỏa mãn bất đẳng thức tam giác. Trong nhiều trường hợp, tập các nút nằm trên một mặt phẳng, vị trí của chúng được cho bởi tọa độ và chi phí cij của mỗi cung (i, j) ∈ A là khoảng cách Euclide giữa hai điểm ứng với nút i và j. Khi đó, ma trận chi phí là đối xứng và thỏa mãn bất đẳng thức tam giác.
Bài toán này được gọi là Euclidian SCVRP. 6 Mỗi khách hàng i có một nhu cầu (về tải trọng) là di và nhu cầu của kho d0 = 0. P Với một tập nút S ⊆ V , ta kí hiệu d(S) = i∈S di là tổng nhu cầu của tập. Một tập hợp K đại diện cho các xe, mỗi xe có tải trọng C, các xe sẵn sàng ở kho tại thời điểm bắt đầu.
Ta giả thiết di ≤ C với mỗi i = 1,. Điều kiện này này là cần thiết để mỗi khách hàng đều được phục vụ. Mỗi xe phục vụ nhiều nhất một tuyến và ta giả thiết K không nhỏ hơn Kmin với Kmin là số xe ít nhất cần để phục vụ toàn bộ khách hàng. Với một tập S ⊆ V \ {0}, ta gọi r(S) là số xe ít nhất để phục vụ toàn bộ khách hàng thuộc tập S.
Chú ý rằng r(V \ {0}) = Kmin. Kmin có thể được xác định bằng cách giải bài toán đóng gói (Bin Packing Problem - BPP ). Bài toán yêu cầu tìm số gói nhỏ nhất, mỗi gói có tải trọng C để chứa n vật, mỗi vật có khối lượng không âm di , i = 1,. BPP cũng là một bài toán NP-khó, một trong những phương pháp hiệu quả có thể được tìm thấy trong công trình của S.
CVRP yêu cầu tìm một tập chính xác K các chu trình đơn (mỗi chu trình ứng với một tuyến đường) với tổng chi phí của tất cả các cung thuộc các chu trình này là nhỏ nhất. Lời giải phải thỏa mãn các ràng buộc sau (i) mỗi chu trình đều đi qua nút ứng với kho hàng; (ii) mỗi nút ứng với một khách hàng được đi qua bởi đúng một chu trình; (iii) tổng nhu cầu của các khách hàng trong mỗi chu trình không được vượt quá tải trọng của xe.2 VRPTW Bài toán định tuyến xe với ràng buộc thời gian - VRPTW (VRP with time windows) là một mở rộng của CVRP. Trong đó, ngoài ràng buộc về tải trọng cho mỗi xe, mỗi khách hàng i bị ràng buộc bởi một khoảng thời gian [ai , bi ] được gọi là khung thời gian hay cửa sổ thời gian (time window ). Thời gian phục vụ khách hàng i là si.
Thời gian di chuyển từ nút i tới nút j là tij với mỗi cung (i, j) ∈ A hay te với e ∈ E. Ngoài ra nếu xe đến nút i sớm thì phải chờ đến thời gian ai mới được phục vụ. Nếu xe đến nút i muộn hơn bi thì khách hàng sẽ không được phục vụ. Thường thì ma trận chi phí và ma trận thời gian di chuyển là như nhau, hơn nữa các xe được giả thiết đều xuất phát từ kho tại thời điểm 0.
Ràng buộc thời gian dẫn tới việc mỗi tuyến đường là có hướng (có thứ tự đi đến các nút) ngay cả khi ma trận chi phí là đối xứng. Chính vì thế, VRPTW thường được mô tả như một bài toán bất đối xứng. 7 VRPTW yêu cầu tìm một tập chính xác K chu trình đơn với tổng chi phí là nhỏ nhất, thỏa mãn các ràng buộc sau đây (i) mỗi chu trình đều đi qua nút ứng với kho hàng; (ii) mỗi nút ứng với một khách hàng được đi qua bởi đúng một chu trình; (iii) tổng nhu cầu của các khách hàng trong mỗi chu trình không được vượt quá tải trọng của xe; (iv) với mỗi khách hàng i, thời gian bắt đầu phục vụ phải nằm trong khung thời gian [ai , bi ] và xe hoàn thành việc phục vụ sau khoảng thời gian si. VRPTW là bài toán NP-khó, nó là trường hợp tổng quát của CVRP.
Nếu ta đặt ai = 0 và bi = ∞ với i ∈ V \ {0} thì VRPTW trở thành CVRP. Ngoài ra ta cũng thu được biến thể TSP với ràng buộc thời gian (TSPTW) nếu C ≥ d(V ) và K = 1.3 VRPPD Một biến thể khác nữa của CVRP là bài toán định tuyến xe với lấy và giao hàng (VRP with pickup and delivery - VRPPD). Trong đó, mỗi khách hàng i có thêm hai đại lượng đặc trưng nữa là di và pi lần lượt là nhu cầu lấy và giao (của khách hàng) tại vị trí của khách hàng i. Đôi khi, ta chỉ dùng một đại lượng di = di − pi cho mỗi khách hàng i để chỉ lượng nhu cầu chênh lệch giữa việc lấy và giao hàng (có thể là số âm).
Với mỗi khách hàng i, gọi Oi là nút đại diện cho điểm giao hàng và Di là nút đại diện cho điểm lấy hàng. Với mỗi khách hàng, ta giả thiết điểm giao được phục vụ trước điểm lấy. Do đó, tải hiện tại của một xe trước khi tới điểm đã cho là tải ban đầu trừ đi tổng nhu cầu đã giao cộng với tổng nhu cầu đã lấy. VRPPD yêu cầu tìm chính xác một tập K các chu trình đơn với tổng chi phí là nhỏ nhất, thỏa mãn các ràng buộc sau đây (i) mỗi chu trình đều đi qua nút ứng với kho hàng; (ii) mỗi nút ứng với một khách hàng được đi qua bởi đúng một chu trình; (iii) tải hiện tại của xe trong suốt quá trình phục vụ không âm và không được vượt quá tải trọng của xe; (iv) với mỗi khách hàng i, khách hàng Oi khác với kho phải được phục vụ trong cùng một tuyến và trước khách hàng i; 8 (v) với mỗi khách hàng i, khách hàng Di khác với kho phải được phụ vụ trong cùng một tuyến và sau khách hàng i.
VRPPD là trường hợp tổng quát của CVRP. Nếu ta đặt Oi = Di = 0 và pi = 0 cho mọi i ∈ V thì VRPPD suy biến về CVRP. Hơn nữa nếu đặt K = 1 thì ta thu được TSP với lấy và giao hàng (TSP with pickup and delivery - TSPPD).2 Mô hình toán học Phần tiếp theo, ta trình bày một số mô hình toán học cơ bản cho VRP theo P. Mô hình cụ thể cho VRPTW được trình bày ở phần 1.1 Các mô hình cơ bản cho VRP Trong phần này, chúng ta cùng xem xét các mô hình toán học cơ bản cho VRP và xem xét cách các mô hình này được mở rộng để kết hợp hay bổ sung ràng buộc hoặc hàm mục tiêu.
Có ba cách tiếp cận để mô hình hóa VRP. Loại mô hình đầu tiên là "mô hình dựa trên dòng xe" (vehicle flow formulations) sử dụng các biến nguyên ứng với mỗi cung hay cạnh của đồ thị.