MỞ ĐẦU. TỔNG QUAN VỀ ĐỀ TÀI. Hiện tr¿ng hệ thống tìm đ°ờng đi ngắn nhất. Phát biểu bài toán.
Yêu cầu đ¿t đ°ÿc cÿa hệ thống. Giới thiệu các phần mềm sử dāng để cài đặt ch°¡ng trình. PHÂN TÍCH THIẾT KẾ HỆ THỐNG. Phân tích bài toán.
Ph°¡ng pháp l°u trữ dữ liệu cÿa bản đồ. Thuật toán tìm đ°ờng đi ngắn nhất. Biểu đồ Use Case. Biểu đồ tuần tự.
CÀI ĐẶT CHƯƠNG TRÌNH VÀ THỬ NGHIỆM. Môi tr°ờng cài đặt. Giao diện ch°¡ng trình. Thử nghiệm gÿi ý tìm kiếm địa điểm.
Tr°ờng hÿp đ°ờng đi không có đ°ờng mát chiều. Tr°ờng hÿp đ°ờng đi có đ°ờng mát chiều. Tr°ờng hÿp đ°ờng đi cấm đi bá và xe máy. Tr°ờng hÿp đ°ờng đi cấm xe ô tô.
43 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN. 45 TÀI LIỆU THAM KHẢO. 48 iv DANH MĀC VI¾T TÂT STT Ký hiáu chÿ vi¿t tÃt Cām tÿ đÅy đă 1 HTML HyperText Markup Language 2 CSS Cascading Style Sheets 3 API Application Programming Interface 4 I/O Input/ Output 5 HTTP HyperText Transfer Protocol 6 JSON JavaScript Object Notation 7 OSM OpenStreetMap 8 id Identification 9 MB Megabyte 10 OS Operating System 11 CPU Central Processing Unit 12 RAM Random Access Memory 13 GPS Global Positioning System 14 WIFI Wireless Fidelity v DANH SÁCH HÌNH VẼ Hình 2.1: Các câu truy vấn lấy dự liệu từ website http://overpass-turbo.2: Phạm vi dữ liệu đ°ợc tải về .3: Các tùy chọn định dạng dữ liệu tải về .4: Dữ liệu tải về đ°ợc l°u d°ới dạng file json .5: Dữ liệu một điểm trong file data.6: Dữ liệu một đoạn đ°ờng trong file data .7: Dữ liệu trong đồ thị graph .8: Dữ liệu trong đồ thị kiểm tra graphtest .9: Kết quả kiểm tra thuật toán Dijkstra, Bellman-Ford và Floyd- Warshall với dữ liệu graphtest .10: Chạy thử ch°¡ng trình với dữ liệu dự án .11: Kết quả kiểm tra thuật toán Dijkstra, Bellman-Ford và Floyd- Warshall với dữ liệu dự án .14: S¡ đồ nghiệp vụ <Tìm đ°ờng đi ngắn nhất= .15: Biểu đồ Use Case <Tìm đ°ờng đi ngắn nhất= .16: Biểu đồ Tuần tự <Chọn ph°¡ng tiện= .17: Biểu đồ Tuần tự <Chọn điểm bắt đầu= .18: Biểu đồ Tuần tự <Chọn điểm đến= .19: Biểu đồ Tuần tự <Tìm đ°ờng đi ngắn nhất= .20: Biểu đồ Lớp <Tìm đ°ờng đi ngắn nhất= .1: Kiểm tra Nodejs đã cài thành công .3: Giao diện website.4: Kết quả thử nghiệm gợi ý tìm kiếm địa điểm .5: Kết quả chạy thử đ°ờng đi không có đ°ờng một chiều .6: Kết quả chạy thử đi vào đ°ờng một chiều với ô tô .7: Kết quả chạy thử đi vào đ°ờng một chiều với xe máy .8: Kết quả chạy thử đi vào đ°ờng một chiều với đi bộ .9: Kết quả chạy thử đi vào đ°ờng cấm đi bộ và xe máy với ô tô.10: Kết quả chạy thử đi vào đ°ờng cấm đi bộ và xe máy với xe máy .11: Kết quả chạy thử đi vào đ°ờng cấm đi bộ và xe máy với đi bộ.12: Kết quả chạy thử đi vào đ°ờng cấm đi ô tô với xe ô tô .13: Kết quả chạy thử đi vào đ°ờng cấm đi ô tô với xe máy .14: Kết quả chạy thử đi vào đ°ờng cấm đi ô tô với đi bộ. 44 vii DANH MĀC BÀNG Bảng 2.1: ¯u nh°ợc điểm của các thuật toán tìm đ°ờng đi ngắn nhất .2: Khởi tạo khoảng cách ban đầu cho các đỉnh .3: Xét từ đỉnh gốc 0 đến đỉnh 3.4: Xét từ đỉnh gốc 0 đến đỉnh 5.5: Xét từ đỉnh gốc 0 đến đỉnh 5.6: Xét từ đỉnh gốc 0 đến đỉnh 5.7: Xét từ đỉnh gốc 0 đến đỉnh 6.8: Xét từ đỉnh gốc 0 đến đỉnh 7.9: Xét từ đỉnh gốc 0 đến đỉnh 8.10: Đỉnh nhỏ nhất từ đỉnh gốc 0 tới đỉnh 8 .11: Bảng đặc tả Use Case <Tìm đ°ờng đi ngắn nhất=.
Lý do chán đÁ tài Trong thời đ¿i hiện nay, công nghệ đã trở thành mát phần không thể thiếu trong mọi lĩnh vực cÿa cuác sống. Việc sử dāng công nghệ thông tin đã và đang thúc đẩy sự phát triển và cải thiện hiệu suất làm việc trong nhiều lĩnh vực. Trong lĩnh vực tìm đ°ờng, việc áp dāng công nghệ thông tin có thể đem l¿i nhiều lÿi ích và giải pháp cho các thách thāc hiện t¿i. Trong quá khā, việc tìm đ°ờng đi giữa hai địa điểm đã gặp phải nhiều h¿n chế và thách thāc.
Tr°ớc đây, việc tìm đ°ờng th°ờng phā thuác vào bản đồ giấy, h°ớng dẫn từ con ng°ời, hoặc sử dāng các hệ thống điều h°ớng cố định có h¿n chế về dữ liệu hoặc tính năng. Công nghệ thông tin đã đóng vai trò quan trọng trong việc giải quyết những h¿n chế này và cải thiện quá trình tìm đ°ờng đi. Sự phát triển cÿa công nghệ thông tin đã mở ra những c¡ hái mới trong việc tìm đ°ờng đi. Các dịch vā bản đồ trực tuyến và āng dāng điều h°ớng nh° Google Maps, OpenStreetMap đã cung cấp dữ liệu chính xác và cập nhật, cho phép ng°ời dùng tìm kiếm và lập kế ho¿ch đ°ờng đi mát cách nhanh chóng và thuận tiện h¡n.
Chính vì lẽ đó, em đã chọn đề tài "Tìm đ°ờng đi ngắn nhất trên bản đồ" cho dự án cÿa mình. Māc tiêu cÿa dự án là nghiên cāu và triển khai các thuật toán tìm đ°ờng đi nh° Dijkstra và tích hÿp chúng vào mát āng dāng web. Em tin rằng việc áp dāng công nghệ thông tin trong lĩnh vực này sẽ cung cấp mát giải pháp hiệu quả và tiện ích cho ng°ời dùng, giúp họ dễ dàng tìm ra đ°ờng đi ngắn nhất giữa hai địa điểm mát cách nhanh chóng và hiệu quả. Nái dung nghiên cąu - Nghiên cāu và phân tích các website tìm đ°ờng đi.
- Xác định yêu cầu và đề xuất xây dựng website. - Tìm hiểu về dữ liệu OpenStreetMap và cách sử dāng trong dự án. - Tìm hiểu cách hiển thị bản trên website qua th° viện Leaflet. - Tìm hiểu thuật toán tìm đ°ờng đi ngắn nhất.
- Lập trình website. Māc đích chán đÁ tài Māc tiêu chính cÿa đề tài là nghiên cāu và phát triển mát website nền tảng āng dāng tìm đ°ờng đi ngắn nhất trên bản đồ. Māc đích cÿa dự án là cung cấp cho ng°ời dùng mát công cā hiệu quả và tiện lÿi để tìm kiếm địa điểm, lập kế ho¿ch đ°ờng đi và hiển thị tuyến đ°ờng ngắn nhất giữa hai điểm trên bản đồ. Đồng thời, thông qua việc nghiên cāu và triển khai, em mong muốn nâng cao sự tiện ích và khả năng áp dāng cÿa công nghệ thông tin trong việc giải quyết vấn đề di chuyển và giao thông trong cuác sống hàng ngày cÿa mọi ng°ời.
Ph°¢ng pháp nghiên cąu a) Ph°¡ng pháp tiếp cận Tìm hiểu và phân tích các tài liệu, sách vở, bài báo và tài liệu trực tuyến liên quan đến các thuật toán và ph°¡ng pháp tìm đ°ờng đi ngắn nhất trên bản đồ. b) Ph°¡ng pháp thực nghiệm Thực hiện các thử nghiệm và thí nghiệm trên website mẫu (google maps, bing maps) để đánh giá hiệu suất và tính năng cÿa hệ thống tìm đ°ờng đi. c) Ph°¡ng pháp phân tích Phân tích các dữ liệu thu thập đ°ÿc từ các thử nghiệm và thí nghiệm để đánh giá hiệu suất và tính chính xác cÿa hệ thống tìm đ°ờng đi. d) Nghiên cāu phát triển Nghiên cāu và phát triển các thuật toán và ph°¡ng pháp mới để cải thiện hiệu suất và tính āng dāng cÿa hệ thống tìm đ°ờng đi.
e) T° duy thiết kế Áp dāng t° duy thiết kế để phát triển các giải pháp mới và sáng t¿o trong việc xây dựng website tìm đ°ờng đi. Ph¿m vi, đßi t°ÿng nghiên cąu căa đÁ tài a) Ph¿m vi nghiên cāu Phát triển mát website hoàn chỉnh tìm đ°ờng đi ngắn nhất trên bản đồ. b) Đối t°ÿng sử dāng 2 Bao gồm tất cả mọi ng°ời (những ng°ời dùng thông th°ờng và các nhóm đặc biệt nh° những ng°ời di chuyển hàng ngày, du khách, nhân viên giao hàng, v. c) Ph¿m vi nghiên cāu Địa lý: Khu vực nhỏ thành phố Hải phòng - Việt Nam.
Công nghệ: JavaScript, HTML, CSS, Nodejs, dữ liệu bản đồ cÿa OpenStreetMap. TâNG QUAN VÀ ĐÀ TÀI 1. Hiện tr¿ng hệ thống tìm đ°ờng đi ngắn nhất Trong thời đ¿i công nghệ ngày càng phát triển, các dịch vā tìm đ°ờng trực tuyến nh° Google Maps, Bing Maps và OpenStreetMap đã trở thành mát phần không thể thiếu trong cuác sống hàng ngày cÿa chúng ta. Các dịch vā này mang l¿i nhiều °u điểm, bao gồm giao diện trực quan, tính năng tìm kiếm m¿nh mẽ và việc cập nhật dữ liệu nhanh chóng, từ đó giúp ng°ời dùng dễ dàng lập kế ho¿ch và thực hiện các chuyến đi cÿa mình.
Tuy nhiên, không phải lúc nào các dịch vā này cũng đáp āng đ°ÿc mọi nhu cầu cÿa ng°ời dùng. Mặc dù các trải nghiệm ng°ời dùng trên Google Maps [6], Bing Maps [7] và OpenStreetMap [8] mang l¿i trải nghiệm tuyệt vời cho ng°ời dùng, nh°ng vẫn tồn t¿i những h¿n chế đáng l°u ý. Mát trong những thách thāc phổ biến là việc ng°ời dùng cần thay đổi địa điểm bắt đầu hoặc địa điểm đến khi tìm kiếm đ°ờng đi. Thay vì có thể chọn trực tiếp trên bản đồ, ng°ời dùng th°ờng phải nhấp và di chuyển biểu t°ÿng vị trí cÿa điểm bắt đầu hoặc điểm đến đến vị trí mong muốn.
Điều này không chỉ có thể trở nên phāc t¿p và tốn thời gian đặc biệt là trên thiết bị di đáng, mà còn gây khó khăn cho những ng°ời không quen thuác với công nghệ hoặc có khả năng thao tác h¿n chế. Với nhận thāc về những khó khăn này, đề tài cÿa em tập trung vào việc nghiên cāu và đề xuất xây dựng mát āng dāng trên nền tảng web tìm đ°ờng đi ngắn nhất. Āng dāng cÿa em sẽ tích hÿp trải nghiệm gÿi ý tìm kiếm thông minh và cho phép ng°ời dùng dễ dàng thay đổi địa điểm bắt đầu hoặc địa điểm đến bằng cách ch¿m trực tiếp trên bản đồ. Điều này giúp ng°ời dùng có thể chọn và tìm đ°ờng đi mát cách thuận tiện h¡n, giải quyết những thách thāc thực tế trong việc di chuyển hàng ngày.
Phát biểu bài toán Trong thời đ¿i công nghệ số hiện nay, việc tìm đ°ờng đi ngắn nhất giữa hai điểm trên bản đồ là mát yêu cầu phổ biến và cần thiết. Đặc biệt, với sự phát triển cÿa các āng dāng di đáng và trang web, việc cung cấp mát giao diện đ¡n giản và hiệu quả để tìm đ°ờng đi đã trở thành mát yêu cầu ngày càng tăng. 4 Bài toán đ°ÿc xây dựng nhằm māc đích cung cấp cho ng°ời dùng mát công cā thuận tiện và nhanh chóng để tìm đ°ờng đi từ mát điểm đến mát điểm khác. Với āng dāng này, ng°ời dùng có thể dễ dàng xác định con đ°ờng tối °u dựa trên lo¿i ph°¡ng tiện di chuyển, điểm xuất phát và điểm đến.