Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng" được nghiên cứu nhằm mục tiêu: Xây dựng mô hình và thuật toán giải quyết các bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí; Ứng dụng các thuật toán luồng tối ưu phân luồng giao thông tại thành phố Đà Nẵng.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Luồng đa hàng hóa đa chi phí tuyến tính tối ưu trên mạng hỗn hợp mở rộng ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA HỒ VĂN HÙNG LUỒNG ĐA HÀNG HÓA ĐA CHI PHÍ TUYẾN TÍNH TỐI ƯU TRÊN MẠNG HỖN HỢP MỞ RỘNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số : 9.48.01.01 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT ĐÀ NẴNG – Năm 2022 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA- ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến Phản biện 1: …………………………………………………………… Phản biện 2: …………………………………………………………… Phản biện 3: …………………………………………………………… Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Trường, Trường Đại học Bách khoa Vào hồi … giờ … ngày … tháng … năm 2022 Có thể tìm hiểu luận án tại: - Thư viện quốc gia Việt Nam. - Trung tâm Thông tin - Học liệu & Truyền thông- Đại học Đà Nẵng. MỤC LỤC MỞ ĐẦU ............................................................................................... 1 CHƯƠNG 1. TỔNG QUAN .................................................................... 3 1.1. Đồ thị ............................................................................................. 3 1.2. Mạng, luồng trên mạng .................................................................... 3 1.3. Bài toán luồng cực đại trên mạng ..................................................... 3 1.4. Bài toán quy hoạch tuyến tính .......................................................... 3 1.5. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đơn chi phí ........ 3 1.6. Kết luận chương ....................................................................................................... 3 CHƯƠNG 2. XÂY DỰNG MÔ HÌNH VÀ THUẬT TOÁN GIẢI QUYẾT CÁC BÀI TOÁN LUỒNG TRÊN MẠNG HỖN HỢP MỞ RỘNG ĐA HÀNG HÓA ĐA CHI PHÍ .......................................................................................... 6 2.1. Luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ................. 6 2.2. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ................................................................................ 7 2.2.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí................................................................................................... 7 2.2.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí ................................................................................ 9 2.3. Mô hình và thuật toán bài toán luồng trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ................................................ 12 2.3.1. Bài toán luồng cực đại trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ................................................................... 12 2.3.2. Bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí giới hạn ................................................ 15 2.4. Mô hình và thuật toán bài toán luồng cực đại đồng thời trên mạng hỗn hợp mở rộng đa hàng hóa đa chi phí với chi phí cực tiểu ........................ 18 2.5. Kết luận chương ............................................................................ 20 CHƯƠNG 3. ỨNG DỤNG PHÂN LUỒNG GIAO THÔNG TẠI THÀNH PHỐ ĐÀ NẴNG ........................................................................................... 20 3.1. Sơ đồ một phần mạng lưới giao thông thành phố Đà nẵng ................ 20 3.2. Ứng dụng thuật toán MFMM phân luồng giao thông ......................... 21 3.3. Ứng dụng thuật toán CMF phân luồng giao thông ............................ 21 3.4. Ứng dụng thuật toán LMF phân luồng giao thông ........................... 22 3.5. Ứng dụng thuật toán LCMF phân luồng giao thông .......................... 22 3.6. Ứng dụng thuật toán MCMF phân luồng giao thông ......................... 23 3.7. Kết luận chương ............................................................................ 24 KẾT LUẬN ................................................................................................................... 24 1 MỞ ĐẦU 1. Tính cấp thiết của việc nghiên cứu Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế,…. Hiện nay, việc ứng dụng lý thuyết đồ thị để giải quyết các bài toán trong thực tế được các nhà khoa học quan tâm nghiên cứu. Bài toán luồng đa hàng hóa trên mạng là bài toán tối ưu có nhiều ứng dụng trong các lĩnh vực kinh tế xã hội như giao thông, truyền thông, vận tải …, khác với bài toán đơn hàng, trong bài toán mạng đa hà ...