Đến nội dung


Chú ý

Diễn đàn vừa được bảo trì và nâng cấp nên có thể sẽ hoạt động không ổn định. Các bạn vui lòng thông báo lỗi cho BQT tại chủ đề này.


Hình ảnh
- - - - -

Bài toán chuyến xe bus


  • Please log in to reply
Chưa có bài trả lời

#1 hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản trị
  • 853 Bài viết
  • Giới tính:Nam
  • Đến từ:Khoa Toán học, trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Tp. Hồ Chí Minh, Việt Nam
  • Sở thích:toán, toán và.... toán

Đã gửi 13-02-2017 - 20:41

BÀI TOÁN CHUYẾN XE BUS
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 thành phố, xấp xỉ lên đến 33 nghìn chuyến mỗi ngày. 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 của thành phố. 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 \text{ 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$ đến $Q$, một hành khách phải đi bộ đến trạm xe buýt gần $P$ nhất, sau đó lên xe và dừng lại ở trạm xe buýt gần $Q$ nhất, rồi đi bộ đến $Q$. Nếu có hai trạm xe buýt cách $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$ một khoảng như nhau). Tốc độ đi bộ là $W \text{ km/h}$, tốc độ của xe buýt là $B \text{ km/h}$, và một chiếc xe buýt phải dành khoảng $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)$ là thời gian mà hành khách phải bỏ ra để đi từ $P$ đến $Q$.
 
Chẳng hạn ta xét bản đồ sau với độ dài quãng đường $L = 20 km$:
Capture.PNG
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$ đến $R$, hành khách cần đi $1 \text{ km}$ đến trạm 2, sau đó qua 2 trạm với độ dài $14 \text{ km}$ xuống trạm 4, rồi đi bộ $1 \text{ km}$ đến $R$. Tổng thời gian là:
$$T(P,R)=\frac{1}{W}+\frac{14}{B}+2S+\frac{1}{W}=\frac{2}{W}+\frac{14}{B}+2S$$
2. Tương tự, để đi từ $Q$ đến $R$, ta cần thời gian:
$$T(Q,R)=T(P,R)+\frac{1}{W}=\frac{3}{W}+\frac{14}{B}+2S$$
3. Để đi từ $P$ đến $Q$, hành khách sẽ đi bộ $1 \text{ km}$ đến trạm 2, đi xe buýt $0 \text{ km}$ đến trạm 2 (nghĩa là không làm gì cả), rồi đi bộ $2 \text{ km}$ đến $Q$. Tổng thời gian là:
$$T(P,Q)=\frac{1}{W}+\frac{0}{B}+0S+\frac{2}{W}=\frac{3}{W}$$
(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 = x_{1} < \cdots < x_{n-1} < x_{n} = L$, khi đó ta biểu diễn tuyến xe buýt $A$ qua bộ sắp xếp trạm là $A = (x_{1}, x_{2}, \cdots, x_{n-1}, x_{n})$..
• Tuyến xe buýt $A$ cũng có thể được biểu diễn thông qua bộ $A = (d_{1}, d_{2}, \cdots , d_{n-1}, d_{n})$, với $d_{i} = x_{i} - x_{i-1}$ và $i = 1, 2, . . . , n$.
• Ký hiệu $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$, 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$ 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)$ đạt giá trị tối thiểu khi $d_{1} = d_{2} = . . . = d_{n-1} = d_{n}$.
 
2) Xét trường hợp $L = 20, W = 5, B = 20, S = 0.05$. Tìm giá trị của $n$ để tối ưu hóa $E(A)$, biết $A$ có $n + 1$ trạm xe buýt cách đều nhau. (Do $S \neq 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.

 

Nguồn: Lê Tạ Đăng Khoa, Bài toán chuyến xe bus, tạp chí Epsilon, số 1, 2015, https://www.facebook...412604425701926


Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

logocopy.jpg?t=1339838138


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh