HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Nguyễn Quang Hưng
TÌM HIỂU GIẢI THUẬT ĐỊNH TUYẾN XE, ỨNG DỤNG
TRONG TỐI ƯU LỘ TRÌNH THU GOM RÁC THẢI TRONG
KHU CÔNG NGHIỆP
CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN
Mã số: 60.48.01.04
TÓM TẮT LUẬN VĂN THẠC SỸ
( Theo định hướng ứng dụng)
Hà Nội - 2021
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: TS Nguyễn Trọng Khánh
Phản biện 1: PGS.TS Nguyễn Linh Giang
Phản biện 2: PGS.TS Bùi Thu Lâm
Luận văn này được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học
viện Công nghệ Bưu chính Viễn thông
Vào lúc: 9 giờ 30phút ngày 15 tháng 01 năm 2022
Có thể tìm hiểu luận văn này tại:
Thư viện của Học viện Công nghệ Bưu chính Viễn thông
1
PHẦN MỞ ĐẦU
1. Lý do chọn đề tài
Hiện nay, vấn đề bảo vệ môi trường luôn là mối quan tâm hàng đầu của nhiều quốc gia
trên thế giới, bởi vấn đề ô nhiễm môi trường đã đang trở nên ngày càng cấp bách hơn bao
giờ hết. Đã có nhiều phương án cũng như nhiều chiến dịch được mở ra để khắc phục, giảm
thiểu đi hậu quả ô nhiễm môi trường như sự kiện “Giờ Trái Đất” khi tất cả các nước cùng
hưởng ứng việc tắt đèn vì môi trường. Cho nên chúng ta phải cùng chung tay đẩy mạnh
việc bảo vệ môi trường đạt kết quả nhiều hơn nữa. Bảo vệ môi trường đồng nghĩa với việc
tự bảo vệ cho sức khỏe của chính bản thân mình. Hành động của mỗi cá nhân có vai trò rất
quan trọng đối với công tác bảo vệ môi trường. Bởi hơn ai hết con người là tác nhân quan
trọng nhất trong việc bảo vệ môi trường.
Việt Nam sau hơn 20 năm đổi mới, vị thế và diện mạo của đất nước đã hoàn toàn
thay đổi. Tuy nhiên, phát triển là một quá trình đa diện và không dễ để điều hoà mối quan
hệ giữa phát triển kinh tế và bảo vệ môi trường, cho dù rất nhiều các quốc gia trên thế giới
đã quen và đã áp dụng chiến lược phát triển bền vững. Sau Vedan, Miwon…sẽ còn không
ít các công ty, tập đoàn khác có tên trong danh sách gây ô nhiễm môi trường nghiêm trọng.
Tại các khu công nghiệp, rác thải cần được thu gom và đưa đi xử lý tại các bãi khá nhiều.
Quản lý rác thải ở khu công nghiệp (RTCN) hiệu quả là một trong những trọng tâm của
những chính sách phát triển môi trường bền vững. Việc quản lý kém hiệu quả RTCN, đặc
biệt ở khu vực KCN, là mối đe dọa tới sức khỏe cộng đồng, làm ô nhiễm môi trường dẫn
tới giảm chất lượng cuộc sống của người dân. Hơn nữa, quản lý RTCN không khoa học
làm phát sinh không chỉ nhiều chi phí tốn kém trong hiện tại mà còn về lâu dài. Qua khảo
sát thì chưa có nhiều đề tài hướng tới giải quyết bài toán tối ưu thu gom rác thải trong Khu
công nghiệp.
2. Tổng quan về vấn đề nghiên cứu
Luận văn sẽ tập trung nghiên cứu các bài toán định tuyến xe, và biến thể của chúng.
Để từ đó áp dụng cho bài toán thu gom rác thải khu công nghiệp, với các ràng buộc liên
quan đến thể tích xe cuốn ép rác, quãng đường phải đi, giới hạn khung thời gian thu gom
...
2
3. Đối tượng và phạm vi nghiên cứu
- Giải pháp đưa ra sẽ được áp dụng thử nghiệm cho việc thu gom rác thải tại khu công
nghiệp.
- Phạm vi: Tìm hiểu các giải thuật tối ưu tìm đường đi ngắn nhất có ràng buộc về thời
gian. Áp dụng bài toán thu gom rác thải ràng buộc thời gian theo ca làm việc.
Xây dựng thử nghiệm hệ thống đề xuất đường đi thu gom rác thải trong khu công
nghiệp có tính các ràng buộc thời gian, hệ thống nhận đầu vào là các bản đồ điểm đổ rác,
lưu lượng rác tại các điểm, số lượng xe, dung lượng thùng xe, thời gian cần phải xong. Đầu
ra là quãng đường tối ưu.
4. Phương pháp nghiên cứu
- Nghiên cứu lý thuyết:
- Thực hiện tìm hiểu một số giải thuật áp dụng cho bài toán định tuyến xe VRP
(Vehicle Routing Problem – VRP).
- Bài toán định tuyến xe với cửa sổ thời gian VRPTW (Vehicle Routing Problem with
Time Windows).
- Nghiên cứu thực nghiệm:
Dữ liệu thực tế được hỗ trợ từ đề tài cấp Sở HN.
Để tính toán đề các yếu tố động, đề tài cũng phát triển một mô hình dựa trên tác tử (Agent
Based Model - ABM) để mô phỏng lộ trình tối ưu trong ngữ cảnh động. Từ đó đối chiếu
và so sánh hai kết quả với nhau.
3
CHƯƠNG 1. TỔNG QUAN VỀ BÀI TOÁN ĐỊNH TUYẾN XE
Chương này sẽ khái quát về lĩnh vực tối ưu hóa tổng hợp, bài toán người giao hàng, bài
toán định tuyến xe và một số biến thể đồng thời trong chương cũng thực hiện giới thiệu
một số giải thuật áp dụng cho bài toán VRP, như giải thuật láng giềng gần nhất nhằm tìm
kiếm đường đi trên đồ thị với một chi phí tối thiểu. Bài toán định tuyến xe với cửa sổ thời
gian VRPTW.
1.1. Tổng quan về lĩnh vực tối ưu hóa tổ hợp
Tối ưu hóa bản chất là một ngành Toán học và được ứng dụng hiệu quả trong nhiều
ngành khác nhau. Bài toán tối ưu tổ hợp là bài toán chỉ quan tâm đến một cấu hình “tốt nhất”
theo một nghĩa nào đấy. Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp
đã đóng góp một phần đáng kể trong việc xây dựng những thuật toán hữu hiệu. Từ các lĩnh
vực như Công nghệ thông tin, thiết kế chế tạo máy đến các lĩnh vực khác như quy hoạch tài
nguyên, điều khiển tự động, quản trị kinh doanh, kiến trúc đô thị, … đều có rất nhiều ứng
dụng, đặc biệt trong việc xây dựng hệ hỗ trợ ra quyết định và phát triển các hệ thống lớn. Do
đó, các lĩnh vực của tối ưu hóa ngày càng trở nên đa dạng.
Bài toán tối ưu tổ hợp có thể phát biểu dưới hình thức toán học như sau:
Tìm X∈ D : f (X) →min (max)
1.2. Bài toán định tuyến xe và một số biến thể
1.2.1 Phát biểu bài toán định tuyến xe
Bài toán Người bán hàng (Travelling Salesman Problem - gọi tắt là TSP) chính là
trường hợp đơn giản nhất của bài toán định tuyến xe (Vehicle Routing Problem - VRP) với
một xe giao hàng duy nhất - người bán hàng. Bài toán yêu cầu tìm đường đi ngắn nhất cho
nhân viên bán hàng (traveling salesman), nhân viên bán hàng xuất phát từ một thành phố, đi
qua lần lượt tất cả các thành phố có trong lộ trình duy nhất một lần và quay về thành phố ban
đầu với chi phí thấp nhất. Nhiệm vụ của bài toán là phải tìm một lộ trình tối ưu nhất (ví dụ
như tổng độ dài quãng đường dịch chuyển là nhỏ nhất) để người bán hàng đi giao hàng cho
tất cả thành phố theo dự định, mỗi thành phố được ghé thăm duy nhất một lần.
Bài toán TSP có thể được mô hình hóa bằng một đồ thị, trong đó các đỉnh của đồ thị
tương ứng với các thành phố, các cạnh tương ứng với đường đi giữa các thành phố, khoảng
cách giữa các thành phố là trọng số tương ứng của các cạnh nối chúng. Lời giải tối ưu của bài
