Bài toán người đưa thư và ứng dụng tìm lộ trình xe thu gom rác tối ưu ở thành phố Đồng Hới

Postman Problem and Application in finding optimal path of rubbish van in DongHoi City
Nơi đăng: KY HTKH HỆ THỐNG THÔNG TIN
The 1st Conference on Information Systems (tháng 04/2014), Số: , Trang: 97, Năm: 2014, Loại bài viết: Tham luận, Quốc gia: Việt Nam.

Tóm tắt:

Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Đồ thị được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau. Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai địa điểm trong một mạng giao thông, bài toán người du lịch, bài toán chọn địa điểm tối ưu, bài toán người đưa thư,… Bài toán người đưa thư là một trong số những bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế. Kết quả chính của bài báo là nghiên cứu thuật toán giải bài toán người đưa thư và xây dựng ứng dụng tìm kiếm lộ trình thu gom rác tối ưu trên địa bàn Thành phố Đồng Hới.

Từ khóa: đồ thị; mạng; bài toán người đưa thư; tối ưu; thuật toán.

Abstract:

Graph theory is an old mathematical discipline that has many modern applications. Graph can be applied to solve problems in many different fields such as transportation, communication, informatics, economy,… Graph with edge’s weights is used to solve such problem as shortest path between points in a transport network, travelling salesman problem, optimal place problem, postman problem,… The problem of finding optimal path of rubbish van can be modelled as the postman problem. The main contribution of this paper is to develop an algorithm solve the postman problem and give an interesting application of finding optimal path of rubbish van in DongHoi City.

Keywords: graph; network; postman problem; optimization; algorithm.