Một số bài toán liên quan đến việc tổ chức mạng vận chuyển bưu chính

Mô hình định tuyến mạng đường thư cấp 1

Mạng đường thư cấp một thực chất là một đồ thị có các đỉnh là các nút trung tâm Bưu chính và các Bưu điện trung tâm. Vận chuyển giữa các nút mạng có thể qua đường trực tiếp hoặc qua các nút trung gian. Do vậy xuất hiện bài toán lựa chọn tuyến đường vận chuyển. Tức là phải chỉ ra cách vận chuyển từ một nút bất kỳ tới một nút bất kỳ khác cần phải qua nút trung gian nào. Giữa 2 đỉnh sẽ có cung liên kết nếu chúng có đường vận chuyển trực tiếp với nhau.

Để giải bài toán xác định đường vận chuyển bưu chính cần có các khái niệm sau:

1. Lưu lượng (luồng) vận chuyển bưu gửi: Số lượng bưu gửi xuất hiện tại một nút mạng bất kỳ cần phải chuyển tới một nút mạng khác. Đại lượng này tính trong một đơn vị thời gian (giờ, ngày, tuần, tháng), được gọi là tải trọng. Do đặc điểm không đồng đều của tải trọng theo ngày trong tuần và tháng trong năm nên ta chỉ xét tải trọng trung bình ngày để lập kế hoạch vận chuyển (thống kê một tháng tiêu biểu và chia trung bình cho một ngày). Trong mô hình, tải trọng giữa các nút mạng được biểu diễn dưới dạng ma trận mà phần tử (ij) được hiểu là tải trọng trong một ngày từ nút mạng i tới nút mạng j.

2. Khả năng lưu thoát của nút mạng là số lượng bưu gửi có thể được khai thác tại một nút mạng trong một ngày. Khả năng lưu thoát phụ thuộc vào nhiều yếu tố như diện tích mặt bằng, mức độ cơ giới hoá, tự động hoá, tổ chức sản xuất, mức độ không đồng đều của tải trọng, tần số và thời gian khởi hành của các phương tiện vận chuyển...

3. Giá trị của các cung (chiều dài các cung) là giá thành vận chuyển một đơn vị sản phẩm theo từng cung liên kết, hoặc thời gian vận chuyển giữa các nút mạng. Đơn vị sản phẩm có thể là một túi thư, một container hoặc một bưu kiện tuỳ vào bài toán cụ thể. Giá thành vận chuyển một đơn vị sản phẩm được biểu diễn qua chiều dài cung hoặc thời gian vận chuyển giữa các nút mạng.

Bài toán lập kế hoạch vận chuyển bưu gửi

Trước tiên, xét hai nút mạng cần trao đổi bưu gửi, một nút mạng là nguồn ws, một nút là đích wt, luồng tải trọng từ nguồn tới đích sẽ là: (x1 ,...,xj ,...,xn)

các cung d_j với xj> 0 tạo thành tuyến vận chuyển tải trọng xjtừ nguồn wstới đích wt , tuyến vận chuyển này được xác định là một tập hợp các nút mạng (hay tập hợp các cung) tham gia vào tuyến vận chuyển này.

Như vậy, bài toán định tuyến mạng vận chuyển bưu gửi là cần xác định luồng bưu gửi từ một nút mạng tới một nút mạng khác cần phải qua các nút trung gian nào để tối thiểu hoá chi phí vận chuyển của toàn bộ mạng, đồng thời việc lựa chọn tuyến đường cần thoả mãn các điều kiện ràng buộc về thời gian toàn trình và khả năng lưu thoát của từng nút mạng.

Trong mạng vận chuyển bưu chính, trên mạng đồng thời thực hiện nhiều luồng trao đổi, mỗi một luồng có nút khởi đầu và nút kết thúc. Do vậy, cần đưa vào ký hiệu từng luồng là véc tơ xq:

x^q =(x^q₁,..., x^q_j,...,x^q_n)

Xqcần thoả mãn điều kiện không âm và điều kiện bảo toàn luồng nghĩa là:

