AlphaTransit: Khi AI thiết kế mạng lưới xe buýt cho cả thành phố

Mình vừa đọc xong một paper khá thú vị trên HuggingFace Daily Papers AlphaTransit: Learning to Design City-scale Transit Routes. Nói thật, ban đầu mình tưởng đây lại là một bài routing optimization kiểu giải Travelling Salesman Problem (TSP) bằng neural network như mấy năm trước, nhưng đọc kỹ thì nó khác hoàn toàn. Bài toán ở đây không phải tìm đường đi ngắn nhất cho một xe, mà là thiết kế toàn bộ mạng lưới tuyến xe buýt cho một thành phố từ việc quyết định có bao nhiêu tuyến, mỗi tuyến đi qua những trạm nào, tần suất ra sao, sao cho tổng thể phục vụ được nhiều người nhất với chi phí hợp lý nhất.

Nếu bạn từng sống ở Hà Nội hay TP.HCM và tự hỏi "tại sao tuyến xe buýt này đi vòng vèo thế nhỉ" thì đây, bài toán thiết kế transit route chính là thứ đứng sau những quyết định đó.

Bài toán Transit Network Design khó hơn bạn nghĩ rất nhiều

Mình muốn giải thích rõ hơn tại sao bài toán này lại khó đến mức cần đến reinforcement learning (RL). Khi bạn thiết kế mạng lưới xe buýt cho một thành phố, bạn phải đối mặt với một combinatorial explosion kinh khủng. Giả sử thành phố có 500 trạm dừng tiềm năng và bạn cần thiết kế 30 tuyến, mỗi tuyến đi qua khoảng 15-25 trạm. Số lượng cách chọn và sắp xếp là... vô hạn thực tế.

Nhưng đó chưa phải vấn đề chính. Cái khó thật sự là feedback loop: khi bạn thay đổi một tuyến, hành vi của hành khách trên TOÀN BỘ mạng lưới thay đổi theo. Người ta sẽ chuyển tuyến, đi bộ sang trạm khác, hoặc thậm chí bỏ xe buýt luôn nếu quá bất tiện. Tức là bạn không thể tối ưu từng tuyến độc lập mọi thứ phụ thuộc lẫn nhau.

Các phương pháp truyền thống thường dùng metaheuristics như genetic algorithm, simulated annealing, hay tabu search. Chúng hoạt động, nhưng cực kỳ chậm và không scale được. Một lần chạy cho thành phố trung bình có thể mất hàng giờ đến hàng ngày, và mỗi lần thay đổi demand data (ví dụ dân số thay đổi, có khu đô thị mới) thì phải chạy lại từ đầu.

AlphaTransit tiếp cận vấn đề như thế nào

Ý tưởng cốt lõi của AlphaTransit là frame bài toán thiết kế mạng lưới transit thành một sequential decision-making problem và dùng RL agent để giải. Cụ thể hơn, agent sẽ xây dựng mạng lưới tuyến theo kiểu step-by-step: mỗi bước, nó chọn thêm một trạm vào tuyến hiện tại, hoặc quyết định kết thúc tuyến đó và bắt đầu tuyến mới.

Điều mình thấy hay ở đây là cách họ encode thông tin. Mạng lưới giao thông của thành phố được biểu diễn dưới dạng graph, với các node là trạm dừng và edge là đường nối giữa chúng. Agent nhận vào state bao gồm:

• Graph representation của mạng lưới đường phố (topology)
• Origin-Destination (OD) demand matrix ma trận nhu cầu đi lại giữa các cặp điểm
• Trạng thái hiện tại của các tuyến đã được xây dựng
• Tuyến đang xây dựng dở agent đang ở trạm nào, đã đi qua những đâu

Reward function thì được thiết kế để cân bằng giữa hai mục tiêu thường xung đột nhau: tối đa hóa coverage (phục vụ được nhiều hành khách nhất) và tối thiểu hóa chi phí vận hành (tổng chiều dài tuyến, số xe cần thiết). Đây chính là trade-off kinh điển trong quy hoạch giao thông bạn muốn phủ sóng rộng thì tốn tiền, muốn tiết kiệm thì bỏ sót nhiều người.

Một điểm kỹ thuật đáng chú ý là họ tích hợp một transit assignment model vào trong training loop. Tức là sau mỗi lần agent đề xuất một mạng lưới, hệ thống sẽ simulate hành vi của hành khách trên mạng lưới đó ai đi tuyến nào, chuyển tuyến ở đâu, thời gian di chuyển tổng cộng bao lâu. Kết quả simulation này mới được dùng để tính reward. Nghe đơn giản nhưng implement thì khá phức tạp vì transit assignment bản thân nó đã là một bài toán optimization con.

So sánh với các approach khác trong cùng domain

Để bạn có cái nhìn rõ hơn, mình tổng hợp lại các approach phổ biến cho bài toán Transit Network Design Problem (TNDP):

Điểm mạnh rõ ràng nhất của approach RL như AlphaTransit là amortized computation: bạn tốn thời gian training một lần, nhưng sau đó inference cho thành phố mới (hoặc cùng thành phố với demand thay đổi) thì cực nhanh. Với các phương pháp metaheuristic, mỗi instance mới là phải giải lại từ đầu.

Mình cũng chú ý thấy trong phần related papers mà Librarian Bot recommend, có TransitLM một paper dùng LLM để generate transit route. Hai hướng này khá khác nhau: AlphaTransit dùng RL thuần với graph neural network, còn TransitLM thì leverage language model. Sẽ rất thú vị để xem trong 1-2 năm tới hướng nào chiếm ưu thế.

