Tài liệu Một giải pháp tiếp cận bài toán thiết lập lịch trình vận tải tối ưu đối với mạng giao thông công cộn

MỘT GIẢI PHÁP TIẾP CẬN BÀI TOÁN THIẾT LẬP LỊCH TRÌNH VẬN TẢI TỐI ƯU ĐỐI VỚI MẠNG GIAO THÔNG CÔNG CỘNG CÓ NHIỀU TRUNG TÂM ĐIỀU HÀNH








TÓM TẮT. Chúng tôi nghiên cứu bài toán xây dựng lịch trình vận tải tối ưu cho mạng giao thông công cộng với nhiều trung tâm điều hành và đề xuất một giải pháp khả thi dựa trên phương pháp phân rã kết hợp với một quá trình lặp. Mỗi vòng lặp bao gồm hai bước, trong đó mỗi bước là một bài toán tối ưu giải được.






I. Đặt vấn đề
Mục tiêu cao nhất của một mạng giao thông công cộng thành phố là đáp ứng được các yêu cầu vận tải hành khách do cơ quan quản lý giao thông đô thị đặt ra, trên cơ sở khảo sát nhu cầu đi lại trong thực tế. Yêu cầu này thường được thể hiện dưới dạng một tập hợp các hành trình nối các nút giao thông cơ bản trong thành phố (với tần suất xác định, trong một khoảng thời gian được đặt ra theo kế hoạch). Trong quá trình thực hiện các hành trình này, xe thường phải thực hiện một số hành trình khác không có trong yêu cầu (ví dụ như là đoạn đường từ bãi để xe cho đến điểm đầu của hành trình phục phụ đầu tiên, hay là đoạn đường xe chạy từ điểm cuối một hành trình vừa thực thi xong cho đến điểm đầu của hành trình khác cần thực thi tiếp theo,v.v .). Đây là phần chi phí không sinh lợi, và một trong những mục tiêu quan trọng trong ngành giao thông là giảm thiểu các chi phí này, dựa trên việc sắp xếp hợp lý các lịch trình và việc phân bổ các tuyến về cho các trung tâm điều hành.
Trong thực tế, mạng lưới xe bus của một thành phố được hình thành và phát triển qua nhiều giai đoạn, song song với sự phát triển của chính thành phố đó. Cho dù ngay từ ban đầu nó có thể được thiết kế một cách tối ưu, nhưng trong quá trình vận hành, với sự mở rộng của đô thị và sự tăng trưởng không ngừng của các lực lượng tham gia giao thông, mạng sẽ không thể giữ nguyên cấu trúc tối ưu ban đầu, do việc phải bổ sung thêm các hành trình mới (xuất phát từ yêu cầu thực tế). Khi ấy, một yêu cầu tự nhiên được đặt ra là cần tái cơ cấu lại lịch trình (và kèm theo là phân bố lại chỉ tiêu phục vụ của các trung tâm điều hành) để tiếp tục có được tính tối ưu ở mức hợp lý. Thông thường, một phương án tối ưu thực sự cho giai đoạn mới thường khác biệt rất xa so với phương án hiện có, và do vậy sẽ đòi hỏi có những thay đổi lớn trong công tác điều hành và quản lý hoạt động của mạng. Một phương án mới sẽ chỉ là khả thi khi tính tối ưu của nó mang lại hiệu quả kinh tế vượt trội so với cái giá phải trả cho việc làm thay đổi về nền nếp quản lý và vận hành (do nó gây ra). Có lẽ đây là một trong những nguyên nhân chính làm cho các phương án tối ưu về mặt lý thuyết không dễ được triển khai trong thực tiễn, cho dù việc tìm ra được một lời giải tối ưu như vậy là một công việc vô cùng gian nan (như sẽ thấy trong phần tiếp theo, trình bày về mô hình toán học của bài toán này). Với các đô thị đang trong tiến trình thay đổi như ở nước ta, đặc biệt là khi khả năng dự báo về giao thông còn rất hạn chế, việc tìm một lời giải cho vận hành mạng ổn định trong thời gian dài (như là ở các nước phát triển) có lẽ chưa thể đặt ra, mà vấn đề khả thi hơn là tìm các phương án phục vụ cho vận hành mạng trong khoảng thời gian vừa phải, để rồi tiếp tục có những thay đổi mới. Điều

này đòi hỏi phương án đưa ra, ngoài khả năng làm giảm các chi phí không sinh lợi trong quá trình vận hành mạng, không được phép gây ra nhiều xáo trộn về mặt quản lý trong quá trình triển khai (và do vậy không đòi hỏi phải trả đáng kể cho việc này). Mục tiêu của bài báo này là nhằm đề xuất một giải pháp cho việc tìm những lời giải như vậy.


II. Mô hình toán học


1. Một số khái niệm và ký hiệu


Một trung tâm điều hành hay bến xe (depot) là nơi tập kết xe, từ đó các xe xuất phát đi thực hiện những hành trình đã quy định, và sau khi kết thúc các hành trình trong ngày, các xe lại phải trở về trung tâm. Trong trung tâm điều hành thường có gara phục vụ cho việc sửa chữa và bảo dưỡng định kỳ. Trung tâm điều hành (sau này thường được gọi tắt là trung tâm khi không thể xảy ra nhầm lẫn) được ký hiệu là d , và mỗi d có điểm xuất bến
là d+ , điểm nhập bến là dư .
Tập tất cả các trung tâm phục vụ cho mạng xe bus thành phố được ký hiệu là D , và tập tất cả các điểm xuất bến và điểm nhập bến của các trung tâm này ký hiệu lần lượt là

D+ = {d + /d

∈ D },

Dư = {dư /d ∈ D } .