1. Mở đầu
Xe buýt là một trong những phương tiện giao thông huyết mạch của các thành phố. Vì vậy, lập tuyến xe buýt mới và tối ưu tuyến xe buýt cũ là một trong những ưu tiên hàng đầu. Mỗi tuyến xe buýt thường được biểu diễn bởi một đoạn thẳng có độ dài cố định và một số trạm xe buýt nằm giữa hai đầu mút. Người dân muốn các trạm nằm sao đó để tối ưu thời gian di chuyển của họ. Vì vậy, đối tượng cần được tối ưu là thời gian di chuyển trung bình của tất cả người dân.
2. Mô hình
Chúng ta xét mô hình sau:
Giả sử có một con đường dài L km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">L km. Dân số được phân bố đều nhau trên suốt con đường này. Chúng ta cần tìm số trạm xe buýt và vị trí tối ưu của chúng để giảm thiểu thời gian di chuyển trung bình mà một hành khách phải bỏ ra, để đi từ một điểm bất kỳ trên đường đến một điểm bất kỳ khác. Để đi từ P" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">P đến Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q, một hành khách phải đi bộ đến trạm xe buýt gần P" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">P nhất, sau đó lên xe và dừng lại ở trạm xe buýt gần Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q nhất, rồi đi bộ đến Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q. Nếu có hai trạm xe buýt cách P" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">P một khoảng như nhau, hành khách sẽ chọn trạm để giảm thiểu số trạm phải đi (tương tự nếu có hai trạm cách Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q một khoảng như nhau). Tốc độ đi bộ là W km/h" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">W km/h, tốc độ của xe buýt là B km/h" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">B km/h, và một chiếc xe buýt phải dành khoảng S" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">S giờ để nhận thêm hoặc bỏ ra các hành khách ở mỗi trạm. Chúng ta ký hiệu T(P,Q)" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">T(P,Q) là thời gian mà hành khách phải bỏ ra để đi từ P" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">P đến Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q.
Chẳng hạn ta xét bản đồ sau với độ dài quãng đường L=20km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">L=20km:
Có 5 trạm xe buýt và 3 vị trí ngẫu nhiên trên bản đồ, ta tính thời gian di chuyển giữa các vị trí này:
1. Để đi từ P" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">P đến R" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">R, hành khách cần đi 1 km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">1 km đến trạm 2, sau đó qua 2 trạm với độ dài 14 km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">14 km xuống trạm 4, rồi đi bộ 1 km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">1 km đến R" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">R. Tổng thời gian là:
T(P,R)=1W+14B+2S+1W=2W+14B+2S
2. Tương tự, để đi từ Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q đến R" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">R, ta cần thời gian:
T(Q,R)=T(P,R)+1W=3W+14B+2S
3. Để đi từ P" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">P đến Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q, hành khách sẽ đi bộ 1 km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">1 km đến trạm 2, đi xe buýt 0 km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">0 km đến trạm 2 (nghĩa là không làm gì cả), rồi đi bộ 2 km" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">2 km đến Q" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">Q. Tổng thời gian là:
T(P,Q)=1W+0B+0S+2W=3W
(Trường hợp này chỉ dùng để minh họa thuật Toán đi, không có ý nghĩa thực tế.)
Chúng ta thống nhất một vài điều kiện và ký hiệu:
• Luôn có một trạm xe buýt ở 2 đầu mút của đoạn đường.
• Giả sử vị trí của các trạm là 0=x1<⋯<xn−1<xn=L" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">0=x1<⋯<xn−1<xn=L, khi đó ta biểu diễn tuyến xe buýt A" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">A qua bộ sắp xếp trạm là A=(x1,x2,⋯,xn−1,xn)" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">A=(x1,x2,⋯,xn−1,xn)..
• Tuyến xe buýt A" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">A cũng có thể được biểu diễn thông qua bộ A=(d1,d2,⋯,dn−1,dn)" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">A=(d1,d2,⋯,dn−1,dn), với di=xi−xi−1" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">di=xi−xi−1 và i=1,2,...,n" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">i=1,2,...,n.
• Ký hiệu E(A)" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">E(A) là thời gian trung bình để đi từ một điểm bất kỳ này đến một điểm bất kỳ khác trên tuyến xe buýt A" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">A, khi bộ sắp xếp trạm của tuyến này được cố định.
3. Câu hỏi
Bài toán 1.
1) Cố định n" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">n và bỏ qua thời gian đón và thả hành khách ở mỗi trạm. Chứng minh rằng bộ sắp xếp tối ưu xảy ra khi các trạm xe buýt cách đều nhau. Nghĩa là E(A)" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">E(A) đạt giá trị tối thiểu khi d1=d2=...=dn−1=dn" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">d1=d2=...=dn−1=dn.
2) Xét trường hợp L=20,W=5,B=20,S=0.05" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">L=20,W=5,B=20,S=0.05. Tìm giá trị của n" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">n để tối ưu hóa E(A)" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">E(A), biết A" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">A có n+1" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">n+1 trạm xe buýt cách đều nhau. (Do S≠0" role="presentation" style="display: inline-block; line-height: 0; font-size: 18.18px; overflow-wrap: normal; word-spacing: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; margin: 0px; padding: 1px 0px; position: relative;">S≠0 nên không đảm bảo đây là cách sắp xếp tối ưu nhất với một giá trị n bất kỳ.)
Bài toán 2. Mô hình của chúng ta còn nhiều khuyết điểm:
1) Hành khách hoàn toàn có thể đi bộ trực tiếp nếu 2 điểm đi và đến gần nhau.
2) Hành khách thường xuyên đến một số nơi như siêu thị, cơ quan, nhà riêng, .v.v. hơn một số điểm trung gian khác.
3) Dân số phân bố chưa hẳn đã đồng đều trên toàn tuyến.
Dựa trên câu 1.1) và 1.2), hãy đưa ra một mô hình có thể giải quyết ba vấn đề trên. Để đơn giản, bạn vẫn có thể giả sử tuyến xe buýt là một đường thẳng.