Phát triển thuật toán giải bài toán tối ưu hóa trong điều hành vận tải chở hành khách và hàng hóa chia sẻ lộ trình

- 1 TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài: Phát triển thuật toán giải bài toán tối ưu hóa trong điều hành vận tải chở hành khách và hàng hóa chia sẻ lộ trình Tác giả luận văn: Thân Thị Lệ Quyên Khóa: 2015B-CNTT Ngƣời hƣớng dẫn: TS.
- Việc lập kế hoạch vận tải tối ƣu có ý nghĩa lớn đối với doanh nghiệp và xã hội.
- Mô hình vận tải kết hợp chở ngƣời và hàng hóa là mô hình mới đã đƣợc đề xuất năm 2014 và vẫn thu hút đƣợc sự quan tâm nghiên cứu giải quyết của các nhà khoa học.
- b) Mục đích nghiên cứu của luận văn, đối tượng, phạm vi nghiên cứu.
- Mục đích nghiên cứu: Mục tiêu của đề tài là tìm hiểu mô hình vận tải kết hợp vận chuyển ngƣời và hàng hóa đƣợc đề xuất đầu tiên vào năm 2014 bởi Li và công sự [1], tìm hiểu các phƣơng pháp thuật toán và thƣ viện liên quan trong việc giải lớp các bài toán lập lộ trình vận tải.
- Thuật toán giải bài toán tĩnh (thông tin về các yêu cầu vận chuyển đã đƣợc biết từ trƣớc) với dữ liệu lớn chƣa đƣợc đề xuất và thử nghiệm.
- Từ đó, đề tài tập trung vào phát triển và thử nghiệm, đánh giá các thuật toán tham lam xây dựng lời giải đối với những bộ dữ liệu lớn.
- Đối tượng: Luận văn nghiên cứu về mô hình bài toán lập lộ trình vận tải kết hợp chở ngƣời và hàng hóa, nghiên cứu các thuật toán để giải bài toán đặt ra, đặc biệt là thuật toán heurisitcs.
- Phạm vi nghiên cứu: Luận văn nghiên cứu bài toàn lập lộ trình vận tải kết hợp chở ngƣời và hàng hóa trong kịch bản tĩnh (các thông tin của bài toán nhƣ yêu cầu vận chuyển đã biết từ trƣớc) và nghiên cứu đề xuất các thuật toán heuristic để xây dựng lời giải với các bộ dữ liệu lớn.
- Phần thử nghiệm đƣợc tiến hành trên các bộ dữ liệu trích xuất từ dữ liệu taxi ở thành phố San Francisco.
- CÀI ĐẶT THUẬT TOÁN GIẢI BÀI TOÁN ĐIỀU HÀNH VẬN TẢI CHỞ NGƢỜI VÀ HÀNG HOÁ CHƢƠNG 3.
- THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT LUẬN d) Phương pháp nghiên cứu.
- e) Kết luận Đề tài đã giải quyết đƣợc các vấn đề sau: Trong luận văn này, chúng tôi đã khảo sát bài toán lập lộ trình vận tải kết hợp chở ngƣời và hàng hóa, cài đặt, thử nghiệm và đánh giá các thuật toán tham lam khác nhau giải bài toán đặt ra.
- Tìm hiểu về bài toán tối ƣu hóa tổ hợp và các hƣớng tiếp cận giải bài toán tối ƣu tổ hợp.
- Tìm hiểu bài toán lập lộ trình vận tải nói chung, bài toán lập lộ trình vận tải kết hợp vận chuyển ngƣời và hàng hóa nói riêng và các nghiên cứu liên quan.
- Tìm hiểu thƣ viện CBLSVR dùng để mô hình hóa và giải các bài toán điều hành vận tải bằng phƣơng pháp tìm kiếm cục bộ dựa trên ràng buộc.
- Đề xuất 7 thuật toán tham lam xây dựng lời giải cho bài toán đặt ra.
- Cài đặt 7 thuật toán đề xuất và thử nghiệm trên các bộ dữ liệu đƣợc trích xuất từ dữ liệu taxi ở thành phố SanFrancisco.
- Kết quả thử nghiệm cho thấy thuật toán 1 cho kết quả tốt nhất do không gian tìm và duyệt lớn.
- Trong khi đó thuật toán số 7 có kết quả tìm kiếm gần tƣơng đƣơng so với thuật toán 1 nhƣng thời gian lớn hơn so với thuật toán tham lam 1.
- Đối với các bộ dữ liệu kích thƣớc lớn thì thuật toán 7 tỏ ra hiệu quả vì đã xây dựng đƣợc lời giải chất lƣợng tốt trong thời gian ngắn.

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt