Một cách tiếp cận mới dựa trên giải thuật di truyền để tìm đường đi tối ưu của bài toán đa nguồn đi, đa đích đến trên google maps

 ISSN: 1859-2171 
e-ISSN: 2615-9562 
TNU Journal of Science and Technology 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 89 
MỘT CÁCH TIẾP CẬN MỚI DỰA TRÊN GIẢI THUẬT DI TRUYỀN 
ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CỦA BÀI TOÁN ĐA NGUỒN ĐI, ĐA ĐÍCH ĐẾN 
TRÊN GOOGLE MAPS 
Hoàng Phước Lộc1*, Nguyễn Phong1, Lê Thanh Hiếu2 
1Trường Cao đẳng Sư phạm Quảng Trị, 2Trường Đại học Sư phạm Huế 
TÓM TẮT 
Vấn đề tìm đường đi trong tập các nút để cho đường đi đơn ngắn nhất giữa 2 nút trong đồ thị đã 
được giải quyết bằng một số thuật toán như Dijkstra, Hueristic, Floyd,  Bài toán này gọi là bài 
toán đơn nguồn đi, đơn đích đến. Tuy nhiên, trong thực tế cuộc sống của chúng ta cần phải giải 
quyết bài toán phức tạp hơn là làm thế nào để tìm đường đi tối ưu nhất từ đa điểm lựa chọn xuất 
phát, đa điểm lựa chọn đích đến cho công việc của người đưa thư, người giao hàng hay đi du lịch 
hàng ngày, ... là vấn đề đang được quan tâm nghiên cứu. Những bài toán dạng này còn được gọi là 
bài toán đơn nguồn đi, đa đích đến hoặc đa nguồn đi, đa đích đến mà các giải thuật đang tồn tại 
như Dijkstra, Floyd, ... khó giải quyết được. Nghiên cứu này đề xuất thuật toán tối ưu dựa trên tiếp 
cận giải thuật di truyền để giải quyết bài toán tìm đường đi qua đa điểm, thuộc lớp bài toán đa 
nguồn đi, đa đích đến, từ đó đề xuất một ứng dụng tối ưu hóa chi phí đi lại dựa trên dữ liệu Google 
Maps. Kết quả thí nghiệm chỉ ra rằng phương pháp đề xuất tối ưu hơn về đường đi và thời gian khi 
so sánh với các ứng dụng phổ biến như Google Maps, Địa điểm và thuật toán Dijkstra. Nghiên cứu 
này hy vọng mang lại những nền tảng ứng dụng để giải các bài toán giao thông trong đời sống một 
cách hiệu quả. 
Từ khóa: Đường đi ngắn nhất, Đồ thị, Google Maps, Giải thuật di truyền, Đa nguồn đi đa đích đến 
Ngày nhận bài: 30/9/2019; Ngày hoàn thiện: 14/10/2019; Ngày đăng: 25/10/2019 
A NEW APPROACH BASED ON GENETIC ALGORITHM 
FOR FINDING THE OPTIMAL ROAD IN MULTI-SOURCE, 
MULTI-DESTINATION OF GOOGLE MAPS 
Hoang Phuoc Loc
1*
, Nguyen Phong
1
, Le Thanh Hieu
2 
1Quang Tri Teacher Training College, 2Hue University of Education 
ABSTRACT 
Searching path problem in two points of graph is solved by some algorithms such as Dijkstra, 
Hueristic, Floyd, etc. This problem is belong to single source, single destination problem. 
However, in our real life, we need to solve more complexity problems, which are how to find the 
optimal path through multi-source selection, multi-destination for some works such as postman, 
roundsman or travel man, etc. are interesting research problems. The Dijkstra and Floyd 
algorithms can not solve the finding path problem in multi-source and multi-destination. This 
research proposes an optimal algorithm based on genetic algorithm approach to solve finding path 
problem through multi-point, which belong to class of multi-source, multi-destination problem. 
And also proposes an application for optimizing travel cost based on Google Maps database. The 
experiment results pointed out that the proposed method is more optimal in time and travel cost in 
comparison with some real applications such as the Google Maps and Địa điểm applications, and 
also Dijkstra algorithm. We hope that, this study brings the application grounds to solve travel 
problems in the real life effectively. 
Key words: Shortest path, Graph, Google Maps, Genetic algorithm, Multiple sources multiple 
destinations 
Received: 30/9/2019; Revised: 14/10/2019; Published: 25/10/2019 
* Corresponding author. Email: loc_hp@qtttc.edu.vn 
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 90 
1. Giới thiệu 
Tìm đường đi ngắn nhất là bài toán được áp 
dụng rộng rãi trong giao thông, truyền thông 
và trong mạng máy tính. Nó giải quyết những 
thách thức để xác định một đường đi với lộ 
trình chi phí nhỏ nhất về khoảng cách, thời 
gian hay giá trị từ nguồn đến đích thỏa mãn 
những yêu cầu nào đó của người sử dụng. 
Trong lớp các bài toán tìm đường đi ngắn 
nhất, bài toán giao thông là một bài toán lớn, 
có tác động sâu rộng đến đời sống của con 
người về nhu cầu vận chuyển, đi lại với một 
lộ trình thông minh và ít chi phí nhất. Do đó, 
ứng dụng khoa học công nghệ vào phát triển 
các dịch vụ hỗ trợ để lựa chọn phương án 
giao thông tốt nhất là một yêu cầu luôn được 
đặt ra với những nhà nghiên cứu. 
Tuy nhiên, những công bố liên quan đến bài 
toán tìm đường đi ngắn nhất hầu hết giải 
quyết bài toán tìm đường đi ngắn nhất giữa 
một đỉnh nguồn và một đích đến. Những bài 
toán tìm đường đi giữa đơn nguồn đi và đa 
đích đến hoặc đa nguồn đi và đơn đích đến 
cũng đã được nghiên cứu nhưng kết quả vẫn 
còn khiêm tốn. Với bài toán tìm đường đi 
giữa Đa Nguồn Đi và Đa Đích Đến (ĐNĐ, 
ĐĐĐ) được mô tả là bài toán tìm điểm xuất 
phát tốt nhất trong n điểm và đồng thời phải 
tìm lộ trình qua tập đa điểm (n-1 điểm còn lại) 
được lựa chọn tùy ý theo một cách nào đó để 
đạt chi phí nhỏ nhất là bài toán lớn, phức tạp 
ít được nghiên cứu và công bố. Bài toán dạng 
này được bắt gặp rất phổ biến trong đời sống 
của chúng ta đặt ra như: Làm thế nào để 
người giao hàng hay người du lịch chọn một 
lộ trình trong tập n điểm cần đến với quãng 
đường ngắn nhất và chi phí đi lại rẻ nhất. Đây 
là những bài toán thực tế đang đặt ra và hết 
sức cần thiết mà đa số thuật toán tỏ ra không 
hiệu quả hoặc khó giải quyết được. Thuật 
toán Dijkstra được biết đến là một thuật toán 
phổ biến để tìm đường đi ngắn nhất trên đồ 
thị xuất phát từ một nguồn s và một đích đến t 
xác định. Hạn chế của thuật toán Dijkstra là 
khó để xác định được đường đi tối ưu nhất để 
đi qua n đỉnh nào đó mà đỉnh nguồn và đích 
là bất kỳ trong n đỉnh và những hạn chế khác 
được chỉ ra ở [1]. Những công bố gần đây cho 
thấy, với thuật toán Heuristic tìm ra đường đi 
tốt nhất trong đa nguồn đi của n nút nhưng chỉ 
giải quyết được trong một đích đến đơn của 
đồ thị [2]. Liang và Wenjia ở [3] cũng đề xuất 
một thuật toán mới để tìm đường đi trong đồ 
thị đa nguồn đi và một đích đến để giải quyết 
bài toán dịch vụ định tuyến trong truyền 
thông. Có thể nói rằng, các giải thuật 
Heuristic cũng tỏ ra hạn chế để giải quyết bài 
toán ĐNĐ, ĐĐĐ đã được chứng minh là bài 
toán có độ phức tạp NP-đầy đủ. 
Với những hạn chế về chi phí đường đi của 
thuật toán Dijkstra và các thuật toán Heuristic 
trong việc giải quyết các bài toán tìm đường 
đi ngắn nhất trên đồ thị, trên mạng định tuyến 
hay định đường đi của robot. Giải thuật di 
truyền (GA) ra đời và mang lại những ưu thế 
nỗi trội trong việc giải quyết bài toán tối ưu 
hóa đường đi này [4]. Hiện nay, giải thuật GA 
được ứng dụng trong khá nhiều lĩnh vực khác 
nhau như: tối ưu hóa đường đi trong mạng 
máy tính; tìm đường đi cho bản đồ video 
game; tìm đường đi ngắn nhất cho rô bốt, kết 
hợp lai ghép giải thuật GA với các giải thuật 
khác để giải quyết bài toán nào đó. Ở [5], các 
tác giả sử dụng GA trong việc tối ưu hóa định 
tuyến để chuyển các tín hiệu giao thông từ 
nguồn đến đích. Một nghiên cứu khác ứng 
dụng GA để tìm đường đi đơn trong đồ thị đa 
nút của mạng chuyển mạch gói với thời gian 
chấp nhận được [6]. Những nghiên cứu tương 
tự sử dụng giải thuật GA để tìm đường đi 
ngắn nhất trong mạng chuyển mạch gói giữa 
nút nguồn và nút đích cũng được chỉ ra ở [7], 
[8], [9] và [10]. Tuy nhiên, những công bố 
này chỉ tập trung nghiên cứu để tìm đường đi 
tối ưu từ nguồn đến đích hoặc cho kết quả 
đường đi đơn từ đồ thị đa đỉnh xuất phát từ 
một đỉnh nguồn. Ở [11], các tác giả thể hiện 
một tiếp cận giải thuật di truyền mới để giải 
quyết vấn đề bài toán tìm đường đi ngắn nhất 
giữa hai thành phố chỉ ra của bản đồ giao 
thông. Một số ứng dụng trên thiết bị di động 
sử dụng GA để xác định lộ trình đường đi 
giữa 2 nút giao thông cũng được công bố ở 
[12], [13] và [14]. Những ứng dụng này giải 
quyết các bài toán thuộc lớp đơn nguồn đi, 
đơn đích đến đơn giản và lĩnh vực này có 
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 91 
nhiều công bố. Một hướng tiếp cận khác là 
tác giả sử dụng thuật toán lai ghép GA với 
giải thuật tối ưu hóa đàn kiến hoặc giải thuật 
Dijkstra và GA để giải quyết bài toán tìm 
đường đi ngắn nhất của mạng không dây [15] 
và [16]. Những ứng dụng được công bố này 
cũng chủ yếu tập trung giải quyết bài toán tìm 
đường đi ngắn nhất giữa 2 nút của bản đồ hay 
mạng không dây. Từ những phân tích ở trên, 
có thể dễ nhận thấy giải thuật di truyền được 
ứng dụng rộng rãi trong nhiều lĩnh vực để giải 
quyết các bài toán thực tế của đời sống con 
người. Tuy nhiên, những ứng dụng đề cập ở 
trên thuộc lớp ứng dụng chủ yếu là tìm đường 
đi tối ưu từ nguồn đến đích xác định hoặc cho 
kết quả đường đi đơn trong đồ thị đa đỉnh 
xuất phát từ một đỉnh nguồn. Các ứng dụng 
mở rộng trên bản đồ đa nguồn lựa chọn và đa 
đích đến nhằm tìm kiếm giải pháp tối ưu cho 
bài toán giao thông vẫn còn chưa được nghiên 
cứu đúng mức, chưa tối ưu trong việc đưa ra 
lời giải cuối hoặc chưa hỗ trợ tìm kiếm qua 
ĐNĐ, ĐĐĐ. Từ những lập luận trên, trong 
bài báo này các tác giả đã nghiên cứu và đề 
xuất một thuật toán mới dựa trên tiếp cận di 
truyền để tìm đường đi tối ứu nhất trong 
ĐNĐ, ĐĐĐ dựa trên dữ liệu vào của Google 
Maps. Kết quả thực nghiệm chỉ ra rằng 
phương pháp đề xuất tối ưu hơn khi so sánh 
với kết quả tìm kiếm đường đi của ứng dụng 
Google Maps, ứng dụng Địa điểm 
( và so sánh với kết 
quả của giải thuật Dijkstra. 
Phần còn lại của bài báo được cấu trúc như 
sau: Phần 2 mô tả về giải thuật di truyền và 
giải pháp đề xuất. Đề xuất thuật toán dựa trên 
cách tiếp cận của giải thuật di truyền để tìm 
đường đi ngắn nhất trong đa điểm của Google 
Maps được đặt ở Phần 3. Kết quả thực 
nghiệm và so sánh đánh giá với các ứng dụng 
và giải thuật khác được đặt ở phần 4, những 
kết luận và kiến nghị được đặt ở Phần 5 của 
bài báo. 
2. Giải thuật di truyền 
Giải thuật di truyền dựa trên ý tưởng quá trình 
tiến hóa của sinh vật trong tự nhiên để mô 
phỏng giải thuật nhằm giải quyết các bài toán 
tối ưu hóa và đưa ra lời giải tốt nhất với mong 
muốn tối ưu theo sự tiến hóa của các loài vật 
trong thế giới tự nhiên. 
Giải thuật di truyền được mô tả một cách cơ 
bản như sau. Đầu tiên, chúng ta xác định các 
tham số vào của bài toán và sau đó khởi tạo 
quần thể ban đầu là các tập nghiệm của bài 
toán. Tiếp đến, xác định độ thích nghi của các 
cá thể trong quần thể, tức là thỏa mãn điều 
kiện của bài toán nêu ra và nếu lời giải đạt tối 
ưu thì thông báo kết quả của bài toán và kết 
thúc. Ngược lại, nếu lời giải chưa tối ưu, ta 
tiến hành chọn lọc các cá thể theo một 
ngưỡng nào đó và tiến hành lai tạo nhằm tạo 
ra quần thể mới. Cuối cùng tiến hành đột biến 
nhằm tạo ra các cá thể có độ thích nghi cao 
hơn. Quá trình này lặp lại và được gọi là quá 
trình di truyền để tạo ra các nghiệm tối ưu 
nhất. Dựa vào sơ đồ giải thuật này, các tác giả 
đã xây dựng, cải tiến thuật toán và tạo một 
ứng dụng Demo1 để tính chi phí đi lại tối ưu 
trong đa điểm. Ở thí nghiệm mô phỏng này 
các trọng số của bài toán được sinh ra một 
cách ngẫu nhiên. Bảng 1 mô tả một phần ma 
trận đường đi và các phương án lựa chọn 
được sinh ra từ thuật toán. Theo kết quả của 
Bảng 1 thì phương án lựa chọn theo tiếp cận 
ĐNĐ, ĐĐĐ để đạt đường đi tối ưu nhất là tập 
các đỉnh theo thứ tự xuất phát: 14 11 4 9 15 1 
7 19 6 17 10 2 8 13 0 18 3 12 16 5, với quãng 
đường ngắn nhất là 30. Nếu thực hiện giải 
thuật theo tiếp cận đơn nguồn đi, đa đích đến 
và đỉnh xuất phát là đỉnh 0 và đỉnh đến là N 
đỉnh bất kỳ thì lộ trình tối ưu nhất là: 0 18 3 9 
15 1 7 19 6 2 8 13 12 16 5 14 11 4 17 10 với 
quãng đường là 39. Từ đây ta dễ dàng nhận 
thấy rằng trong các bài toán giao thông, cách 
tiếp cận ĐNĐ, ĐĐĐ là bài toán phức tạp với 
nhiều ràng buộc, tuy nhiên kết quả chi phí 
thực tế của người sử dụng là tối ưu hơn nhiều 
cách tiếp cận đơn nguồn đi, đơn đích đến 
hoặc đơn nguồn đi, đa đích đến. 
3. Đề xuất thuật toán và ứng dụng tìm 
đường đi tối ưu trong ĐNĐ, ĐĐĐ 
Trong thực tế cho thấy, bài toán vận tải hay 
du lịch, người sử dụng muốn lập một kế 
hoạch để thực hiện lộ trình N điểm đến với 
1  
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 92 
một chi phí về lộ trình nhỏ nhất là một nhu 
cầu lớn. Với ý nghĩa đó, các tác giả đã đề xuất 
thuật toán dựa trên tiếp cận của giải thuật di 
truyền và xây dựng hệ thống tìm kiếm đường 
đi trong đa điểm Google Maps. Hình 1 mô tả 
thuật toán tìm kiếm đường đi tối ưu trong đa 
điểm Google Maps. Tiến trình của thuật toán 
được mô tả một cách ngắn gọn bằng ngôn 
ngữ tự nhiên như sau: Trước tiên, thuật toán 
xử lý dữ liệu và đọc các điểm từ Google 
Maps vào ma trận. Kế đến, tiến hành xử lý 
mảng và tính khoảng cách giữa các điểm. Sau 
đó kiểm tra có hay không sự tồn tại của 
đường đi theo yêu cầu của bài toán. Nếu 
không tồn tại đường đi thì thông báo đường đi 
không tồn tại và kết thúc. Nếu tồn tại đường 
đi, thuật toán tiến hành kiểm tra có tồn tại 
đường đi đơn không, nếu chỉ tồn tại đường đi 
đơn thì thông báo tồn tại đường đi duy nhất 
và tiến hành xuất đường đi trên Google Maps 
và kết thúc. Nếu đường đi tồn tại và không 
duy nhất, chúng ta chuyển sang bước tiếp 
theo là tìm đường đi tối ưu trong đa điểm đã 
xuất ra ở ma trận dựa trên tiếp cận của giải 
thuật GA. Sau quá trình tính toán sẽ cho ra 
đường đi tối ưu và chuyển sang bước tiếp 
theo là xuất đường đi trên Google Maps và 
kết thúc thuật toán. Thuật toán: CGTĐĐG liệt 
kê chi tiết những modul cơ bản của giải thuật 
cải tiến của Hình 1. Hình 2 mô tả ứng dụng 
Demo
2
 được phát triển nhằm hỗ trợ người 
dùng tìm đường đi tối ưu trong đa điểm 
Google Maps. Hình 2 còn thể hiện lộ trình 
đường đi chi tiết trên bản đồ để người dùng có 
thể nhìn thấy một cách trực quan đường đi của 
mình trên máy tính, tablet hay thiết bị di động. 
Đồng thời hiển thị thông tin tóm tắt gồm chi phí 
quãng đường, thời gian đi dự kiến bằng taxi, đề 
xuất lộ trình điểm khởi đầu, các điểm cần đi qua 
và điểm đầu cuối cần đến. 
Bảng 1. Mô tả ma trận đường đi và những phương án lựa chọn2 
Chuỗi gen di truyền Quãng đường 
14 11 4 9 15 1 7 19 6 17 10 2 8 13 0 18 3 12 16 5 [30] 
7 19 6 2 8 16 5 14 11 4 13 0 18 3 9 15 1 17 10 12 [37] 
2 8 16 5 14 11 4 13 0 18 3 9 15 1 7 17 10 12 19 6 [40] 
10 17 12 3 9 15 1 7 19 6 2 8 16 5 14 11 4 13 0 18 [44] 
15 1 7 19 6 2 8 16 5 14 11 4 13 0 18 3 9 12 10 17 [44] 
8 10 16 5 14 11 4 13 0 18 3 9 15 1 7 19 6 2 17 12 [49] 
3 9 15 7 19 6 2 8 16 5 14 11 4 13 0 18 1 12 10 17 [52] 
13 8 16 5 14 11 4 2 0 18 3 9 7 19 6 17 10 12 15 1 [58] 
16 5 14 11 4 13 0 18 3 9 15 1 7 19 6 2 8 17 10 12 [41] 
19 6 2 8 16 5 14 11 4 13 0 18 3 9 15 1 7 12 10 17 [47] 
Hình 1. Tìm đường đi tối ưu trong ĐNĐ, ĐĐĐ trên Google Maps theo tiếp cận di truyền 
2
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 93 
Bảng 2. Danh sách đa điểm thực nghiệm (N=10) 
STT Địa điểm cần đến 
1 Hùng Vương, Đông Hà, Quảng Trị 
2 Trần Cao Vân, Đông Hà, Quảng Trị 
3 Lê Lợi, Đông Hà, Quảng Trị 
4 Lê Duẩn, Đông Hà, Quảng Trị 
5 Hàm Nghi, Đông Hà, Quảng Trị 
6 Nguyễn Huệ, Đông Hà, Quảng Trị 
7 Trần Hưng Đạo, Đông Hà, Quảng Trị 
8 Nguyễn Đình Chiểu, Đông Hà, Quảng Trị 
9 Lý Thường Kiệt, Đông Hà, Quảng Trị 
10 Điện Biên Phủ, Đông Hà, Quảng Trị 
Thuật toán: CGTĐĐG (Cải tiến Giải thuật di truyền Tìm đường đi trên ĐNĐ, 
ĐĐĐ của Google Maps) 
Input: Đa điểm tìm kiếm trên Google Maps. 
Output: Một đường đi tối ưu qua đa điểm trên Google Maps. 
Method: 
1: Tạo một danh sách sẽ chứa đa điểm trên bản đồ; 
2: { 
3: Tạo mảng chứa đa điểm cần tìm kiếm; 
4: Thêm mảng đa điểm vào các vị trí của Google Maps tương ứng; 
5: } 
6: Xử lý đa điểm trên Google Maps; 
7: { 
8: Xử lý đa điểm; 
9: Kiểm tra đường đi tồn tại; 
10: Tính toán khoảng cách của 2 điểm tồn tại trên Google Maps; 
11: } 
12: Truy vấn tính toán đường đi ngắn nhất của ĐNĐ, ĐĐĐ dựa trên tiếp cận di 
truyền; 
//Có N phương án chọn nguồn đi và N phương án chọn đích đến chưa xác định. 
13: { 
14: Khởi tạo các tham số (các điểm, quần thể, GEN, đột biến, .vv); 
15: Tìm và chọn đường đi tối ưu; 
16: { 
17: Sinh ra và chọn lọc những phương án GEN tối ưu; 
18: { 
19: Tìm và chọn lọc chuỗi GEN tốt nhất trong các GEN là 
phương án đường đi tối ưu; 
20: } 
21: } 
23: } 
24: Thông báo đương đi tối ưu qua N điểm trên Google Maps; 
25: Return. 
4. Kết quả thực nghiệm 
Trong nghiên cứu này, các tác giả đã tiến 
hành thực nghiệm để tìm đường đi tối ưu nhất 
trong ĐNĐ, ĐĐĐ (N=10), với lộ trình mỗi 
điểm là tọa độ tìm kiếm điểm gần nhất của 
đường giao nhau từ cơ sở dữ liệu ở Google 
Maps được chỉ ra ở Bảng 2. Hình 2 là kết quả 
thực nghiệm của phương pháp đề xuất, nó chỉ 
ra thứ tự các nút được đi qua để cho kết quả 
đường đi tối ưu nhất. Ở bài báo này, các tác 
giả cũng đã tiến hành chạy thực nghiệm để so 
sánh giải pháp đề xuất với các ứng dụng phổ 
biến: (1) Google Maps 
(https://www.google.com/maps/). (2) Ứng 
dụng Địa điểm ( là 
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 94 
một trong những ứng dụng tìm đường đi phổ 
biến nhất ở Việt Nam và (3) thuật toán 
Dijkstra. Kết quả so sánh được thể hiện chi 
tiết ở Bảng 3. Kết quả này cho thấy phương 
pháp đề xuất tối ưu hơn các ứng dụng khác cả 
về đường đi tối ưu và chi phí thời gian. Ứng 
dụng đề xuất thực hiện lộ trình với quãng 
đường là 21,8 Km và thời gian dự kiến bằng 
phương tiện ô tô là 46,65 phút, chi tiết được 
thể hiện ở Hình 2. Trong khi đó ứng dụng 
Google Maps (1) thực hiện lộ trình với quãng 
đường là 27,1 Km và thời gian dự kiến là 57 
phút. Cụ thể kết quả được chỉ ra ở Hình 3. 
Ứng dụng tìm địa điểm (2) không hỗ trợ tìm 
kiếm đường đi theo dạng ĐNĐ, ĐĐĐ. Ứng 
dụng này chỉ hỗ trợ thực hiện tìm kiếm đường 
đi theo đoạn kiểu một nguồn đi, một đích đến, 
chi tiết được chỉ ra ở Hình 4. Trong nghiên 
cứu này, các tác giả cũng tiến hành cài đặt 
dựa trên thuật toán Dijkstra để tìm kiếm 
đường đi tối ưu cho bài toán đề cập. Kết quả 
thuật toán Dijkstra không thể thực hiện được 
bài toán với ràng buộc lựa chọn ĐNĐ, ĐĐĐ. 
Kết quả thực nghiệm này cho thấy rằng, 
phương pháp đề xuất để tìm kiếm đường đi 
tối ưu trong đa điểm với dữ liệu và bản đồ 
thực tế được chiết xuất từ Google Maps có 
nhiều ưu thế nổi trội và tối ưu hơn các ứng 
dụng phổ biến khác được so sánh. Phương 
pháp này có thể được sử dụng để xây dựng 
các ứng dụng về bài toán liên quan đến giao 
thông trong thế giới thực nhằm tiết kiệm chi 
phí và hứa hẹn mang lại hiệu quả kinh tế lớn 
trong thế giới số ngày nay. 
Hình 2. Kết quả tìm đường đi tối ưu trong đa điểm của phương pháp đề xuất 
Bảng 3. Kết quả so sánh thực nghiệm 
 Phương pháp đề xuất 
(CGTĐĐG) 
Google Maps 
(1) 
Địa điểm 
(2) 
Thuật toán 
Dijkstra (3) 
Quãng đường 
(Km) 
21,8 27,1 (#), (*) (##) 
Chi phí thời gian 
(phút) 
46,65 58 (*) (##) 
#: Ứng dụng không hỗ trợ để thực hiện tìm kiếm đường đi theo dạng ĐNĐ, ĐĐĐ. 
(*): Ứng dụng chỉ thực hiện tìm kiếm đường đi theo đoạn kiểu một nguồn đi, một đích đến, kết quả đường 
đi và chi phí thời gian được tính theo lộ trình mà người sử dụng nhập vào. 
(##): Thuật toán cài đặt không thể thực hiện được lời giải với bài toán ĐNĐ, ĐĐĐ. 
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 95 
Hình 3. Tìm đường đi trong đa điểm của ứng dụng Google Maps 
Hình 4. Tìm đường đi của ứng dụng Địa điểm (diadiem.com) 
5. Kết luận và kiến nghị 
Trong bối cảnh ứng dụng công nghệ thông tin 
theo xu thế thời đại công nghiệp 4.0 đang 
diễn ra và hướng đến một cuộc cách mạng 5.0 
sắp tới. Việc xây dựng các giải pháp tối ưu để 
giảm chi phí cho bài toán đi lại càng trở nên 
cần thiết nhằm góp phần phát triển kinh tế, xã 
hội của mỗi quốc gia trên thế giới. Trong bài 
báo này, các tác giả đã dựa trên tiếp cận của 
giải thuật di truyền để xây dựng một giải 
thuật nhằm tìm kiếm đường đi tối ưu trên cơ 
sở dữ liệu đa điểm của Google Maps. Giải 
thuật này được dùng để phát triển một ứng 
dụng tìm kiếm đường đi tối ưu cho bài toán 
ĐNĐ, ĐĐĐ trên bản đồ Google Maps. Ứng 
dụng thực nghiệm được đánh giá qua tập dữ 
liệu vào N=10 nút. Kết quả thực nghiệm này 
được so sánh với các ứng dụng phổ biến như 
https://www.google.com/maps/, 
 và thuật toán 
Dijkstra. Kết quả so sánh cho thấy giải pháp 
đề xuất tối ưu hơn các ứng dụng và thuật toán 
được so sánh về chi phí khoảng cách và thời 
gian. Với kết quả này, các tác giả hy vọng 
giải pháp sẽ được sử dụng vào các lĩnh vực 
khác nhau trong giao thông, trong du lịch, 
trong vận hay các công việc khác. 
Trong nghiên cứu này, khi sử dụng ứng dụng 
được đề xuất để tìm đường đi với số điểm khá 
lớn, bước xử lý mảng và tính khoảng cách các 
điểm của thuật toán còn chậm. Do mất thời 
gian hàng đợi khi đọc và chuyển đổi dữ liệu 
thực phụ thuộc vào dữ liệu của Google Maps. 
Đây cũng là công việc mà nhóm tác giả sẽ 
nghiên cứu để cải tiến và đề xuất giải thuật tối 
ưu hơn trong tương lai. Hơn nữa, trên nền 
ứng dụng này, xây dựng các ứng dụng đi kèm 
để giải quyết các công việc khác nhằm áp 
dụng vào đời sống xã hội cũng là nhiệm vụ 
trong tương lai mà nhóm tác giả hướng đến. 
Hoàng Phước Lộc và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ ĐHTN 208(15): 89 - 96 
 Email: jst@tnu.edu.vn 96 
TÀI LIỆU THAM KHẢO 
[1]. R. Avash and J. Ashi, "Genetic Algorithm 
based Logistics Route Planning," International 
Journal of Innovation, Management and 
Technology, vol. 1, pp. 4, 2009. 
[2]. K. Faisal and A. Nabil, "An Efficient Multiple 
Sources Single-Destination MSSD) Heuristic 
Algorithm Using Nodes Exclusions," 
International Journal of Soft Computing · January 
2015, vol. 10, pp. 6, 2015. 
[3]. Z. Liang and W. Wenjia, 
"A New Path Search Algorithm for Providing 
Paths among Multiple Origins and 
One Single Destination"International 
Journal of Computer Science and Application (IJC
SA), vol. 3, pp. 5, 2014. 
[4]. S. Yagvalkya, C. S. Subhash, and B. Manisha, 
"Comparison of Dijkstra’s Shortest Path 
Algorithm with Genetic Algorithm for Static and 
Dynamic Routing Network," International 
Journal of Electronics and Computer Science 
Engineering, vol. 1, pp. 10, 2016. 
[5]. K. Rakesh and K. Mahesh, "Exploring 
Genetic Algorithm for Shortest Path Optimization 
in Data Networks," Global Journal of Computer 
Science and Technology, vol. 10, p. 5, 2010. 
[6]. V. Hars, B. Shreejith, H. Wanjun, R. Miguel, 
S. Arularasi, T. Limin, M. Paolo, T. Marco, and F. 
Andrea, "Finding a Simple Path with Multiple 
Must-include Nodes," 2009. 
[7]. G. Bilal and S. J. L., "Genetic Algorithm 
Finding the Shortest Path in Networks," presented 
at the Fifth International Conference on Genetic 
and Evolutionary Computing, San Diego, 
California, USA, 2011. 
[8]. V. Anusuya and R. Kavitha, "Genetic 
Algorithm for Finding Shortest Path in a 
Network," Intern. J. Fuzzy Mathematical Archive, 
vol. 2, pp. 6, 2013. 
[9]. C. Anu and K. P. Neeraj, "Genetic algorithm 
for shortest path in packet switching networks," 
Journal of Theoretical and Applied Information 
Technology, vol. 29, pp. 11, 2011. 
[10]. Y. H. Ahmed and M. R. Hassan, "A Genetic 
Algorithm To Solve The Minimum-Cost Paths 
Tree Problem," International Journal of Computer 
Networks & Communications (IJCNC), vol. 7, pp. 
11, 2015. 
[11]. A. Sachith, G. Baladasan, and K. Saluka, "A 
Genetic Algorithm Approach to Solve the Shortest 
Path Problem for Road Maps," in International 
Conference on Information and Automation, 
Colombo, Sri Lanka, 2005. 
[12]. A. Umit, R. K. Ismail, G. Cevdet, Y. Beyza, 
and M. O. Ilhami, "An Idea for Finding the 
Shortest Driving Time Using Genetic Algorithm 
Based Routing Approach on Mobile Devices," 
International Journal of Mathematics and 
Computers In Simulation, vol. 6, pp. 8, 2012. 
[13]. B. Saeed and A. A. Alia, "Developing a 
Genetic Algorithm for Solving Shortest Path 
Problem," presented at the International 
conference on Urpan planing and transportation, 
Heraklion, Crete Island, Greece, 2008. 
[14]. A. Nouara and C. Mohamed, "Mobile Robots 
Path Planning using Genetic Algorithms," in The 
Seventh International Conference on Autonomic 
and Autonomous Systems, 2011. 
[15]. B. Eşref and B. Selami, "A Hybrid Genetic 
Algorithm for Mobile Robot Shortest Path 
Problem," International Journal of Intelligent 
Systems and Applications in Engineering, vol. 1, 
pp. 8, 2016. 
[16]. S. Aravindh and G. Michael, "Hybrid Of Ant 
Colony Optimization And Genetic Algorithm For 
Shortest Path In Wireless Mesh Networks," 
Journal of Global Research in Computer Science, 
vol. 3, pp. 4, 2012.