AXq =Vq         Xq ≥ 0Trong đó:Vq: véctơ tất cả các phần tử đều bằng 0, ngoại trừ hai phần tử tương ứng với nút mạng khởi đầu và nút kết thúc có giá trị là -vqvà Vq(vRlà lưu lượng cần vận chuyển của mỗi luồng);

A: Ma trận liên kết cung nút chứa m dòng và n cột trong đó m là số nút mạng và n là số cung. Ma trận A chính là mô hình định tuyến mạng vận chuyển của từng luồng cần xác định.

Ma trận liên kết cung nút của graph G = (W,D), ký hiệu A=[aij] có kích thước m x n với các phần tử được xác định như sau:

aij =

1, nếu wi là đỉnh đầu của cung dj−1, nếu wi là đỉnh cuối của cung dj 0, nếu wi không là đỉnh đầu hoặc cuối của cung dj

Ngoài ra luồng Xqcòn phải thoả mãn điều kiện ràng buộc không được vượt quá khả năng khai thác của từng nút mạng wi.

Xét véc tơ Pi(Pi₁, Pi₂, ... Pin) trong đó Pi= l nếu djhướng tới đỉnh wivà Pi = 0 nếu ngược lại. Véc tơ Pichính là dòng i của ma trận liên kết cung nút A mà trong đó tất cả các phần tử -l được thay bằng 0.

Như vậy, điều kiện ràng buộc về khả năng lưu thoát của các nút mạng là:

Trong đó:

hi: Khả năng Lưu thoát của nút mạng W

r: Số đôi nút mạng trong mạng có trao đổi bưu gửi

Tiêu chí tối ưu của bài toán vận chuyển bưu gửi như sau:

Giả sử C (C₁,C₂,... Cn) là Véctơ chi phí vận chuyển trong đó C_j là cước vận chuyển l đơn vị sản phẩm qua cung dj(chiều dài cung d_j). Khi đó chi phí vận chuyển sẽ là:

Z = CX¹ + ... + CXq+ ... + CXr

   = C(X¹ + ... + Xq+ ... + Xr) → min

Vậy mô hình vận chuyển tối ưu là:

min[Z = C(X1+ ... + Xq+ ... + Xr)]

P1(X¹ + ... + Xq+ ... + Xr) ≤ h1

..................................................

P m (X 1 + ... + X q + ... + X r ) ≤ h m

AX 1                                         = V 1

AX q                                         = V q

AX r                                          = V r

Trong trường hợp không có điều kiện hạn chế về khả năng lưu thoát của các nút mạng, bài toán định tuyến mạng bưu chính chỉ đơn giản là bài toán tìm đường đi ngắn nhất giữa từng đôi nút mạng. Bài toán tìm đường ngắn nhất được giải bằng thuật toán dán nhãn của Dijkstra.

Mô hình mạng đường thư trong thành phố

Mạng đường thư trong thành phố là một đồ thị đỉnh của nó là các bưu cục. Hai đỉnh của đồ thị sẽ được nối kết với nhau bằng cung liên kết nếu giữa chúng có tuyến đường đi. Trong thành phố giữa các bưu cục bao giờ cũng có các đường thư, nên đồ thị được kết nối theo kiểu điểm nối điểm. Đồ thị mạng đường thư trong thành phố là một đồ thị có hướng vì khoảng cách i tới j và j tới i có thể không trùng nhau (đường một chiều). Giá trị của cung được biểu diễn bằng khoảng cách hoặc thời gian vận chuyển giữa các nút mạng hoặc chi phí vận chuyển giữa các nút mạng.

Ta có chi phí vận chuyển giữa các nút mạng là:

c_ịj = kr_ij

r_ij : Khoảng cách giữa các nút i và nút j (cần được xác định theo khoảng cách thực tế và phải lựa chọn r_ij là đường ngắn nhất, tức là phải thoả mãn điều kiện r_ij ≤ r_ik + r_kj do một cạnh tam giác nhỏ hơn tổng 2 cạnh còn lại).

k: Chi phí vận chuyển l km bằng ô tô.

Thời gian vận chuyển trên cung ij

V_ij : Vận tốc vận chuyển ô tô từ nút i tới nút j.

t_0j : Thời gian trao đổi tại nút mạng j.

Khi tổ chức mạng đường thư có thể sử dụng phương thức đường thẳng, đường vòng hoặc hỗn hợp.

Mạng đường vòng có ưu điểm là sử dụng các phương tiện vận chuyển hiệu quả hơn. Do vậy trong thành phố thường sử dụng đường vòng do tính kinh tế của nó.

Bài toán

Bài toán tổ chức mạng đường thư trong thành phố là xác định hành trình của từng chiếc ô tô phải qua các nút mạng nào, theo trình tự nào để đảm bảo chi phí vận chuyển toàn mạng là nhỏ nhất (hoặc tổng quãng đường hay tổng thời gian vận chuyển nhỏ nhất) đồng thời thoả mãn các ràng buộc về thời gian vận chuyển của từng ô tô và dung lượng vận chuyển của từng ô tô.

Trong hệ thống khai thác tập trung tồn tại một Bưu điện trung tâm duy nhất. Nếu chia các nút mạng ra làm hai loại nguồn và đích, nút mạng trung tâm sẽ là nguồn, các nút mạng còn lại sẽ là đích hoặc ngược lại.

Trong mô hình vận chuyển bưu gửi trong thành phố, các đỉnh đồ thị được đặc trưng bởi số lượng bưu gửi mà nó cần nhận được từ q_i hoặc ngược lại cần gửi đi r_i.

Trong đó:

0: nút nguồn.

i = l ÷ N : đích

Trong hệ thống khai thác phân tán khi đó đồ thị sẽ được chia thành các đồ thị con, mỗi một đồ thị chỉ có một nút mạng nguồn duy nhất và việc giải bài toán thực tế là giải từng bài toán con.

Nếu mạng vận chuyển trong thành phố chủ yếu bằng ô tô, ta giả sử:

M: số ô tô toàn mạng

Q_j - dung lượng của j ô tô, phụ thuộc vào loại ô tô

T - thời gian vận chuyển tối đa cho phép trên một đường thư.

T được xác định dựa trên các định mức (T = 2 giờ).

Q_j = min (P_j / b, V_j / d)

Trong đó P_j : tải trọng của ô tô;

V_j : thể tích vận chuyển của ô tô;

b: Khối lượng trung bình của túi thư;

d: thể tích trung bình của túi thư.

Mô hình toán học

Giả sử gọi xijk là ẩn cần tìm, xijk = 1 nếu trong tuyên vòng k, đỉnh j sẽ được tới ngay sau đỉnh i, Xijk = 0 trong trường hợp ngược lại, khi đó mô hình toán học của bài toán mạng đường thư trong thành phố là:

Biến Xijk cần thoả mãn các ràng buộc sau:

	j = 0 ÷ N	(1)
	k = 1 ÷ M, p = 0 ÷ N	(2)
	k = 1 ÷ M	(3)
	k = 1 ÷ M	(4)

Trong đó t_0i : thời gian trao đổi tại nút mạng i.

(l): Do mỗi đỉnh đồ thị chỉ thuộc một tuyến đường vòng;

(2): Đối với mỗi một đỉnh, số lượng các cung đi vào và đi ra phải bằng nhau tại một đỉnh;

(3): Ràng buộc về dung lượng của ô tô;

(4): Ràng buộc về thời hạn vận chuyển của từng ô tô.

Đây là bài toán tổng quát về mạng vận chuyển thư trong thành phố. Bài toán tìm hành trình của bưu tá qua n điểm là trường hợp riêng khi chỉ có 1 tuyến đường vòng qua n điểm (M=1), còn bài toán này cần xác định M tuyến đường cho M ô tô và cần thoả mãn các hạn chế (ràng buộc) về chỉ tiêu thời gian và dung lượng vận chuyển của ô tô.