Khi xây dựng một hệ thống giao nhận hay logistics ép tải cao (high-scale), những bài hướng dẫn thuật toán chung chung trên mạng thường hay dắt mũi lập trình viên đi sai đường. Bọn họ cứ ra rả rằng A* lúc nào cũng ngon hơn Dijkstra. Thế nhưng, bước ra ngoài đời thực, trong thế giới của Hệ thống Định tuyến (Routing Engines) và Ma trận Khoảng cách (Distance Matrices), sự thật lại phũ phàng và phức tạp hơn rất nhiều.

Trong phần đầu tiên của khóa masterclass này, chúng ta sẽ bước ra khỏi mớ lý thuyết hàn lâm sách vở. Chúng ta sẽ trực quan hóa vòng đời chính xác của một cú request định tuyến (routing request)—bắt đầu từ việc bẻ cong (snapping) một tọa độ GPS bám vào mặt đường, cho đến việc luồn lách né kẹt xe, và cuối cùng là giải bài toán tìm đường chỉ trong chớp mắt (vài mili-giây) nhờ vào Contraction Hierarchies.

Khớp Bản Đồ (Map Matching): Bẻ Cong GPS Trúng Khớp Đồ Thị

Answer-first: Trước khi mấy thuật toán cao siêu kịp làm ăn gì, hệ thống (engine) bắt buộc phải dập cái tọa độ GPS thô thiển của bạn cho khớp vào đúng một đoạn đường vật lý (physical road segment) thông qua trò Khớp Bản Đồ (Map Matching). Các hệ thống chuẩn công nghiệp xài R-Trees (các hộp không gian bao lọt - spatial bounding boxes) kết hợp với Mô hình Markov Ẩn (Hidden Markov Models - HMM) để suy luận ra đúng con đường dựa trên quỹ đạo di chuyển (trajectory) của bạn.

Mỗi khi cái điện thoại của bạn nhè ra (ping) một tọa độ GPS, nó có thể bị lệch sóng tới 10 hay 20 mét. Giả sử bạn đang vi vu trên cầu vượt cao tốc, cái tọa độ thô đó dư sức đánh lừa hệ thống rằng bạn đang chạy tàng tàng ở con đường làng bên dưới.

Một cái hệ thống định tuyến non nớt (naive) sẽ hì hục ngồi tính khoảng cách từ điểm đó tới mọi con đường trong thành phố. Chuyện này về mặt tính toán là lực bất tòng tâm (computationally impossible). Thay vào đó, những engine hiện đại như Graphhopper xài R-Trees. R-trees gom các đoạn đường nhốt vào trong những Hộp Chữ nhật Bao lọt Nhỏ nhất (Minimum Bounding Rectangles - MBRs). Engine truy vấn (queries) cái cây này để tóm gọn mọi con đường lọt thỏm trong bán kính 50 mét với tốc độ lô-ga-rít (logarithmic time).

Để chặn đứng trò nhận vơ dính sai đường (kiểu nhầm đường hầm dưới gầm cầu), các engine nhờ cậy đến Mô hình Markov Ẩn (HMM) và thuật toán Viterbi. HMM cân đo đong đếm xác suất (probability) của lộ trình bằng cách dòm ngó lại lịch sử vệt quỹ đạo di chuyển của bạn đối chiếu với mạng lưới giao thông (network topology), đảm bảo bạn lúc nào cũng được đặt vào đúng con đường hợp lý nhất (logical road).

Dijkstra đọ sức A*: Hiện Thực Phũ Phàng Trong Logistics

Answer-first: A* phóng nhanh hơn trong mấy pha tìm đường Điểm-nối-Điểm (A đến B) vì nó xài hàm heuristic (ước lượng) để lái hướng tìm kiếm. Tuy nhiên, Dijkstra mới là trùm cuối vô đối khi sinh ra Ma trận Khoảng cách (Distance Matrix, 1 đến N) vì nó sinh ra cái tài thiên bẩm: đồng loạt đẻ ra một cái cây đường đi ngắn nhất (shortest-path tree) cắm rễ tới mọi điểm đích (reachable nodes) trong cùng một lúc.

Mấy bài tutorial sách vở cực kỳ cuồng A*. Thuật toán A* xài một hàm heuristic $h(n)$, thường là nã khoảng cách đường chim bay (Euclidean distance - cho đường nội đô) hoặc khoảng cách bề mặt cầu (Haversine distance - cho đường xa), để phỏng đoán quãng đường còn lại. Hàm này y hệt cái la bàn, ép thuật toán đâm đầu hùng hục cày thẳng về phía đích.

Nhưng mấy hệ thống logistics cỡ bự như Grab hay ShopeeXpress hiếm khi thèm đoái hoài ba trò định tuyến Điểm-nối-Điểm (Point-to-Point) nguyên thủy. Bọn họ bào Ma trận Khoảng cách (Distance Matrices) (ví dụ: bới tìm 10 tài xế gần nhất cho 1 cuốc khách). Ngu ngốc vác A* ra giải bài toán ma trận 1-ra-10, bạn sẽ phải hì hục cày lại thuật toán tận 10 lần riêng biệt. Trong khi nếu xài Single-Source Dijkstra (Dijkstra Đơn Nguồn), bạn chỉ tốn công chạy đúng một lần. Dijkstra lan tỏa ra tứ phía y y như mặt nước gợn sóng (ripple), hễ chạm tay vào cái node nào là lòi ngay ra đường ngắn nhất đến node đó. Thuật toán sẽ ngay lập tức phanh gấp (stops) ngay cái khoảnh khắc tóm được ông tài xế thứ 10, biến nó thành công cụ bóc lột sức mạnh rẻ mạt tới mức hàm mũ (exponentially cheaper) cho các trò tính ma trận.

Đồ Thị Hướng Cạnh (Edge-Based Graphs) Và Những Biển Cấm Rẽ

Answer-first: Để đối phó với dăm ba cái luật lệ trần đời như “Cấm Quay Đầu (No U-Turns)” hay “Cấm Rẽ Trái (No Left Turns)”, các bộ định tuyến âm thầm biến hình Đồ thị Hướng Nút (Node-based graphs) thành Đồ thị Hướng Cạnh (Edge-Based graphs). Mánh khóe này trao quyền cho thuật toán bám sát được trạng thái chuyển hướng (transition state) giữa hai đoạn đường cụ thể.

Lý thuyết đồ thị chuẩn mực coi ngã tư là mấy cái Nút (nodes) và đường sá là Cạnh (edges). Nhưng chuyện gì xảy ra nếu cái ngã tư đó treo biển cấm rẽ trái? Ném vào một cái đồ thị hướng nút (node-based graph), thuật toán não cá vàng chỉ nhớ được là nó vừa bò tới cái nút đó; còn nó chui ra từ cái lỗ (con đường) nào thì nó quên béng mất.

Các hệ thống định tuyến (Routing engines) giải bài toán này bằng cách lật ngược thế cờ: phong cho đường sá (roads) lên làm nút (nodes), và các ngã rẽ (turns) thành cạnh (edges). Đứa con lai này được gọi là Đồ Thị Hướng Cạnh (Edge-Based Graph). Lúc thuật toán đưa mặt ra ngã rẽ, nó sẽ liếc trộm cái bảng cước phạt nội bộ (internal penalty table). Nếu rẽ trái bị cấm, nó phết cho cái giá chuyển hướng (transition cost) vọt lên hàng vô cực (infinity), ép lộ trình phải ngậm đắng nuốt cay đi thẳng. Đây cũng là lý do tại sao đôi khi bạn thấy mấy lộ trình vạch hình “răng cưa” (zigzag) chạy ngoằn ngoèo trong mấy khu phố bàn cờ nếu cái hệ thống bị nhồi cái luật phạt nặng (heavy penalties) cho những pha rẽ trái cắt ngang dòng xe cộ.

