LuanVan.vnLuận Văn
Gửi thư

Phương pháp tìm kiếm lân cận rộng thích ứng cho một số lớp bài toán định tuyến phương tiện

Luận văn · Thạc sĩ · năm 2024 · đề tài tham khảo

Loại tài liệuLuận văn
Bậc họcThạc sĩ
NgànhCông nghệ thông tin
Tác giảNguyễn Mạnh Linh
Người hướng dẫnHoàng Nam Dũng
Cơ sở đào tạoĐại học Quốc gia Hà Nội
Năm2024
NguồnThư viện số Đại học Quốc gia Hà Nội · trang gốc

Tóm tắt

Luận văn này nghiên cứu mô hình toán học cho lớp các bài toán định tuyến xe (Vehicle Routing Problem - VRP). Các thuật toán liên quan được giới thiệu và phân loại xuyên suốt lịch sử hơn 60 năm phát triển của VRP. Các mô hình toán học được trình bày dựa trên ngôn ngữ của lý thuyết đồ thị bao gồm Công thức dòng xe (hai chỉ số, ba chỉ số), Công thức dòng hàng, Phân hoạch tập hợp. Chúng tôi nghiên cứu thuật toán Tìm kiếm lân cận rộng (Large Neighborhood Search - LNS) và đặc biệt là thuật toán Tìm kiếm lân cận rộng thích ứng (Adaptive Large Neighborhood Search - ALNS). Một cách tổng quan, LNS cố gắng bỏ đi một số yêu cầu trong tuyến và thêm lại các yêu cầu đó vào vị trí khác hay tuyến đường khác hoặc thậm chí tạo một tuyến mới nhằm giảm tổng chi phí. ALNS là một phiên bản cải tiến của LNS khi sử dụng không chỉ một thuật toán hủy (bỏ đi yêu cầu) và thêm lại mà sử dụng kết hợp nhiều cách bỏ đi và thêm lại khác nhau. Các thuật toán hủy và thêm lại được lựa chọn một cách thích ứng tùy thuộc vào trạng thái hiện tại của thuật toán tổng thể ALNS. ALNS được chúng tôi áp dụng để giải bài toán Định tuyến xe với ràng buộc khung thời gian (Vehicle Routing Problem with Time Window - VRPTW). Ta có thể điều chỉnh hàm mục tiêu (một chút) hay thay đổi các ràng buộc của VRPTW để thu được các biến thể như Định tuyến xe với ràng buộc tải trọng hay là Lấy vàgiao hàng với ràng buộc thời gian. ALNS được xem như một bộ thư viện khi có thể giải nhiều biến thể của VRP với một chiến thuật chung.
Bản toàn văn lưu tại thư viện Đại học Quốc gia Hà Nội

Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.

Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
  • Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
  • Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
  • Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.

Hướng dẫn chọn đề tài, cấu trúc và số liệu cho ngành này: Luận văn công nghệ thông tin · Hỏi đáp từng chương với người hướng dẫn số: Học Giả Số · Công cụ số: Luận Văn Số.

Đề tài cùng ngành

Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.

Tải ứng dụng AI Học Thuật

Tư vấn học thuật, luận văn, công bố quốc tế với chuyên gia — miễn phí trên iPhone, iPad và Android.

Download on the App Store Tải trên Google Play