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

Chia sẻ: Thanh Nga | Ngày: | Loại File: PDF | Số trang:16

0
407
lượt xem
167
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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...

Chủ đề:
Lưu

Nội dung Text: 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

  1. 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 PHẠM HUY ĐIỂN và PHẠM XUÂN HINH 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 1
  2. 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 } . Như đã nói, dựa trên kết quả khảo sát nhu cầu đi lại của dân cư trong thực tế, các cơ quan quản lý giao thông thành phố định ra yêu cầu phục vụ đối với mạng giao thông công cộng dưới dạng một tập hợp các hành trình chở khách cần phải thực hiện trong thành phố (sau này còn được gọi là các hành trình bắt buộc). Mỗi hành trình như vậy, được ký hiệu là t , có điểm xuất phát t − (điểm đỗ đầu tiên) với thời gian khởi hành là st ,và có điểm đỗ cuối cùng là t + với thời gian đến là et . Ta ký hiệu T là tập tất cả các hành trình bắt buộc, còn T − (T + , tương ứng) là tập hợp tất cả các điểm xuất phát (điểm đỗ cuối) của các hành trình t ∈ T . Như vậy, T − = {t − t ∈ T } và T + = { t + t ∈ T } . Thực ra, mỗi hành trình t ∈ T còn được gắn một thuộc tính quan trọng nữa là tải trọng tối đa (liên quan đến số lượng khách mà nó phải chở và do đó liên quan tới chủng loại xe được sử dụng: xe 2 tầng, xe dài có khớp nối, xe lớn, xe tầm trung,v.v...). Đây là thuộc tính được quy định trước, không phải là tham số cần tối ưu hóa, nhưng nó tạo ra ràng buộc vì không phải trung tâm nào cũng có gara phù hợp với loại xe phục vụ cho một hành trình cho trước. Ta ký hiệu tập tất cả các trung tâm điều hành có khả năng phục vụ cho hành trình t ∈ T là G ( t ) ⊆ D và gọi nó là nhóm các trung tâm có thể phục vụ được cho hành trình t ∈ T . Ngược lại, mỗi trung tâm điều hành có khả năng đưa xe đi phục vụ cho nhiều hành trình, cho nên ta có tập các hành trình có thể được phục vụ bởi xe của trung tâm điều hành d , ký hiệu là Td . Như vậy Td = { t ∈ T d ∈ G ( t ) } . Liên quan đến khái niệm này, ta có Td− = { t − ∈ T t ∈ Td } là tập hợp các điểm xuất phát của các hành trình trong tập Td , còn Td+ = { t + ∈ T t ∈ Td } là tập hợp các điểm đỗ cuối của các hành trình trong tập Td . Các hành trình chở khách nói chung là không "kế tiếp" nhau về mặt thời gian và vị trí địa lý (điểm đỗ cuối hành trình này không nhất thiết trùng với điểm xuất phát của hành trình khác, về thời gian hay vị trí địa lý), cho nên một chiếc xe muốn thực thi được hơn 2
  3. một hành trình chở khách trong một chu trình làm việc của mình thì phải trải qua những đoạn đường "chuyển tiếp hành trình", không có trong yêu cầu của cơ quan quản lý giao thông. Nói cách khác, trong vận hành của mạng còn có các hành trình không thuộc các hành trình bắt buộc nói trên. Có thể kể ra các hành trình kiểu này ở trên các đoạn đường sau đây: - Cung xuất bến nối điểm xuất bến d + với điểm xuất phát t − của một hành trình bắt buộc nào đó. Trên mỗi cung xuất bến có thể có nhiều hành trình được thực thi (vào các thời điểm khác nhau), và được gọi là các hành trình xuất bến. Để đảm bảo cho tính khả thi của các hành trình bắt buộc, người ta giả thiết rằng với mỗi hành trình t ∈ Td luôn tồn tại một hành trình xuất bến phù hợp với nó, nghĩa là có thời gian đến điểm t − trùng với thời điểm xuất phát của hành trình t . - Cung nhập bến nối điểm nhập bến d − với điểm đỗ cuối cùng t + của một hành trình bắt buộc nào đó. Tương tự như trên ta có khái niệm hành trình nhập bến và kèm theo là giả thiết về sự tồn tại các hành trình nhập bến phù hợp cho mỗi hành trình bắt buộc. - Cung liên kết nối điểm cuối của một hành trình p ∈ T (tức là p + ) với điểm xuất phát của một hành trình khác q ∈ T (tức là q − ). Trên cung đường này người ta cần phải thực hiện một "hành trình chuyển tiếp" nếu như muốn thực thi hành trình q sau khi đã thực thi hành trình p , bằng chính chiếc xe đã thực hiện hành trình này. Điều này là khả thi khi cặp hai hành trình p, q ∈ T là tương thích. Cụ thể, ta ký hiệu Δp,q ≥ 0 là khoảng thời gian cần thiết để đi từ p + tới q − . Khi Δp,q ≤ sq − ep thì ta nói rằng hai hành trình p và q là tương thích, và khi ấy ta có thể tạo ra một hành trình liên kết (giữa hai hành trình này) có điểm xuất phát là p + (với thời điểm xuất phát là ep ) và điểm kết thúc là q − (với thời điểm kết là sq ). Để thuận tiện cho các lập luận sau này, hành trình liên kết giữa hai hành trình tương thích p và q luôn được xem là tồn tại, ngay cả khi p + = p− (với chi phí có thể là bằng 0). Đại lượng sq − ep được xem là thời gian chờ chuyển tiếp giữa hai hành trình p và q . Khi thời gian này đủ lớn thì khả năng tương thích là dễ xảy ra. Tuy nhiên, trong thực tế, khi đại lượng này là quá lớn thì việc nối hành trình sẽ là không hiệu quả (vì thời gian chờ để nối là quá lâu, đồng nghĩa với thời gian rỗi của xe và tài xế là quá nhiều). Để tránh phải xét các cặp hành trình "tương thích" mà việc nối chúng không có ý nghĩa thực tế, người ta thường chỉ xét những cặp có thời gian chờ chuyển tiếp không vượt quá một giới hạn nào đó được ấn định trước (tùy tình hình thực tế, người ta có thể chọn giới hạn này trong khoảng từ 40 đến 120 phút). Nếu vượt quá giới hạn này thì người ta cho Δp,q = ∞ và xem hai hành trình là không thể kết nối được (điều kiện tương thích không thỏa mãn). - Cung nối điểm nhập bến của trung tâm điều hành d với điểm xuất bến của nó, tức là ( d −, d + ) , được sử dụng để cho xe chạy trở lại điểm xuất bến sau khi đã thực hiện xong một lịch trình và về nhập bến, thường được gọi là cung ngược. Các hành trình trên cung ngược sẽ được gọi là các hành trình nội bộ. Giả thiết về sự tồn tại các các hành trình xuất bến và hành trình nhập bến phù hợp với từng hành trình bắt buộc đã nêu ở trên về bản chất chính là giả thiết về sự tương thích của hành trình nội bộ với các hành trình bắt buộc, từ đó có các hành trình liên kết giữa chúng dưới dạng các hành trình xuất bến và hành trình nhập bến. Tuy rằng trên thực tế có nhiều hành trình nội bộ, nhưng vì chúng giống hệt nhau về mặt bản chất và được "cảm sinh" bởi các hành trình bắt buộc, cho nên ta sẽ chỉ dùng một ký hiệu d0 cho mọi hành trình nội bộ. Một 3
  4. lý do khác là, đối tượng được quan tâm sau này chính là các hành trình liên kết giữa hành trình nội bộ và các hành trình bắt buộc (hay cũng là các hành trình xuất bến, nhập bến) vốn chỉ được xác định bởi các hành trình bắt buộc mà chẳng phụ thuộc gì vào hành trình nội bộ. Số lượng các hành trình nội bộ được thực thi đúng bằng số các hành trình nhập bến (cũng như số các hành trình xuất bến), vì mọi xe sau hành trình nhập bến phải trải qua hành trình trên cung ngược để trở về điểm xuất bến. Các hành trình trên các cung xuất bến, cung nhập bến, cung ngược hay cung liên kết đều không có trong tập các hành trình yêu cầu của nhà quản lý giao thông (không thuộc tập T ), cho nên xe không có trách nhiệm chở khách và vì vậy ta gọi chúng là các hành trình không tải. Như đã nói, để thực hiện được các hành trình bắt buộc, xe không thể tránh được việc phải trải qua một số hành trình không tải, và người làm lịch trình giỏi chính là người biết cách tối thiểu hóa cái phần hành trình không tải này. Khi không cần phân biệt giữa hành trình không tải và hành trình bắt buộc (có tải) thì ta gọi chung chúng là các hành trình. Trong thực tế, khi một xe xuất phát từ trung tâm đi làm việc thì nó phải trải qua một đoạn đường nào đó để đến với điểm đỗ đầu của hành trình bắt buộc cần thực thi đầu tiên, tức là nó phải thực thi một hành trình xuất bến. Sau khi thực thi hành trình bắt buộc, nếu muốn thực thi tiếp một hành trình bắt buộc khác (tương thích với hành trình vừa qua) nó sẽ phải thực thi hành trình liên kết giữa hai hành trình này. Khi thực thi xong hành trình bắt buộc cuối cùng thì xe phải quay trở lại trung tâm, tức là đi từ điểm đỗ cuối của hành trình này về điểm nhập bến của trung tâm, hay cũng chính là thực thi một hành trình nhập bến. Muốn cho xe tiếp tục đi làm việc vào ngày hôm sau thì xe phải thực hiện một hành trình từ điểm nhập bến đến điểm xuất bến của trung tâm, tức là thực hiện một hành trình nội bộ. Một lần quay vòng xe như vậy sẽ được gọi là một lịch trình chạy xe. Dựa vào thực tế nêu trên, ta đưa ra khái niệm lịch trình triển khai là một chuỗi các hành trình liên tiếp kề nhau, trong đó các hành trình không tải và các hành trình bắt buộc được bố trí đan xen nhau, khởi đầu bằng một hành trình xuất bến và kết thúc bằng một hành trình nhập bến. Sau này, để cho gọn, ta cũng thường gọi lịch trình triển khai là lịch trình. Khi một lịch trình được bổ sung thêm hành trình nội bộ thì ta có một chu trình. Lịch trình được xem là hợp lệ, hay là chấp nhận được, khi có ít nhất một hành trình thuộc tập T và tồn tại một trung tâm d có thể phục vụ cho tất cả các hành trình có trong lịch trình này. Mỗi lịch trình như vậy có thể được thực thi bởi một xe của trung tâm đã nói. Sau này, khi nói rằng một hành trình thuộc (hay được phủ bởi) một lịch trình của trung tâm d thì cũng có nghĩa là có một xe của trung tâm d thực thi hành trình đó trong khuôn khổ lịch trình này. Khi ấy ta cũng nói rằng hành trình đó được thực thi theo lịch trình này. Từ đây ta chỉ xét những lịch trình hợp lệ cho nên ta sẽ luôn hiểu lịch trình được đề cập tới là hợp lệ. Mỗi hành trình được gán một trọng số (hay chi phí) phụ thuộc khoảng cách, thời gian đi, loại xe sử dụng,... Trọng số của hành trình liên kết có thể còn tính thêm thời gian chờ của xe, thời gian nghỉ của lái xe. Trọng số của hành trình xuất bến thường có thêm chi phí sử dụng đầu xe, còn trọng số của hành trình nội bộ thường được cho bằng 0. Dựa trên trọng số của các hành trình người ta tính ra chi phí của cả lịch trình. Nhiệm vụ của người điều hành mạng lưới giao thông công cộng là đưa ra được một phương án triển khai dưới dạng một tập các lịch trình triển khai sao cho mỗi hành trình bắt buộc t ∈ T đều được thực thi đúng một lần, tức là đáp ứng đầy đủ yêu cầu của cơ quan quản lý giao thông thành phố. Ngoài ra, người điều hành giỏi thì không chỉ có được phương án triển khai, mà còn tìm được phương án triển khai tốt nhất, theo nghĩa có giá trị hàm tổng chi phí của các lịch trình là cực tiểu. Có thể đặt ra nhiều hàm mục tiêu khác nhau 4
  5. dựa trên cách cho trọng số. Ví dụ, với các hãng vận tải lớn thì mục tiêu chính là sử dụng ít xe nhất có thể. Lý do của việc chọn mục tiêu này là nhằm giảm các chi phí đầu tư lớn vào mua sắm và duy tu, bảo dưỡng các phương tiện giao thông và chi phí lái xe. Với mục tiêu này người ta trường cho trọng số sử dụng đầu xe là đủ lớn. Một mục tiêu khác (thường là đối với các công ty vận tải cỡ nhỏ) là điều hành đội xe hiện có với chi phí vận hành nhỏ nhất. Đồ thị của mạng giao thông công cộng Với mỗi trung tâm điều hành d ∈ D ta định nghĩa các tập sau: - Ad = {( t −, t + ) t ∈ Td } là tập hợp tất cả các cung đường cần thực hiện (đặt ra trong bb kế hoạch của cơ quan quản lý giao thông), có thể được phục vụ bởi trung tâm d . xuat - Ad = { ( d +, t − ) t ∈ Td } là tập hợp tất cả các cung xuất bến (từ trung tâm d ). Tập các hành trình có thể trên các cung này (ứng với các thời điểm khác nhau) được gọi là tập các hành trình xuất bến (của trung tâm d ) và được ký hiệu là Ad −x . ht nhap - Ad = { ( t +, d − ) t ∈ Td } là tập hợp tất cả các cung nhập bến (vào trung tâm d ). Tập các hành trình có thể trên các cung này (ứng với các thời điểm khác nhau) được gọi là tập các hành trình nhập bến (của trung tâm d ) và được ký hiệu là Ad −n . ht - Ad = {( p +, q − ) p, q ∈ Td , ep + Δp,q ≤ sq } là tập hợp tất cả các cung chuyển tiếp lk giữa các cặp hành trình tương thích trong tập Td . Tập các hành trình liên kết (có thể thực hiện trên các cung này) sẽ được ký hiệu là Ad −lk . Lưu ý rằng, giữa hai hành trình ht tương thích chỉ có duy nhất một hành trình liên kết (như đã nói ở trên), còn trên một cung chuyển tiếp có thể có nhiều hành trình liên kết (được thực hiện vào các thời điểm khác nhau). Như vậy, tập các hành trình không tải mà trung tâm d có thể thực hiện là Ad −kt := Ad −x ∪ Ad −n ∪ Ad −lk ∪ {d0 } . ht ht ht ht ht Kết hợp với tập các hành trình bắt buộc Td ta có tập các hành trình ký hiệu là Ad . Nhờ ht có các hành trình liên kết, tập Ad có được tính "kề nhau cục bộ" theo nghĩa là mỗi hành trình p đều có ít nhất một hành trình q kế tiếp cả về vị trí địa lý và thời gian, cụ thể là có p − = q + và ep = sq . Một cặp hành trình như vậy được xem là kề nhau, và khi ấy ta có thể nói p là tiền bối của q hay q là kế cận của p . Tập tất cả các cặp hành trình kề nhau ht ht ht trong Ad sẽ được ký hiệu là Kd (một tập con của Ad × Ad ). Với mỗi hành trình ht p ∈ Ad , ta ký hiệu Kd (p) là tập các hành trình kế cận của p . Để hình dung về cấu trúc mạng giao thông, ta có thể thiết lập đồ thị của nó dựa trên các tập cung đường đã định nghĩa ở trên. Trước hết, ta lập đồ thị của mạng do trung tâm d quản lý, đó là đồ thị có hướng Dd = (Vd , Ad ) , với Vd = {d +, d − } ∪ Td− ∪ Td+ là tập hợp các đỉnh, bb xuat nhap Ad = Ad ∪ Ad ∪ Ad ∪ Ad ∪ ( d −, d + ) là tập hợp các cung của đồ thị. lk Đồ thị của toàn mạng sẽ là hợp của tất cả các đồ thị trên, cụ thể hơn D = (V , A ) , 5
  6. i với V = D + ∪ D − ∪ T + ∪ T − là tập các đỉnh và A = ∪d ∈D Ad là tập các cung. Ở đây i ∪ là ký hiệu của phép hợp tháo rời (disjoint union), theo đó nếu có một cung thuộc nhiều tập thì khi "hợp vào" sẽ thành ra nhiều cung riêng biệt (như có thêm chỉ số chỉ tập chứa nó). Thông thường, người ta thường xây dựng đồ thị cho từng trung tâm riêng. Để cho dễ phân biệt 2 loại hành trình bắt buộc và không tải, người ta thường biểu diễn các hành trình bắt buộc bằng các cung song song với nhau (cùng hướng) và được nối với điểm nhập bến (hay điểm xuất bến) bằng các cung nhập bến (tương ứng, cung xuất bến) trông giống như hình rẽ quạt. Các cung liên kết chính là các cung "nối chéo" từ đuôi hành trình bắt buộc này sang đầu hành trình bắt buộc khác. Đồ thị cho nhiều trung tâm được ghép từ nhiều đồ thị của từng trung tâm độc lập (xem ví dụ trong hình vẽ, trong đó phía bên phải là đồ thị của từng trung tâm r và g , còn ở phía bên trái là đồ thị của toàn mạng với hai trung tâm). Mỗi hành trình bắt buộc t mà có thể được phục vụ bởi nhiều trung tâm (ví dụ như là (a , a + ) ở trong hình vẽ trên) thì sẽ được biểu diễn bởi nhiều cung song song trên đồ thị − toàn mạng D = (V , A ) (với số lượng cung đúng bằng số lượng trung tâm có thể phục vụ cho nó, tức là G (t ) ). 2. Bài toán thiết lập lịch trình vận tải trong mạng giao thông với nhiều trung tâm điều hành Hàm mục tiêu Hàm mục tiêu (hàm chi phí) được thiết lập trên cơ sở nhận xét sau đây. Với mỗi hành trình không tải a ∈ Ad −kt ta cho tương ứng với một trọng số ca ∈ , là chi phí vận ht d hành của hành trình a khi được thực hiện bởi xe của trung tâm d . Thêm vào đó, ta bổ sung vào trọng số của mỗi hành trình xuất bến một số M đủ lớn, biểu thị chi phí đầu tư cho mỗi đầu xe (số M thường lớn hơn chi phí vận hành trên bất cứ hành trình nào). Chi phí trên các hành trình bắt buộc và các cung ngược là cố định, cho nên có thể không cần xét tới trong bài toán tối ưu, nghĩa là có thể cho chúng bằng 0. (Thực ra, đây là một cách "đơn giản hóa", trong đó người ta xem chi phí phục vụ cho một hành trình bắt buộc là không phụ thuộc vào việc chọn trung tâm nào phục vụ cho nó. Trong trường hợp tổng quát thì chi phí cho một hành trình có thể phụ thuộc vào trung tâm phục vụ nó, và do vậy cùng một hành trình nhưng trong các phương án triển khai khác nhau thì có chi phí khác nhau, điều này kéo theo tổng chi phí trên các hành trình bắt buộc trong các phương án khác nhau có thể là không giống nhau. Tuy nhiên, trong tình huống này, người ta có thể dùng cách chuyển chi phí trên mỗi hành trình bắt buộc sang cho các hành trình không tải kế cận, và khi ấy chi phí trên hành trình bắt buộc lại có thể được xem là bằng 0. Ta biết rằng trong một lịch trình thực thi, mỗi hành trình bắt buộc chỉ có đúng một trong số các hành trình không tải kế cận được thực thi cùng với nó, và do vậy chi phí của nó luôn được tính đến, và chỉ một lần, thông qua chi phí của hành trình không tải này). [Lưu ý: Trong tài liệu [10] người ta dùng giải pháp có vẻ đơn giản hơn, đó là chuyển chi phí của hành trình bắt buộc sang cho hành trình nhập bến liền kề với nó (do mỗi hành trình bắt buộc luôn có được một hành trình như vậy tại mỗi trung tâm có thể phục vụ nó). Tuy nhiên, cách này là "không ổn" vì chi phí của hành trình bắt buộc này sẽ bị "mất hút" khi hành trình nhập bến của nó không được thực thi trong lịch trình. Tình huống này thường xảy ra với các hành trình bắt buộc có hành trình kế tiếp là một hành trình liên kết và do đó sẽ không về "nhập bến" qua hành trình nhập 6
  7. bến của chính mình. Khi ấy, trong cả dãy các hành trình bắt buộc và các hành trình liên kết (đan xen nhau) thì chỉ có chi phí của hành trình bắt buộc cuối cùng liền kề với hành trình nhập bến là được tính đến, còn chi phí của các hành trình bắt buộc khác đều bị bỏ qua. Như vậy, chi phí được tính theo cách này đã không phản ánh đúng chi phí thật]. Mô hình toán học Trong thực tế triển khai, chu kỳ lập lịch vận tải của mạng giao thông công cộng trong thành phố thường là một ngày và tập các hành trình bắt buộc đưa ra trong kế hoạch chính là tập các hành trình cần thực hiện trong một ngày. Bài toán đặt ra là thiết lập tập các lịch trình cho mỗi trung tâm điều hành hoạt động trong một ngày. Khái niệm lịch trình đã nêu cho phép loại trừ khả năng lịch trình chỉ gồm có một hành trình duy nhất, vì vậy ta có điều cần lưu ý sau đây. Chú ý 1. Một khi hành trình được thực thi (trong khuôn khổ một lịch trình nào đó) thì phải có ít nhất một trong số các hành trình kề với nó (hoặc là tiền bối hoặc là kế cận của nó) cũng được thực thi (trong cùng lịch trình đó). Một phương án triển khai là một tập hợp các lịch trình, sao cho mỗi hành trình bắt buộc (trong tập T ) phải được thực thi đúng một lần và lịch trình thuộc về trung tâm nào sẽ phải thỏa mãn các ràng buộc đặt ra tại trung tâm đó (thường là về số lượng đầu xe phục vụ). Một phương án triển khai như vậy sẽ được gọi là phương án chấp nhận được. Phương án tối ưu là phương án có tập lịch trình với tổng chi phí thực thi nhỏ nhất trong số các phương án chấp nhận được. Trong một phương án triển khai, việc mỗi hành trình bắt buộc chỉ được thực hiện đúng một lần sẽ kéo theo các hành trình liên kết giữa hai hành trình bắt buộc cũng chỉ được thực thi đúng một lần. Như vậy, trong mỗi lịch trình, kế tiếp cho một hành trình bắt buộc sẽ chỉ có duy nhất một hành trình liên kết. Ngược lại, kế tiếp cho một hành trình liên kết không phải là nhập bến thì chỉ có duy nhất một hành trình bắt buộc. ht Giả sử có một phương án chấp nhận được. Với mỗi d ∈ D và i, j ∈ Ad , người ta d sử dụng biến quyết định Xij để biểu thị việc hai hành trình i, j ở trong cùng một lịch trình d triển khai của trung tâm d và j là kế tiếp của i . Như vậy, ta có X ij = 1 khi và chỉ khi d ( i, j ) ∈ Kd và hai hành trình này cùng thuộc một lịch trình, và có X ij = 0 trong tất cả d các trường hợp còn lại. Ký hiệu C ij là chi phí cho việc thực hiện hành trình j ngay tiếp sau hành trình i . Với khái niệm về trọng số chi phí đã nói ở trên, có thể xem C ij = cid + cd , nhưng lưu ý rằng khi ấy trọng số của mỗi hành trình đều được tính 2 lần vì d j trong chu trình luôn có 2 hành trình liền kề với một hành trình đã cho, bởi vậy để cho hợp lý hơn thì nên nhân thêm hệ số 1/2. Mục tiêu giảm thiểu tổng chi phí là min ∑ ∑ d d C ij Xij . (1) d ∈D ( i, j )∈Kd d Với điều kiện các biến Xij chỉ có thể nhận một trong hai giá trị, 0 hoặc 1, ta thấy rằng điều kiện cần và đủ để một hành trình i ∈ T được thực thi đúng một lần sẽ là: ∑ ht d X ij = 1 , ∀i ∈ T . (2) d ∈D , j ∈Ad 7
  8. Ta biết rằng khi một hành trình bắt buộc j được thực thi (trong một lịch trình) sẽ có đúng một hành trình tiền bối và một hành trình kế cận với nó cùng được thực thi (cùng trong lịch trình đó). Điều kiện này được biểu diễn một cách toán học nhờ mệnh đề sau đây. MỆNH ĐỀ 1. Trong khuôn khổ của các ràng (2), hai điều kiện sau đây là tương đương: (*) Mỗi hành trình bắt buộc j mà được thực thi sẽ luôn có đúng một hành trình tiền bối và một hành trình kế cận với nó cũng được thực thi trong cùng một lịch trình với nó; (**) ∑ ht d X kj − ∑ ht X d = 0 , ∀j ∈ Td , ∀d ∈ D . jk (3) k ∈Ad k ∈Ad Chứng minh. Từ điều (*) ta có ∑ ht d Xkj = ∑ ht X d = 1 , và từ đây suy ra (3). Ta chỉ jk k ∈Ad k ∈Ad còn phải chứng minh điều ngược lại. Do điều kiện (2), với một j ∈ Td chỉ có 2 khả năng xảy ra là: (i) ∑ Xd jk ht =0 , k ∈Ad (ii) ∑ ht Xd = 1. jk k ∈Ad Trường hợp (i) có nghĩa là hành trình j không được thực thi trong cùng một lịch trình với bất cứ một hành trình nào kế cận với nó (mà thuộc về trung tâm d ). Từ (i) và điều kiện (3) lại suy ra ∑ X d = 0 , và điều này có nghĩa là không có hành trình nào jk ht k ∈Ad trong số các tiền bối của j (mà thuộc miền phục vụ của d ) có thể được thực thi trong cùng lịch trình với nó. Như vậy bản thân hành trình j không thể được thực thi (bởi trung tâm d ) vì nếu ngược lại thì phải có ít nhất một trong các hành trình liền kề với nó được thực thi, như đã nói trong Chú ý 1. (Lưu ý rằng việc j không được thực thi bởi trung tâm d là không có gì mâu thuẫn với việc j ∈ Td và phải được thực thi 1 lần, bởi vì Td chỉ là tập hành trình mà d có thể phục vụ, chứ không phải là tập hành trình mà d buộc phải thực thi.) Trường hợp (i) có nghĩa rằng tồn tại duy nhất một hành trình k0 là kế cận của j được thực thi cùng với nó, và khi ấy điều kiện (3) kéo theo ∑ Xkj = 1 , tức là sẽ có duy d ht k ∈Ad nhất một hành trình k1 là tiền bối của j và được thực thi cùng với nó. Mệnh đề đã được chứng minh. Số lượng xe được sử dụng tại trung tâm đúng bằng số các hành trình xuất bến được thực thi, tức là bằng ∑ Xd0 j . Do đó, ràng buộc về số lượng xe sử dụng tại mỗi trung d j ∈Ad −x ht tâm được thể hiện như sau: λd ≤ ∑ d Xd0 j ≤ κd , ∀d ∈ D . (4) j ∈Ad −x ht Điều kiện nguyên 0 hoặc 1 của biến quyết định được viết lại là d ht X ij ∈ { 0,1 }, ∀ d ∈ D, ∀i, j ∈ Ad . (5) 8
  9. Như vậy, một phương án triển khai là chấp nhận được thì các điều kiện (2)-(5) phải được thỏa mãn. Bài toán tìm phương án tối ưu chính là bài toán tìm phương án chấp nhận được với hàm chi phí (1) nhỏ nhất, tức là có thể được mô tả bởi (1)-(5). Sau này, để cho gọn, ta sẽ gọi nó là Bài toán (MD). Như trên ta thấy, với mỗi phương án chấp nhận được, bằng việc sử dụng biến d quyết định, ta có thể tạo ra một vectơ X = (X ij )d ∈D,i, j ∈Aht thỏa mãn các ràng buộc (2)- d (5). Điều ngược lại cũng đúng, nhờ mệnh đề sau. MỆNH ĐỀ 2. Từ vectơ các giá trị biến quyết định thỏa mãn các điều kiện (2)-(5) ta có thể thiết lập được một phương án triển khai chấp nhận được (cũng tức là một tập lịch trình chấp nhận được). Chứng minh. Tập hợp các hành trình được thực thi trong lịch trình sẽ được xác định thông qua tập các tọa độ vectơ nhận giá trị bằng 1. Tập các hành trình này được phân bổ về các trung tâm dựa theo chỉ số d . Từ tập các hành trình của mỗi trung tâm, ta sẽ xác định ra các lịch trình cho trung tâm đó, một cách duy nhất bởi các điều kiện (2), (3) và (5). Thật vậy, lấy một hành trình bắt buộc a ∈ T và, theo điều kiện (2), ta tìm được duy nhất ht d một trung tâm d và một hành trình j ∈ Ad sao cho Xaj = 1 . Điều này cũng có nghĩa j là kế cận của a và được thực thi trong cùng lịch trình với a . Như đã nói, Điều kiện (3) có nghĩa là tồn tại duy nhất một hành trình l là tiền bối của a và được thực thi trong cùng lịch trình với a . Lặp lại quá trình tương tự như vậy với cả l và j ta sẽ tìm ra các hành trình tiền bối của l và kế cận của j cùng ở trong một lịch trình với a . Cứ tiếp tục quá trình này cho đến khi ta gặp một hành trình nhập bến và một hành trình xuất bến. Điều này có nghĩa là ta đã tìm ra một lịch trình chứa hành trình a đã nêu. Ta ký hiệu lịch trình này là La . Tiếp tục, lấy một hành trình b khác trong tập T (nằm ngoài lịch trình La vừa nói), và làm tương tự như trên ta sẽ tìm ra một lịch trình Lb khác. Điều kiện (2) cho thấy rằng các lịch trình này không thể có chung một hành trình. Vì tập T là hữu hạn cho nên sau một số lần hữu hạn ta sẽ vét hết tập T và có nghĩa là tìm ra tất cả các lịch trình. Mệnh đề được chứng minh xong. Sử dụng một biến quyết định khác ht Vì tập các hành trình Ad là lớn gấp bội so với tập các hành trình bắt buộc Td , cho nên kích thước bài toán sẽ nhỏ hơn nhiều nếu như biến i, j chỉ chạy trên tập Td , thay vì trên ht tập Ad . Trên thực tế, việc một hành trình liên kết k được thực hiện sau hành trình bắt buộc i luôn kéo theo một hành trình bắt buộc j nào đó sẽ được thực hiện ngay sau hành trình k . Về bản chất, điều này có thể xem như là hành trình bắt buộc j được thực hiện tiếp sau hành trình bắt buộc i thông qua hành trình liên kết k , và do vậy có thể xem k được sinh ra như một hệ quả của việc thực hiện hai hành trình bắt buộc i, j kế tiếp nhau (khi chỉ xét trên tập Td ). Vì hành trình liên kết k được xác định một cách duy nhất từ cặp hành trình tương thích i, j ∈ Td , cho nên ta có thể quy ước rằng khi nói "hai hành trình i, j ∈ Td được thực hiện kế tiếp nhau trong cùng một lịch trình" là có nghĩa hành trình liên kết giữa chúng cũng được thực hiện trong khuôn khổ của lịch trình đó. Như đã nói, hành trình xuất bến (hay nhập bến) cũng có thể được xem như là hành trình liên kết giữa hành trình bắt buộc và hành trình nội bộ d0 và do vậy cũng được xác định từ cặp gồm một hành trình bắt buộc và một hành trình nội bộ. 9
  10. Các phân tích trên cho thấy rằng ta có cơ sở để "bỏ qua" tập các hành trình liên kết cũng như hành trình xuất bến và hành trình nhập bến, mà chỉ đặt biến quyết định trên tập các hành trình còn lại, tức là tập Td := Td ∪ {d0 } . Cụ thể, với một phương án triển khai d cho trước và với i, j ∈ Td , ta có X ij = 1 khi và chỉ khi cặp hành trình (i, j ) là tương thích và cùng ở trong một lịch trình của trung tâm d trong phương án triển khai này. Tương tự như đối với cặp hành trình kề nhau, với cặp hành trình tương thích (i, j ) ta cũng gọi i là tiền bối của j và gọi j là kế cận của i . Theo quy ước về sự tồn tại các cung xuất bến bà các cung nhập bến, hành trình nội bộ được xem là tiền bối của mọi hành trình bắt buộc và cũng là kế cận của mỗi hành trình này. Trong cách xem xét mới, nếu không kể hành trình nội bộ, thì lịch trình là một dãy các hành trình bắt buộc liên tiếp kế cận nhau, mà về bản chất cũng chính là tập các hành trình bắt buộc trong một lịch trình theo nghĩa trước đây, cho nên đôi khi ta sẽ gọi nó là lịch trình thu gọn. Khi bổ sung thêm hành trình nội bộ vào một lịch trình thu gọn thì ta được một chu trình thu gọn. Như vậy, trong một chu trình thu gọn thì mọi hành trình bắt buộc đều có tiền bối và kế cận của mình. Chi phí cho quá trình thực hiện hành trình j tiếp theo hành trình i có thể được xem là chi phí cho hành trình liên kết trên cung liên kết nối hai hành trình i, j và sẽ được ký d hiệu là C ij . Như đã nói ở trên, nó có thể bao hàm cả chi phí của hành trình i (khi ta muốn chuyển chi phí từ hành trình bắt buộc sang cho các hành trình không tải). Khi i = d 0 thì d Cd0 j chính là chi phí của hành trình xuất bến. Như đã nói, nó thường bao hàm cả chi phí thực tế trên cung xuất bến lẫn trọng số sử dụng đầu xe (để điều tiết số lượng xe sử dụng tại trung tâm đang xét: khi trọng số này càng lớn thì kết quả cho số đầu xe sử dụng càng ít). Bây giờ, mục tiêu giảm thiểu tổng chi phí triển khai sẽ là min ∑ ∑ C ij Xij . d d (6) d ∈D i, j ∈Td d Với điều kiện các biến Xij chỉ có thể nhận một trong hai giá trị, 0 hoặc 1, ta thấy rằng điều kiện cần và đủ để một hành trình i ∈ T được thực thi đúng một lần sẽ là: ∑ d Xij = 1 , i ∈ T . (7) d ∈D, j ∈Td Như đã nói ở trên, mỗi hành trình bắt buộc ở trong một chu trình (thu gọn) nào đó đều có hành trình kế cận và hành trình tiền bối ở trong chu trình này. Trong khuôn khổ của ràng buộc (7), lập luận như trong Mệnh đề 1, ta biết điều này được thể hiện như sau ∑ Xkj − ∑ X d d jk = 0 , ∀j ∈ Td , ∀d ∈ D . (8) k ∈Td k ∈Td Lưu ý rằng, số lượng xe đi phục vụ tại một trung tâm phải bằng số hành trình xuất bến được thực thi, được tính bằng ∑ Xd0k , và cũng phải bằng số lượng hành trình nhập d k ∈Ad −x ht bến được thực thi, tức là bằng ∑ d Xkd0 , cho nên điều kiện (8) cũng được thỏa mãn tại k ∈Ad −n ht d0 , tức là với mọi j ∈ Td . Ràng buộc về số lượng xe sử dụng tại mỗi trung tâm được thể hiện như sau: 10
  11. λd ≤ ∑ d Xd0 j ≤ κd , ∀d ∈ D . (9) j ∈Ad −x ht Tóm lại, bài toán tìm tập lịch trình tối ưu với các ràng buộc đã nêu có thể được mô tả bởi (6) - (9) kết hợp với điều kiện nguyên 0 hoặc 1 của biến quyết định, tức là d X ij ∈ { 0,1 }, ∀ d ∈ D, ∀i, j ∈ Td . (10) Sau này, để cho gọn, ta sẽ gọi nó là Bài toán (MD1). Tương tự như trên, ta có mệnh đề sau. MỆNH ĐỀ 3. Với mỗi phương án triển khai chấp nhận được, ta có vectơ giá trị biến quyết d định X = (Xij )d ∈D,i, j ∈Td thỏa mãn các điều kiện (7)-(10). Ngược lại, từ mỗi vectơ giá trị d biến quyết định X = (Xij )d ∈D,i, j ∈Td thỏa mãn các điều kiện (7)-(10) ta có thể thiết lập được một phương án triển khai chấp nhận được. Chứng minh. (Tương tự như chứng minh Mệnh đề 2) Chú ý 2. Từ các Mệnh đề 2-3 ta thấy rằng việc tìm phương án triển khai tối ưu được quy về việc giải bài toán (MD) hoặc (MD1). 3. Độ phức tạp của bài toán và giải pháp khả thi trong thực tiễn Nhận xét về độ phức tạp của bài toán Khi áp dụng vào thực tế của một thành phố lớn, bài toán quy hoạch nguyên (MD) có thể đạt tới hàng chục triệu biến với hàng trăm nghìn ràng buộc. Người ta đã chứng minh rằng, trong trường hợp tổng quát với hơn một trung tâm điều hành, các bài toán (MD) và (MD1) nêu trên là thuộc lớp NP-khó (xem [2]). Ngay cả bài toán tìm nghiệm tối ưu xấp xỉ ε cũng đã là NP-khó. Ngoài ra, người ta còn chỉ ra rằng bài toán tìm phương án chấp nhận được cho bài toán này khi có ràng buộc về dung lượng của các trung tâm cũng đã là NP đầy đủ. Đây chính là lý do vì sao bài toán này, mặc dù đã được rất nhiều người quan tâm nghiên cứu (xem [2, 3, 5, 6, 8, 9, 10, 11,...]) nhưng, cho đến nay, vẫn chưa có được lời giải trọn vẹn. Một số giải pháp thực tiễn Như đã nói ở trên, việc tìm lời giải chính xác cho bài toán quy hoạch nguyên (MD) là không khả thi trong thực tiễn. Trong tình huống như thế này người ta có thể nghĩ tới một trong số những giải pháp siêu cảm tính đang ngày càng thể hiện tính hiệu quả trong thực tiễn triển khai (xem [6], [11],... và các tài liệu trong đó), hoặc tìm cách đơn giản hóa bài toán (dựa trên các điều kiện thực tế cho phép), để hy vọng có được một lời giải đủ tốt thay vì đi tìm kiếm một lời giải tối ưu chính xác theo lý thuyết mà việc tính toán là không khả thi. Ở đây, chúng tôi đề xuất một cách "đơn giản hóa" bài toán, làm cho nó trở nên dễ giải hơn, và đồng thời lời giải thu được vẫn có được ý nghĩa thực tiễn rõ rệt. Đơn giản hóa điều kiện ràng buộc Việc có nhiều chủng loại xe tham gia hoạt động trên cùng một mạng giao thông công cộng là thực tế hiện hữu, và thậm chí là không tránh khỏi. Tuy nhiên việc đưa thêm tập G (t ) và các tập ràng buộc liên quan tới nó như Td sẽ làm cho bài toán phức tạp lên rất nhiều. Có lẽ ta nên tránh sự "phức tạp hóa" này bằng cách giả thiết sử dụng một chủng loại xe (loại phổ 11
  12. biến nhất). Sau khi giải xong bài toán, người quản lý có thể dùng phép "quy đổi" sang chủng loại xe khác trên một số tuyến đường cụ thể, kèm theo việc tăng hay giảm tần suất chạy xe sao cho phù hợp với lưu lượng hành khách cần phục vụ. Thông thường, việc "quy đổi" là không "tương đương", cho nên giải pháp này không bảo toàn "tính tối ưu" của lời giải. Tuy nhiên, nếu việc "quy đổi" là hợp lý thì lời giải cũng có thể chấp nhận được về mặt thực tiễn. Trong điều kiện đồng nhất về chủng loại xe thì chi phí trên các hành trình không còn phụ thuộc vào đặc thù kỹ thuật tại trung tâm điều hành, mà chỉ còn phụ thuộc vào quãng đường chạy xe, hay quy đổi tương đương thành ra thời gian xe chạy trên các hành d trình. Như vậy, có thể xem như chi phí C ij sẽ không còn phụ thuộc vào d mà chỉ còn phụ thuộc vào thời gian đi từ điểm cuối hành trình i đến điểm đầu của hành trình j , và theo cách chuyển chi phí ra khỏi các hành trình bắt buộc thì C ij sẽ bao hàm cả thời gian xe chạy trên hành trình i , ký hiệu là hi . Như vậy, cặp hai hành trình bắt buộc i, j sẽ là tương thích nếu như si + hi ≤ s j . Tập các cặp hành trình như vậy sẽ được gọi là tập các cặp hành trình tương thích, không còn phụ thuộc vào trung tâm điều hành, và cũng là tập các hành trình liên kết giữa các cặp hành trình tương thích (đương nhiên ta vẫn có quyền loại bỏ các cặp "tương thích vô dụng" bằng một điều kiện phụ như đã nhận xét ở trên). Vì các xe là như nhau, cho nên tập Td cũng là như nhau (và trùng với T ), còn các tập G (t ) cũng không còn phụ thuộc vào t (và luôn bằng D ). Bây giờ, với mỗi trung tâm điều hành d ∈ D , ta có các tập sau: - Ad −lk = Aht −lk , ht ∀d ∈ D . - Ad −kt = Ad −x ∪ Ad −n ∪ Aht −lk ∪ {d0 } , Ad = T ∪ Ad −kt . ht ht ht ht ht Đồ thị của trung tâm d là Dd = (Vd , Ad ) có các tập đỉnh và cung như sau Vd' = {d +, d − } ∪ T − ∪ T + , Ad = Ad ∪ ( d −, d + ) . ht Bây giờ Bài toán (MD) được viết lại thành bài toán sau đây ∑ ∑ ht d C ij Xij → min d ∈D i, j ∈Ad với ràng buộc ∑ Xij = 1 , ∀i ∈ T , d ht d ∈D, j ∈Ad (MD*) ∑ ht d Xij − ∑ ht X d = 0 , ∀j ∈ Td , ∀d jk ∈D. i ∈Ad k ∈Ad λd ≤ ∑ ht −x d Xd0 j ≤ κd , ∀d ∈ D , j ∈Ad d ht Xij ∈ { 0,1 }, ∀i, j ∈ Ad , ∀d ∈ D , ht d trong đó, với i, j ∈ Ad , biến quyết định Xij cho biết hành trình j có là kế cận của hành trình i và cùng ở trong một lịch trình của trung tâm d hay không. Tương tự như vậy, với ký hiệu Td = T ∪ {d0 } , ta có thể viết lại Bài toán (MD1) dưới dạng sau đây 12
  13. ∑ ∑ C ij Xij d → min . d ∈D i, j ∈Td với ràng buộc ∑ d Xij = 1 , i ∈ T . d ∈D, j ∈Td (MD1*) ∑ Xkj − ∑ X d d jk = 0 , ∀j ∈ Td , ∀d ∈ D . k ∈Td k ∈Td λd ≤ ∑ d Xd0 j ≤ κd , ∀d ∈ D . j ∈Ad −x ht d Xij ∈ { 0,1 }, ∀d ∈ D, ∀i, j ∈ Td . d trong đó, với i, j ∈ Td , biến quyết định Xij cho biết cặp hành trình bắt buộc (i, j ) có là tương thích và được thực thi trong cùng một lịch trình của trung tâm d hay không. Phân rã thành 2 bài toán đơn giản hơn Ta biết rằng chi phí không sinh lợi chỉ phát sinh trên tập các hành trình không tải, bao gồm 2 loại: các hành trình liên kết (giữa các hành trình bắt buộc) và các hành trình xuất hay nhập bến (mà ta đôi khi gọi gộp là các hành trình xuất-nhập bến). Ta có thể "đơn giản hóa" bằng cách xem như hai loại chi phí này ít phụ thuộc lẫn nhau, và do vậy trước hết ta xét vấn đề cực tiểu hóa chi phí trên các hành trình xuất - nhập bến (việc cực tiểu hóa các chi phí trên các hành trình liên kết sẽ được đề cập trong bước tiếp theo). Trước hết, ta ghép các hành trình bắt buộc có chung điểm đầu và điểm cuối thành một cụm hành trình (mà về bản chất cũng giống như là một cung như đã định nghĩa ở trên). Với mỗi cụm hành trình như vậy ta cho ứng với một cung xuất bến và gán cho một trọng số chi phí bằng số lượng các hành trình trọng cụm này (Chính xác hơn thì có thể lấy bằng số lượng các hành trình xuất bến có thể sinh ra cho các hành trình trong cụm này). Số các hành trình này nói chung là nhỏ hơn số hành trình trong cụm, và thường chỉ phát sinh với các hành trình có thời gian xuất phát vào buổi đầu giờ sáng. Nó có thể tính được một cách xấp xỉ bằng số lượng các hành trình có thời điểm xuất phát trước khi chiếc xe đi thực hiện hành trình đầu tiên trong cụm có đủ thời gian quay trở về điểm đầu (để thực hiện vòng hành trình mới). Dựa vào các cung xuất bến và các trọng số chi phí này (kết hợp với chi phí thực tế trên từng cung có từ dữ liệu ban đầu) ta tính được chi phí cho các tuyến chạy xe giả lập, mỗi tuyến khởi đầu bằng một cung xuất bến, một cụm hành trình và một cung nhập bến. Từ đây, theo mô hình bài toán phân bổ các tuyến chạy xe về cho các trung tâm điều hành đã được xét trong [12], ta tìm ra cách phân bổ tối ưu các tuyến giả lập về cho các trung tâm điều hành, mà trên thực tế cũng chính là cách phân các cụm hành trình về cho các trung tâm. Đây chính là Bài toán thứ 1, và từ kết quả giải nó ta có được tập những hành trình bắt buộc được phân về cho từng trung tâm (bằng cách lấy hợp của tất cả các hành trình trong các cụm được phân về trung tâm). Bây giờ ta có bài toán lập lịch trình tối ưu phủ hết các hành trình bắt buộc của từng trung tâm điều hành riêng biệt (có cả thảy D bài toán như vậy, và có thể được xử lý song song một cách tự nhiên). Ở đây, ta cần giải bài toán thiết lập lịch trình tối ưu cho mạng giao thông chỉ với một trung tâm điều hành. Đây chính là Bài toán thứ 2, là một trường hợp riêng của bài toán tổng quát đã nêu và dễ giải hơn hẳn (như sẽ thấy trong phần trình bày tiếp theo). Lời giải của mỗi bài toán này chính là lịch trình cho từng trung tâm điều hành (dưới dạng một tập hợp các lịch trình). Tập hợp các lịch trình thu được sau việc giải D bài toán trên cho ta một lời giải chấp nhận được của bài toán tổng quát ban đầu, vì rằng tất cả các hành trình bắt buộc đều đã được phân bổ 13
  14. về cho các trung tâm (theo Bài toán thứ nhất), và mỗi hành trình chỉ được thực hiện đúng một lần (theo Bài toán thứ hai). Quá trình làm tốt thêm nhờ các vòng lặp Lời giải nói trên có thể đã là tốt về mặt thực tiễn (nhờ hai lần thực hiện phép cực tiểu hóa) nhưng nói chung chưa phải là lời giải tối ưu theo lý thuyết, và do vậy có khả năng "làm tốt thêm". Cụ thể, với tập lời giải chấp nhận được đã nói ở trên, với mỗi lịch trình đóng vai trò một tuyến xe, ta thực hiện việc tái phân bổ các tuyến về cho các trung tâm (tức là giải Bài toán thứ 1 như đã xét trong [12]). Lời giải của bài toán này sẽ là một cách phân bổ mới cho các tuyến về các trung tâm, nói chung là khác trước và cho giá trị hàm mục tiêu tốt hơn (do quá trình làm cực tiểu hóa khi tái phân bổ). Lời giải nêu trên không làm thay đổi cấu trúc của các lịch trình, mà chỉ thay đổi trung tâm điều hành nó. Điều này có nghĩa là tập các hành trình bắt buộc được "phủ" bởi từng trung tâm đã được thay đổi. Nói cách khác, nếu cho "phân rã" các lịch trình mới được phân về từng trung tâm và lấy lại tập các hành trình bắt buộc có trong các lịch trình này, ta sẽ có dữ liệu mới cho bài toán thiết lập tập lịch trình tối ưu (cho từng trung tâm riêng biệt). Nếu giải bài toán này ta sẽ nhận được kết quả là một lời giải tốt hơn hẳn phương án trước khi phân rã (vì nó sẽ là lời giải tối ưu thực sự cho bài toán với một trung tâm, trong khi phương án trước khi phân rã chỉ là một phương án chấp nhận được mà thôi). Như vậy qua một vòng lặp gồm hai bước, ta nhận được kết quả mới với chất lượng tốt hơn. Quy trình nêu trên có thể được lặp đi lặp lại nhiều lần, và sau mỗi vòng lặp kết quả sẽ được cải thiện. Tuy nhiên, như đã nói từ đầu, việc thực hiện thêm vòng lặp chỉ có ý nghĩa khi kết quả vòng sau thực sự tốt hơn đáng kể so với vòng trước. Việc thực hiện liên tiếp nhiều vòng lặp chỉ có thể được áp dụng khi ta thiết lập mới hay tiến hành "cải tổ" mạng giao thông một cách toàn diện (chỉ một lần trong khoảng thời gian rất dài). Trong thực tế triển khai, người ta không nhất thiết phải áp dụng cả một vòng với 2 bài toán như trên, vì kết quả nhận được sau một vòng tính toán sẽ gây xáo trộn lớn đối với mạng giao thông. Việc tái phân bổ tuyến cho các trung tâm điều hành (theo Bài toán thứ nhất) chỉ ảnh hưởng đến các nhà quản lý giao thông, mà không gây ảnh hưởng nhiều đến người sử dụng, do các tuyến vẫn giữ nguyên cấu trúc các lịch trình cần phục vụ. Việc tái thiết lập các lịch trình cho một trung tâm kéo theo việc tái cấu trúc lại các tuyến chạy xe của trung tâm đó, cho nên không chỉ làm thay đổi công tác quản lý tại trung tâm (do số lượng lịch trình có thể thay đổi), mà còn gây ảnh hưởng lớn đến cư dân sử dụng (vì làm thay đổi lịch trình các tuyến xe mà họ đã biết sau một thời gian dài quen đi). Tuy nhiên, khi dữ liệu thay đổi không quá nhiều, có thể hi vọng rằng những thay đổi trong phạm vi của một trung tâm cũng không nhiều, và do vậy giải pháp thu được sau tính toán vẫn có thể là khả thi. Khi áp dụng cả 2 bài toán, dữ liệu đầu vào của Bài toán thứ 2 sẽ được kết xuất từ kết quả của Bài toán thứ nhất, nói chung là bị xáo trộn nhiều, và kết quả giải ra sẽ là những thay đổi "toàn diện" khó lường trước, cho nên thường là khó khả thi. Việc giải bài toán tối ưu tổng thể (MD) về thực chất cũng sẽ dẫn đến tình huống này, cho nên phương án tìm được cũng khó khả thi. Chính vì vậy, giải pháp mà chúng tôi đề xuất cho mỗi lần cải tiến mạng là chỉ nên giải một trong hai bài toán nêu trên. Nhu cầu giải Bài toán thứ 1 sẽ phát sinh sau một thời gian dài sử dụng có một số tuyến nào đó được "cấy" thêm vào mạng do nhu cầu đi lại của dân cư trong thực tiễn, hoặc do sự xuất hiện của một trung tâm điều hành mới. Nhu cầu giải Bài toán thứ 2 sẽ phát sinh có thêm nhiều hành trình bắt 14
  15. buộc mới được bổ sung vào trung tâm hoặc chuyển sang cho trung tâm khác (một trong những nguyên nhân có thể là kết quả của việc giải Bài toán thứ 1). Bài toán lập lịch trình cho mạng giao thông với một trung tâm điều hành Khi chỉ có duy nhất một trung tâm điều hành thì chỉ số d có thể loại bỏ và từ Bài toán (MD*) ta có bài toán sau đây min ∑ C ij Xij i, j ∈Aht với các ràng buộc ∑ Xij = 1 , ∀i ∈ T , j ∈Aht (SD) ∑ Xij − ∑ X jk = 0 , ∀i ∈ Aht , j ∈Aht k ∈Aht λ≤ ∑ Xi0 j ≤ κ , j ∈Aht −x Xij ∈ { 0,1 }, ∀i, j ∈ Aht , trong đó Aht là tập tất cả các hành trình, Aht −x là tập các hành trình xuất bến, còn Xij là biến quyết định và nhận giá trị bằng 1 khi và chỉ khi cặp hành trình (i, j ) là kề nhau và được thực thi trong cùng một lịch trình. Tương tự như vậy, với ký hiệu T = T ∪ {d0 } , từ bài toán (MD1*) ta có bài toán sau đây: ∑ Cij Xij → min . i, j ∈T với ràng buộc ∑ Xij = 1, i ∈ T . j ∈T (SD1*) ∑ Xkj − ∑ X jk = 0 , ∀j ∈ T . k ∈T k ∈T λ ≤ ∑ Xd0 j ≤ κ . j ∈Aht −x Xij ∈ { 0,1 }, ∀i, j ∈ T . trong đó Xij là biến quyết định và nhận giá trị bằng 1 khi và chỉ khi cặp hành trình (i, j ) là tương thích và được thực thi trong cùng một lịch trình. Bài toán này đã được giải quyết trọn vẹn bằng những thuật toán với thời gian đa thức, thông qua việc chuyển nó về bài toán phân bổ, hoặc bài luồng cực tiểu trên mạng rồi giải bằng thuật toán Hungary hoặc thuật toán đấu giá (Auction Algorithm). Chi tiết có thể xem trong các công trình [1], [7],.... và các tài liều dẫn trong đó. 15
  16. TÀI LIỆU DẪN [1] Ahuja R.K., Magnanti T.L., Orlin J.B., Network Flows: Theory, Algorithms and Applications, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1993. [2] Bertossi A.A., Carraresi P., Gallo G., On some matching problems arising in vehicle scheduling models, Networks, 17 (1987), pp. 271-281. [3] Bianco L., Mingozzi A., Ricciardelli S., A set partitioning approach to the multiple-depot vehicle scheduling problem, Optimization: Methods and Software, 7 (1994), pp. 163-194. [4] Bokinge U., Hasselstrom D., Improved vehicle scheduling in public transport through systematic changes in the time-table, European Journal of Operational Research, 5 (1980), pp. 388-395. [5] Branco I., Costa A., Paixão J., Vehicle scheduling problem with multiple type of vehicles and a single depot, in Daduna, Branco and Paixão [1995], pp. 115-129. [6] Dell'Amico M., Fischetti M., Toth P., Heuristic algorithms for multiple depot vehicle scheduling problem, Management Science, N1, Vol. 39 (1993), pp. 115-125. [7] Freling R., Wagelmans A., Paixão J., Models and Algorithms for Single-Depot Vehicle Scheduling, Transportation Science, Vol. 35, No. 2, 2001, pp. 165–180. [8] Kokott A., Loebel A., Lagrangean relaxation and subgradient methods for multiple-depot vehicle scheduling problem, http://www.zib.de. [9] Larsen A., Madsen O.B.G., Solving the multiple vehicle scheduling problem in a major scandinavian city, Technical Report IMM-REP-1997-10, Technical University of Denmark. [10] Loebel A., Optimal Vehicle Scheduling in Public Transit, (PhD Thesis), 1997. [11] Mesquita M., Paixão J., Multiple-depot vehicle scheduling problem: A new heuristic based on quasi-assignment algorithms, in Desrochers and Rousseau (eds), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematicals Systems 386, Springer Verlag, Berlin, Heidelberg, 1992, pp.181-195. [12] Phạm Xuân Hinh, Nguyễn Quang Minh, Phân bổ hợp lý các trung tâm điều hành của mạng lưới xe buýt thành phố Hà Nội, Tạp chí Ứng Dụng Toán Học, Số 1, Tập IV, năm 2006, tr. 37-44. A PRACTICAL APPROACH TO THE MULTIPLE-DEPOT VEHICLE SCHEDULING PROBLEM ABSTRACT. We consider the multiple-depot vehicle scheduling problem for public transport networks and propose a practical approach to the solution of the problem, which based on the decomposition method and an iterative procedure. Each iteration round consists of two solvable optimization problems. 16

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản