Luận văn: Platform Quản lý & Lập lộ trình Vận tải Thời gian thực - Nguyễn Thanh Hoàng

Khám phá luận văn về platform và thuật toán G-Tree lập lộ trình vận tải thời gian thực. Giải pháp tối ưu cho việc quản lý và điều phối phương tiện.

• Tác giả: Nguyễn Thanh Hoàng
• Người hướng dẫn: TS. Phạm Quang Dũng
• Trường học: Trường Đại học Bách Khoa Hà Nội
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu và xây dựng platform cho việc quản lý các phương tiện di chuyển và phát triển các thuật toán lập lộ trình vận tải thời gian thực
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Khái Niệm Lập Lộ Trình Vận Tải Thời Gian Thực

Lập lộ trình vận tải thời gian thực là một quá trình động để tối ưu hóa các tuyến đường giao hàng dựa trên thông tin vị trị thực tế của phương tiện. Với sự phát triển của thương mại điện tử, nhu cầu điều phối vận chuyển hiệu quả trở nên cấp thiết hơn bao giờ hết. Hệ thống quản lý phương tiện di chuyển cần theo dõi liên tục vị trí của các đơn vị giao vận để tính toán khoảng cách chính xác giữa phương tiện và địa điểm nhận hàng. Đây là nền tảng cho việc lựa chọn phương tiện phù hợp nhất phục vụ từng đơn hàng, giảm thiểu thời gian giao hàng và chi phí vận hành. Thuật toán lập lộ trình phải cân bằng giữa tốc độ xử lý dữ liệu và khả năng mở rộng khi làm việc với bộ dữ liệu cực lớn.

1.1. Tầm Quan Trọng của Tối Ưu Hóa Lộ Trình

Tối ưu hóa lộ trình vận tải giúp giảm chi phí xăng dầu, thời gian giao hàng và tăng sự hài lòng khách hàng. Mỗi phương tiện cần được định tuyến một cách thông minh để phục vụ tối đa các đơn hàng trong cùng một chuyến đi. Hệ thống điều phối vận tải thời gian thực cho phép điều chỉnh lộ trình khi có đơn hàng mới hoặc thay đổi tình hình giao thông.

1.2. Thách Thức Trong Thực Hiện

Các thách thức chính bao gồm xử lý dữ liệu khổng lồ, cập nhật vị trí theo thời gian thực, và tìm kiếm nhanh k điểm gần nhất. Thuật toán cổ điển như Dijkstra không đủ hiệu quả khi xử lý các bộ dữ liệu lớn. Do đó, cần các cấu trúc dữ liệu và thuật toán tiên tiến để đảm bảo thời gian xử lý truy vấn nhanh chóng.

II. Kiến Trúc Platform Quản Lý Vận Tải

Platform quản lý phương tiện di chuyển được xây dựng dựa trên một kiến trúc phân tầng bao gồm tầng thu thập dữ liệu, tầng xử lý và tầng giao diện người dùng. Tầng thu thập dữ liệu theo dõi vị trí thực tế của các phương tiện thông qua GPS hoặc công nghệ định vị khác. Dữ liệu này được lưu trữ trong cơ sở dữ liệu bản đồ mạng lưới đường bộ với cấu trúc được tối ưu hóa. Tầng xử lý thực thi các thuật toán lập lộ trình và truy vấn tìm kiếm để đưa ra quyết định điều phối phương tiện. Platform phải đảm bảo độ tin cậy cao và khả năng xử lý concurrency khi có hàng nghìn phương tiện hoạt động đồng thời.

2.1. Cấu Trúc Dữ Liệu G Tree

G-Tree là cấu trúc dữ liệu tiên tiến dựa trên phân hoạch đồ thị mạng lưới đường bộ. Nó chia nhỏ đồ thị lớn thành các đồ thị con nhỏ hơn, tạo ra một cấu trúc cây trong đó mỗi nút tương ứng với một phân vùng. G-Tree cân bằng tốt giữa thời gian xử lý truy vấn và khả năng mở rộng với bộ dữ liệu khổng lồ.