Định Tuyến Bám Thời Gian (Time-Dependent Routing) Né Kẹt Xe

Answer-first: Mấy thuật toán cổ điển ngây thơ tin rằng quãng đường là bất biến (static). Dijkstra Phụ Thuộc Thời Gian (Time-Dependent Dijkstra - TDD) cập nhật động (dynamically updates) cái trọng số của một cạnh $w(u,v,t)$ dựa rịt vào thời gian dự kiến tới nơi (arrival time) $t$ của xe ngay tại cái ngã tư đó.

Giao thông không bao giờ đứng yên. Nếu cái lộ trình tốn mất 2 tiếng, thì tình trạng kẹt xe ở đích đến lúc bạn tới nơi đã biến hóa khôn lường so với lúc bạn xuất phát. Trò định tuyến bám thời gian giải quyết vấn đề này bằng cách ép luật Vào Trước-Ra Trước (FIFO). Ngay khi thuật toán lết qua (traverses) đồ thị, nó tính luôn thời gian tới nơi (arrival time) ở từng ngã rẽ và chọc (queries) vào một cái ma trận tốc độ biến thiên theo thời gian (time-varying speed matrix) để moi ra được cái giá phải trả thực sự (true travel cost) cho chặng tiếp theo.

Cấu Trúc Phân Cấp Rút Gọn (Contraction Hierarchies - CH): Bí Kíp Đạt Tốc Độ Mili-giây

Answer-first: Để vượt qua cái hố đen ngốn tài nguyên $N^2$ của tụi A* và Dijkstra, những engine đời mới xài Contraction Hierarchies (CH). CH ngồi tính nháp trước (pre-calculates) mấy cái “lối tắt” (shortcuts) vắt ngang các nút giao lớn, giúp mấy cú truy vấn (queries) nhàn nhã nhảy cóc qua mấy đường xó xỉnh và ói ra kết quả trong vài mili-giây.

Tưởng tượng CH giống hệt cái Phép Ẩn Dụ Chuyến Bay (Airport Analogy). Nếu bạn muốn lết từ Hồ Chí Minh ra Hà Nội, bạn không rảnh đâu mà chạy luồn lách qua từng ngõ hẻm dọc đường. Bạn chui vào đường làng chạy ra sân bay, bay cái vèo thẳng ra thành phố đích, rồi lại vác xác bò đường làng về khách sạn.

Contraction Hierarchies làm y chang trò đó bằng toán học:

  1. Tiền Xử Lý (Giai Đoạn Ôn Bài - The Study Phase): Bộ engine bốc rải dọn sạch ba cái đường hẻm cụt (cul-de-sacs) “kém sang”, rồi nối những Lối Tắt (Shortcuts) đâm thẳng giữa các nút cao tốc đầu sỏ.
  2. Giai Đoạn Truy Vấn (Query Phase): Khi bạn ném một yêu cầu tìm đường vào, bộ engine kích nổ một cú Tìm Kiếm Hai Chiều (Bidirectional Search) (vừa bò tới từ vạch xuất phát, vừa thụt lùi từ vạch đích). Cái cuộc lùng sục này chỉ có nước leo “lên” (climbs “up”) cái thang phân cấp của mấy con đường VIP (important roads).

Trò này vả rụng thời gian tính toán từ hàng giây xuống còn vài mili-giây lèo tèo (single-digit milliseconds). Tuy nhiên, cục CH mặc định thì cứng nhắc (static). Lỡ có vụ tai nạn cấm đường, nguyên cái hệ thống phân cấp phải bị đập đi xây lại (rebuilt). Để cân được luồng giao thông biến động vùn vụt (dynamic traffic), các engine xài Cấu trúc CH Tùy biến (Customizable Contraction Hierarchies - CCH) hoặc nhét Thuật toán ALT (A*, Landmarks, Triangle Inequality) để cập nhật trọng số (weights) ngay tắp lự.

Sẵn sàng biến mớ lý thuyết khô khan thành đồ thật chưa? Quất tiếp Phần 2: Cài Đặt Môi Trường Từ Số 0 (Docker, OSM, Golang) để lót gạch cho cái môi trường code local của bạn và nặn dữ liệu OpenStreetMap nào.

Hỏi Nhanh Đáp Gọn (FAQ): Thuật Toán Định Tuyến & Mấy Góc Khuất Đời Thực

Tại sao bộ engine nhà em nó lại nhè ra cái lộ trình hình 'răng cưa' (zigzag) dị hợm trên mấy cái đường ô bàn cờ (grid) vậy?
Là do cái hàm heuristic trong A* nó bốc phét phóng đại (overestimating) khoảng cách đường chim bay, hoặc cái đồ thị của bạn đang ôm cấu hình Hướng-Cạnh (Edge-based) và cắn thuốc phạt quá nặng mấy cái ngã rẽ (ví dụ: bẻ luật cho đi đường thẳng rẻ rúng hơn nhiều so với việc mòn mỏi chờ rẽ trái, đẻ ra mấy đường răng cưa dị hợm).
Nếu Contraction Hierarchies (CH) nó mượt đến thế, sao thiên hạ không xài nó quách cho rồi 24/7 luôn?
Tại vì cục CH gốc rễ nó chôn chân một chỗ (static). Hễ cái đường nó bị bưng bít hay kẹt xe lòi kèn (severe traffic jam), nguyên bộ sậu cấu trúc phân cấp (entire hierarchy) phải đè nhau ra tính toán gỡ gạc xây lại (computational rebuild) cực kỳ tốn kém. Mấy hệ thống ngậm thìa vàng (high-end systems) phải móc Cấu trúc CH Tùy biến (CCH) hoặc thuật toán ALT ra mới trị được mớ giao thông đỏng đảnh.
Làm sao cái engine nó biết tôi đang băng băng trên cầu chứ éo phải đang lết ở con đường hầm bên dưới?
Nhờ trò Khớp Bản Đồ (Map Matching) xài Mô hình Markov Ẩn (HMM) với thuật toán Viterbi đó. Nó đâu có dở hơi mà đi bẻ cong (snap) dính chặt vào cái vạch đường gần nhất; nó ngồi dòm ngó lịch sử quỹ đạo di chuyển (historical trajectory - xác suất chuyển đổi) và vác cả cao độ (elevation) ra cân đo đong đếm để rặn ra cái lộ trình hợp lý nhất.
Chuyện gì xảy ra nếu tôi muốn tìm đường cho xe tải chứ không phải xe hơi con? Tôi có phải hì hục đúc lại nguyên một cái đồ thị mới toanh không?
Không cần. Bạn xài chiêu đổi Hồ sơ Trọng số (Weighting Profiles). Cái hình hài mạng lưới đồ thị vật lý (physical graph topology) vẫn giữ y nguyên, nhưng cái hàm phán xét giá cả (cost function) bên trong sẽ bị tráo đi để đập phạt thẳng tay hoặc cấm tiệt mấy cái bờ rìa (edges) chui hầm vướng nóc hay quá tải trọng cấm qua cầu.
Cái vụ Dijkstra 1-ra-N có nghĩa là cái máy chủ (server) nó phải khóc ròng chạy tìm đường ngắn nhất cho sạch sành sanh nguyên cái bản đồ luôn à?
Sai bét. Cái thuật toán đẻ cây đường đi ngắn nhất (shortest-path tree algorithm) nó khôn lõi lắm, nó sẽ bấm nút dừng bung xòe (stops expanding) vùng bán kính tìm kiếm (search radius) ngay chóc cái giây phút nó chộp được con mồi (đích đến) thứ N, đỡ tốn được một lượng tài nguyên CPU khổng lồ (massive amounts of CPU compute) so với việc hì hục cày nát nguyên một cái sa bàn thành phố (full city grid).