Đồ Án Nghiên cứu, cài đặt thuật toán giải bài toán lập hành trình người đưa thư và ứng dụng

LỜI NÓI ĐẦU

Các bài toán trên đồ thị có nhiều ứng dụng trong các lĩnh vực khác nhau như mạng thông tin, đồ họa, ứng dụng lập kế hoạch . Các bài toán đặt ra trong các ứng dụng như vậy thường có cơ sở dữ liệu lớn nên việc rút ngắn thời gian tính toán để trả lời một câu truy vấn có ý nghĩa thực tiễn cao. Ngoài ra trong thực tế, các đồ thị được sử dụng trong các bài toán có thể liên tục thay đổi theo thời gian, ví dụ như các đỉnh hay các cạnh của nó có thể được thêm vào hay xóa đi (đồ thị động), hoặc thay đổi độ dài, lượng thông qua .
Mỗi lần có một thay đổi như vậy cấu trúc dữ liệu của bài toán, thông tin về các đỉnh cũng như các cạnh cũng bị thay đổi theo. Trong khi đó yêu cầu đặt ra là phải liên tục trả lời các câu hỏi về thông tin trong đồ thị như tính liên thông của đồ thị, rừng bao trùm tối thiểu, 2 đỉnh bất kỳ có nằm trên cùng một cây bao trùm tối thiểu hay không, đường đi ngắn nhất . Một cách tiếp cận để giải quyết các bài toán trên đồ thị động là sử dụng các cấu trúc dữ liệu và thuật toán truyền thống trong đồ thị tĩnh và chạy lại chúng mỗi khi có sự thay đổi trong đồ thị. Tuy nhiên cách tiếp cận như vậy không tận dụng được thông tin của đồ thị trước khi thay đổi dẫn đến độ phức tạp để trả lời một câu truy vấn về đồ thị sau mỗi bước thay đổi là lớn.
Trong đồ án tốt nghiệp này, em xin trình bày các nghiên cứu, khảo sát thực nghiệm và ứng dụng một số cấu trúc dữ liệu được đưa ra gần đây nhằm giúp quản lý các đồ thị động một cách mềm dẻo. Dựa trên các cấu trúc dữ liệu này, một số bài toán trên đồ thị động như kiểm tra tính liên thông, xây dựng cây bao trùm, tìm đường đi ngắn nhất được giải quyết với độ phức tạp thời gian nhỏ hơn so với việc chạy lại các thuật toán truyền thống trên đồ thị tĩnh mỗi khi có sự thay đổi trong đồ thị.
Đề tài của đồ án là “Nghiên cứu, cài đặt thuật toán giải bài toán lập hành trình người đưa thư và ứng dụng” được đặt ra với mục tiêu:

Nghiên cứu thuât toán giải và xây dựng ứng dụng giải quyết bài toán tìm hành trình tối ưu nhất cho người đưa thư, báo với các điểm đưa thư, báo cố định hoặc thay đổi tuỳ theo nhiệm vụ phân công.
Mô tả bằng đồ hoạ trên bản đồ tuyến đường lựa chọn cho người đưa thư, đảm bảo nhanh và ít tốn kém nhất.
Cài đặt cho mô hình trung tâm phát hành báo với tập hợp người đưa thư hữu hạn, hoặc chọn tuyến đường cho xe phục vụ đưa đón học sinh, sinh viên .
Thuật toán tìm hành trình tối ưu nhất cho người đưa thư là một thuật toán quan trọng, khó khăn và ý nghĩa to lớn trong thực tế tìm lộ trình di chuyển của bất kỳ đối tượng di động nào đó như: người, xe máy, ô tô Với hệ thống này mang lại nhiều tiện ích và hiệu quả cho người sử dụng, đặc biệt là hiệu quả về kinh tế, tiết kiệm thời gian, công sức trong việc lựa chọn đường đi cho hợp lý. Bên cạnh đó với màn hình mô phỏng trực tiếp trên bản đồ giúp cho người sử dụng dễ quan sát, dễ sử dụng, mang tính chất thực tế cao. Mô hình này có thể triển khai cho nhiều ứng dụng thực tế:

Hệ thống tìm đường đi tối ưu cho người đưa thư, người giao báo .
Hệ thống tìm đường đi tối ưu cho các dịch vụ đưa đón học sinh, sinh viên
Hệ thống xác định lộ trình cho các tour du lịch
Nôi dung của đồ án đề cập tới các vấn đề sau:

Nghiên cứu lý thuyết đồ thị và ứng dụng.
Nghiên cứu cụ thể về các thuật toán tìm đường đi trên đồ thị, đặc biệt là thuật toán giải bài toán lập hành trình cho người đưa thư.
Nghiên cứu về lập trình sử dụng cơ sở dữ liệu trên bản đồ(cụ thể là MapInfo).
Nghiên cứu về số hoá bản đồ, thực hiện số hoá một vùng cụ thể(ví dụ: khu vực Hà Nội), số hoá điểm, đường, và các mốc quan trong trên bản đồ cần thiết cho việc xác định đường đi đường biểu diễn cụ thể trên bản đồ.
Phân tích và cài đặt thuật toán người đưa thư.
Viết chương trình tìm đường đi cho người đưa thư, và thể hiện kết quả trên bản đồ cụ thể.
Sau 6 tháng thực hiện đế nay em đã xây dựng được chương trình trên ngôn ngữ C#, kết hợp với cơ sở dữ liệu MapInfo mô phỏng được các tác nghiệp trên bản đồ. Chương trình có thể sử dụng tại các Trung tâm phát hành báo chí tại các quận nội thành Hà Nội.
Trong quá trình thực hiện đồ án tốt nghiệp em xin chân thành cảm ơn thầy giáo Đại tá PGS. TS Nguyễn Đức Hiếu đã tận tình chỉ bảo để em có thể hoàn thành nhiệm vụ.

Hà Nội, Ngày 13 tháng 3 năm 2009
Học viên








BC_DATN_Le Thi Mong Thanh