2.2. Các Thành Phần Hệ Thống

Hệ thống bao gồm: (1) Module theo dõi vị trí phương tiện; (2) Module tìm đường đi ngắn nhất sử dụng thuật toán tối ưu; (3) Module tìm k điểm gần nhất để chọn phương tiện phù hợp; (4) Module giao diện quản lý và giám sát hoạt động vận tải.

III. Các Thuật Toán Lập Lộ Trình Thời Gian Thực

Các thuật toán lập lộ trình hiện đại phải xử lý nhanh các truy vấn trong môi trường thay đổi liên tục. Thuật toán Dijkstra là phương pháp cơ bản tìm đường đi ngắn nhất nhưng có hiệu suất kém với dữ liệu lớn. Các thuật toán nâng cao như A* sử dụng heuristic để tăng tốc độ tìm kiếm. Thuật toán dựa trên G-Tree kết hợp phân hoạch đồ thị với tìm kiếm cục bộ, cho phép xử lý truy vấn nhanh hơn đáng kể. Các thuật toán động có khả năng điều chỉnh lộ trình khi có sự thay đổi về tình hình giao thông hoặc đơn hàng mới. Nghiên cứu cho thấy G-Tree có thời gian xử lý tốt hơn so với Dijkstra trên bộ dữ liệu bản đồ thực tế.

3.1. Tìm Đường Đi Ngắn Nhất

Truy vấn tìm đường đi ngắn nhất là cơ sở của lập lộ trình vận tải. Sử dụng G-Tree, hệ thống không cần tìm kiếm trên toàn bộ đồ thị mà chỉ tập trung vào các phân vùng liên quan. Điều này giảm đáng kể thời gian xử lý và tài nguyên tính toán cần thiết.

3.2. Tìm K Điểm Gần Nhất

Truy vấn k-NN (k nearest neighbors) giúp tìm k phương tiện gần nhất với vị trí đơn hàng. Với cấu trúc G-Tree, việc tìm kiếm được tối ưu hóa bằng cách sử dụng khoảng cách Euclidean và khoảng cách đường bộ thực tế, cải thiện độ chính xác trong lựa chọn phương tiện.

IV. Ứng Dụng và Kết Quả Thực Nghiệm

Platform lập lộ trình vận tải thời gian thực đã được triển khai thử nghiệm trên bộ dữ liệu bản đồ thực tế của 6 tỉnh thành phố lớn tại Việt Nam. Kết quả thử nghiệm cho thấy hệ thống có thể xử lý điều phối thu gom đơn hàng hiệu quả, với thời gian xử lý truy vấn nhanh hơn đáng kể so với các thuật toán cổ điển. So sánh giữa việc tối ưu lộ trình sử dụng khoảng cách thực tế và khoảng cách đường chim bay cho thấy khoảng cách thực tế cung cấp kết quả chính xác hơn. Hệ thống điều phối xe có khả năng điều chỉnh lộ trình theo thời gian thực khi có đơn hàng mới, giảm chi phí vận hành và tăng tỷ lệ giao hàng đúng hạn.

4.1. Kết Quả Hiệu Suất

G-Tree cho thấy kết quả xử lý vượt trội so với Dijkstra cổ điển, với tốc độ nhanh hơn từ 10-20 lần tùy theo quy mô dữ liệu. Trên bộ dữ liệu lớn, sự khác biệt còn lớn hơn, chứng tỏ khả năng mở rộng tuyệt vời của cấu trúc này. Thời gian xử lý truy vấn trung bình giảm từ hàng giây xuống millisecond.

4.2. Lợi Ích Thực Tế cho E commerce

Trong lĩnh vực thương mại điện tử, platform quản lý vận tải giúp giảm chi phí vận hành, tăng tốc độ giao hàng, và cải thiện trải nghiệm khách hàng. Khả năng xử lý lộ trình thời gian thực cho phép các đơn vị giao vận linh hoạt điều chỉnh kế hoạch khi có tình huống đột phát.

Trích đoạn nội dung tài liệu

Chương 1 Giới thiệu Với sự bùng nổ của ngành thương mại điện tử trong những năm gần đây, đặc biệt trong năm 2020 vừa rồi, dịch Covid-19 đã làm thay đổi mạnh mẽ hành vi của người tiêu dùng, khi cả người mua và người bán đều đẩy mạnh chuyển sang các hình thức mua sắm và kinh doanh trực tuyến thay vì hình thức mua bán truyền thống như trước đây. Cũng vì thế, giao vận vốn đã quan trọng nay lại càng trở nên quan trọng hơn trong chuỗi cung ứng. Trong thực tế, một đơn vị vận chuyển trong một ngày có thể nhận số lượng đơn hàng lên đến hàng nghìn đơn, cũng như phải quản lý hàng nghìn xe phục vụ vận chuyển các đơn hàng. Do đó cần phải có những hệ thống tự động quản lý và đưa ra quyết định xe nào phục vụ đơn hàng nào.

Hiện nay, do điện thoại thông minh và mạng 4G đã trở lên quá phổ biến, hầu hết ai cũng sở hữu một chiếc smartphone để làm việc, và chúng đều được trang bị hệ thống định vị toàn cầu. Nên các hệ thống quản lý vận chuyển đều có thể dễ dàng lấy được vị trí của đơn hàng và các xe vận chuyển theo thời gian thực. Để đưa ra được các quyết định điều phối xe, các hệ thống này sẽ cần biết được thông tin khoảng cách giữa vị trí của các xe, vị trí lấy và vị trí giao của các đơn hàng. Ngoài ra ta cũng cần tính khoảng cách giữa địa điểm lấy hàng và giao hàng để tính được chi phí vận chuyển của đơn hàng.

Như vậy, ta cần một hệ thống có thể trả lời được hai loại truy vấn cơ bản sau: (1) Tìm đường đi ngắn nhất giữa hai địa điểm (Single-Pair Shortest Path Query - SPSP). Tùy vào từng loại đơn hàng cùng với nhu cầu của khách hàng, các đơn vị vận chuyển sẽ có nhiều cách vận hành khác nhau. Với hình thức giao hàng trong ngày sẽ chỉ thực hiện khi địa điểm lấy hàng và giao hàng trong cùng thành phố, các tài xế thường chỉ thực hiện vận chuyển một đơn trong một thời điểm, nghĩa là họ sẽ chỉ đi đến nơi lấy hàng và đi thẳng đến nơi giao hàng của đơn hàng mà không đi qua bất kỳ địa điểm nào khác nữa. Và chi phí sẽ phụ thuộc vào khoảng cách giữa hai địa điểm lấy hàng và giao hàng.

Do đó hệ thống sẽ cần truy vấn (1) để tính chi phí, và sử dụng truy vấn (2) để tìm các tài xế gần với địa điểm lấy hàng, sau đó chọn ra người phù hợp nhất thực hiện đơn hàng. Ngược lại, với hình thức vận chuyển liên tỉnh, để tối ưu chi phí các đơn hàng sẽ được thu gom 1 đến các kho tại khu vực của nơi lấy hàng, sau đó được phân loại và vận chuyển đến kho ở khu vực nơi giao hàng, rồi mới được giao đến khách hàng. Hình thức này là bài toán VRP [21], để tạo được các lộ trình tối ưu đi gom hàng ta cần phải có khoảng cách ngắn nhất giữa các địa điểm lấy hàng (truy vấn (1)) rồi từ đó sử dụng các thuật toán heuristics để tìm lời giải có lộ trình thu gom tốt nhất. Một ý tưởng là ta có thể sử dụng Google Map cho hai truy vấn trên.

Tuy nhiên, ta chỉ có thể sử dụng Google Map một cách miễn phí khi là những người dùng cơ bản. Với các đơn vị vận chuyển có hàng nghìn đơn hàng một ngày, số truy vấn sẽ lên đến hàng triệu, do đó để có thể sử dụng các API truy vấn cho hai truy vấn trên, họ sẽ cần phải trả phí cho Google. Đương nhiên, hướng tiếp cận này sẽ làm giảm lợi nhuận của công ty. Một giải pháp khác đó là ta có thể sử dụng khoảng cách Haversine1 để tính khoảng cách giữa hai địa điểm.

Nhưng khi sử dụng cách này cho các thành phố có địa hình nhiều sông hồ, khoảng cách tính được có thể khác rất xa so với di chuyển thực tế. Một hướng tiếp cận có thể khắc phục được các nhược điểm trên là sử dụng dữ liệu bản đồ mở OpenStreetMap2 cho hai truy vấn trên. Dữ liệu trong OpenStreetMap bao gồm các địa điểm trên các con đường, mỗi địa điểm sẽ có thông tin về kinh tuyến và vĩ tuyến, và dữ liệu cũng cung cấp thông tin về các con đường được tạo thành bởi một chuỗi các địa điểm liên tiếp kết nối với nhau. Do đó, ta có thể coi mỗi địa điểm là một đỉnh của đồ thị, mỗi cạnh tương ứng là hai địa điểm liên tiếp trên một con đường và có trọng số là khoảng cách Haversine giữa hai địa điểm đó.

Đối với các đối tượng di chuyển trên mạng lưới đường bộ sử dụng dữ liệu OpenStreetMap, vị trí của các đối tượng di chuyển tại mỗi thời điểm sẽ được cập nhật theo các địa điểm trên dữ liệu bản đồ, để từ đó sử dụng thông tin địa điểm của đối tượng cho hai truy vấn trên cho các bài toán vận chuyển. Vì hai địa điểm liên tiếp trên một con đường trong dữ liệu bản đồ cách nhau không quá xa (dưới 50 mét), cũng như mật độ các địa điểm trên bản đồ là rất dày đặc, nên chúng tôi sử dụng KD-Tree [3] để cập nhật vị trí của đối tượng chuyển động là địa điểm gần nhất trong dữ liệu bản đồ so với vị trí thực tế của đối tượng. Như vậy sẽ có thể coi như đồ thị là tĩnh không thay đổi và ta chỉ việc xử lý các truy vấn theo một đồ thị duy nhất. Đã có rất nhiều nghiên cứu giải quyết hai truy vấn trên.

Các tác giả trong [2, 7, 13, 14, 23, 24] đã nghiên cứu bài toán tìm đường đi ngắn nhất giữa hai địa điểm. Trong khi các nghiên cứu [5, 11, 12, 16, 17, 19, 22] giải quyết bài toán tìm k địa điểm gần nhất. Mặc dù họ đã có được những kết quả tốt cho từng loại truy vấn, tuy nhiên vẫn có những hạn chế của các phương pháp này với những dữ liệu thực tế. Hoặc là các phương pháp này không thể mở rộng được với những bộ dữ liệu cực lớn, hoặc là không thể giải quyết được cả hai loại truy vấn trên.

Một cấu trúc dữ liệu G-Tree được Ruicheng Zhong và các cộng sự đề xuất trong [26] đã đạt được việc vừa hỗ trợ hai truy vấn trên một cách hiệu quả vừa có khả năng mở rộng cho những bộ dữ liệu cực lớn. G-Tree được lấy ý tưởng từ cấu trúc dữ liệu R-Tree [9], trong đó, mạng lưới đường bộ sẽ được phân hoạch ra thành các đồ thị con, với bộ nhớ sử dụng chỉ là O(|V | log |V |) (với V là tập đỉnh của đồ thị), nên nó có khả năng mở rộng với những bộ dữ liệu rất lớn. Trong luận văn này, chúng tôi nghiên cứu và khai thác cấu trúc lưu trữ thông tin về bản đồ để có thể cung cấp các truy vấn về khoảng cách và điểm gần nhất một cách hiệu quả. 1 Khoảng cách tính theo kinh tuyến và vĩ tuyến giữa hai địa điểm.

2 Một dữ liệu bản đồ trực tuyến được cập nhật liên tục bởi các cộng tác viên. 2 Cụ thể, luận văn sẽ khai thác cấu trúc G-Tree [26] và áp dụng vào việc xây dựng hệ thống quản lý các đối tượng chuyển động, cung cấp các truy vấn hiệu quả về khoảng cách và tập điểm gần nhất. Hệ thống này sẽ được áp dụng thử nghiệm vào bài toán điều phối các phương tiện vận chuyển thu gom đơn hàng trong lĩnh vực thương mại điện tử. Hệ thống được cài đặt và thử nghiệm, đánh giá trên dữ liệu bản đồ OpenStreetMap và kịch bản mô phỏng việc điều phối các đơn hàng sinh ngẫu nhiên.

Các phần tiếp theo trong luận văn này được trình bày như sau. Chương 2 trình bày cơ sở lý thuyết và mô hình toán học của bài toán, và các nghiên cứu liên quan. Chương 3 trình bày cụ thể về cấu trúc dữ liệu G-Tree, và cách sử dụng G-Tree cho hai truy vấn Single-Pair Shortest Path Query và k Nearest Neighbors Query. Chương 4 giới thiệu hệ thống tự động điều phối xe thu gom đơn hàng theo thời gian thực trong đó có ứng dụng G-Tree vào xử lý truy vấn kNN.

Chương 5 trình bày về các kết quả thực nghiệm. 3 Chương 2 Phát biểu bài toán 2.1 Phát biểu bài toán Một mạng lưới đường bộ có thể được mô hình hóa thành một đồ thị vô hướng có trọng số G = (V, E), trong đó V là tập đỉnh và E là tập cạnh của đồ thị. Mỗi cạnh (u, v) trong tập E có trọng số là w(u, v) (có thể là khoảng cách hay thời gian di chuyển giữa hai địa điểm), và là một số có giá trị dương. Với một đường đi từ u đến v, tổng trọng số của các cạnh trên đường đi này được gọi là khoảng cách của đường đi đã cho từ u đến v.

Trong tất cả các đường đi giữa hai đỉnh u và v, đường đi có khoảng cách ngắn nhất được gọi là đường đi ngắn nhất giữa u và v.1: Một đồ thị mô phỏng mạng lưới đường bộ [26]. • Gọi SP(u, v) là đường đi ngắn nhất giữa u và v. • Gọi SPDist(u, v) là khoảng cách của đường đi ngắn nhất giữa u và v.1 mô tả một mạng lưới đường bộ được mô hình hóa thành một đồ thị. 4 Ta xem xét hai loại truy vấn sau: • Single-Pair Shortest Path Query (SPSP): Cho một đồ thị G và một truy vấn q = {u, v}, truy vấn SPSP sẽ trả về SPDist(u, v).

Ví dụ, ta xem xét một truy vấn q = {v4 , v11 } với đồ thị trong Hình 2.1, ta có thể thấy SP(v4 , v11 ) = hv4 , v3 , v2 , v6 , v7 , v10 , v11 i nên SPDist(v4 , v11 ) = 18. • k Nearest Neighbors Query (kNN): Cho một đồ thị G và một truy vấn q = {vq ,C, k}, với vq là đỉnh (địa điểm) cần truy vấn, C là một tập các đỉnh chứa đối tượng, và k là một số nguyên, kết quả truy vấn cần trả về R là một tập k đối tượng (đỉnh của đồ thị) gần với đỉnh truy vấn nhất mà: – Kích thước của R là k hay |R| = k; – R phải là tập con của C hay R ⊆ C; – ∀v ∈ R, u ∈ C \ R, SPDist(vq , v) ≤ SPDist(vq , u). Để đơn giản, trong luận văn này chúng tôi giả sử rằng các địa điểm truy vấn và các đối tượng đều được đặt tại các đỉnh của đồ thị G. Nếu địa điểm truy vấn nằm trên một cạnh của đồ thị, ta có thể sử dụng KD-Tree để tìm đỉnh gần nhất so với địa điểm truy vấn theo khoảng cách Haversine.