Deep dive vào kiến trúc model

Phần architecture của AlphaTransit khá quen thuộc nếu bạn đã từng đọc các paper về neural combinatorial optimization. Họ dùng một Graph Neural Network (GNN) để encode thông tin topology của mạng lưới đường phố, kết hợp với attention mechanism để agent có thể "nhìn" toàn bộ trạng thái mạng lưới khi ra quyết định.

Policy network nhận vào embedding của node hiện tại, context vector của tuyến đang xây, và global state embedding, rồi output ra probability distribution trên tập hợp các node lân cận khả thi. Đây là kiểu autoregressive decoding giống như cách language model generate text token by token, ở đây agent generate route station by station.

Theo kinh nghiệm của mình khi làm việc với GNN, cái khó nhất không phải architecture mà là reward shaping. Nếu reward quá sparse (chỉ cho điểm khi hoàn thành toàn bộ mạng lưới), agent sẽ học cực chậm. Nếu reward quá dense và hand-crafted, agent có thể hack reward mà không thực sự tạo ra mạng lưới tốt. Paper này xử lý vấn đề đó bằng cách dùng transit assignment simulation làm intermediate signal một cách tiếp cận mình thấy khá elegant.

Evaluation phần mình quan tâm nhất

Anh em làm ML chắc biết, với dạng bài toán planning/design thế này, evaluation là phần gây tranh cãi nhất. Bạn so sánh với cái gì? Ground truth là gì? Mạng lưới xe buýt thực tế của thành phố chưa chắc đã optimal nó là kết quả của hàng chục năm quyết định chính trị, ngân sách, và legacy infrastructure.

AlphaTransit evaluate trên nhiều thành phố với các kích thước khác nhau, so sánh với cả mạng lưới thực tế lẫn các baseline metaheuristic. Kết quả cho thấy agent tạo ra mạng lưới có tổng thời gian di chuyển trung bình thấp hơn so với baseline, đồng thời coverage tốt hơn hoặc tương đương.

Điểm mình appreciate là tác giả (Bibek Poudel) đã lên HuggingFace comment sẵn sàng trả lời câu hỏi về method, evaluation setup, và reproducibility. Đây là dấu hiệu tốt paper mà tác giả dám đứng ra defend công khai thì thường chất lượng ổn.

Ứng dụng thực tế và những thứ mình suy nghĩ thêm

Bạn có thể hỏi: "OK paper hay, nhưng liên quan gì đến mình?" Thực ra nếu bạn đang làm trong lĩnh vực logistics, ride-hailing, hay bất kỳ thứ gì liên quan đến routing và network design, thì approach này rất đáng tham khảo.

Mình đặc biệt thấy tiềm năng ở mấy use case sau:

Quy hoạch giao thông cho đô thị mới: Việt Nam đang phát triển rất nhiều khu đô thị mới, thành phố vệ tinh. Thay vì thuê consultant nước ngoài tốn tiền, một tool dựa trên RL có thể đề xuất mạng lưới transit ban đầu rồi expert review và điều chỉnh.

What-if analysis: Giả sử thành phố xây thêm một khu công nghiệp mới, demand matrix thay đổi. Với metaheuristic, bạn phải chạy lại cả ngày. Với trained RL agent, bạn feed demand mới vào và có kết quả trong vài phút.

Multi-modal planning: Mở rộng ra, approach tương tự có thể dùng cho việc thiết kế mạng lưới kết hợp xe buýt, metro, và xe đạp công cộng.

Tuy nhiên, mình cũng muốn lưu ý vài điểm thực tế. Bài toán transit design trong paper thường đơn giản hóa rất nhiều so với thực tế. Trong thực tế, bạn phải tính đến: đường một chiều, giờ cao điểm vs thấp điểm, capacity constraint của từng loại xe, depot location, driver scheduling, và cả yếu tố chính trị ("tuyến này phải đi qua khu vực X vì lý do Y"). Không có paper nào cover hết được, và AlphaTransit cũng không ngoại lệ.

Trend lớn hơn: RL cho infrastructure design

Nhìn rộng hơn, AlphaTransit nằm trong một trend đang lên rất mạnh: dùng RL để thiết kế và tối ưu hạ tầng quy mô lớn. Trong danh sách related papers, mình thấy có DeCoR (dùng RL để co-optimize thiết kế đường phố), các paper về routing xe điện, traffic forecasting bằng GNN... Tất cả đều hướng đến một tương lai mà AI không chỉ dự đoán mà còn thiết kế hạ tầng.

Đối với dev Việt Nam, mình nghĩ đây là một domain rất đáng để theo dõi. Giao thông đô thị ở Việt Nam đang là vấn đề lớn, và bất kỳ công cụ nào giúp quy hoạch tốt hơn đều có giá trị thực tiễn cao. Nếu bạn đang làm data science hay ML engineering và muốn tìm một bài toán vừa có depth kỹ thuật vừa có impact xã hội, thì transportation planning là một lựa chọn rất đáng cân nhắc.

Paper gốc có thể tìm trên HuggingFace Daily Papers. Nếu bạn muốn dive deeper, mình recommend đọc thêm TransitLM để so sánh hai paradigm (RL vs LLM) cho cùng một bài toán sẽ cho bạn perspective rất tốt về landscape hiện tại của AI for transportation.