i
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nghiên cứu
được trình bày trong luận án là hoàn toàn trung thực và chưa từng được ai công bố trong bất kỳ
công trình nào khác.
GIÁO VIÊN HƯỚNG DẪN NGHIÊN CỨU SINH
PGS.TS Đỗ Phan Thuận Nguyễn Ngọc Quang
ii
LỜI CẢM ƠN
Tôi xin trân trọng cảm ơn PGS.TS Nguyễn Đức Nghĩa đã tin tưởng, tâm huyết và tận tình dạy,
định hướng, hướng dẫn tôi trong học tập và quá trình thực hiện nghiên cứu sinh.
Tôi xin trân trọng cảm ơn PGS.TS Đỗ Phan Thuận đã nhiệt tình hướng dẫn tôi học tập, nghiên
cứu và thực hiện luận án này.
Tôi xin trân trọng cảm ơn TS. Nguyễn Khánh Phương đã nhiệt tình tạo điều kiện và hỗ trợ
hướng dẫn tôi trong công tác nghiên cứu.
Tôi xin trân trọng cảm ơn lãnh đạo và các chuyên viên Viện Công nghệ thông tin và Truyền
thông, phòng Đào tạo - trường Đại học Bách khoa Hà Nội đã quan tâm, hỗ trợ tôi trong quá
trình tôi làm nghiên cứu sinh tại Trường.
Tôi xin trân trọng cảm ơn các thầy cô ở Bộ môn Khoa học máy tính Viện Công nghệ thông tin
và Truyền thông trường Đại học Bách khoa Hà Nội đã giúp đỡ tôi trong 7 năm làm nghiên cứu
sinh tại Bộ môn. Các thầy cô đã nhiệt tình hướng dẫn tôi thực hiện các học phần tiến sĩ, các
chuyên đề tiến sĩ, tiểu luận tổng quan và có những góp ý quý báu để tôi hoàn thiện luận án này.
Trân trọng cảm ơn ban lãnh đạo công ty Cổ phần giải pháp ETC và gia đình đã tạo điều kiện
trong thời gian tôi làm nghiên cứu sinh.
Hà Nội, ngày 11 tháng 10 năm 2021
Tác giả luận án
Nguyễn Ngọc Quang
iii
MỤC LỤC
LỜI CAM ĐOAN ........................................................................................................................ i
LỜI CẢM ƠN ............................................................................................................................. ii
MỤC LỤC ................................................................................................................................. iii
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................................ vi
DANH MỤC CÁC BẢNG ....................................................................................................... vii
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................................. viii
MỞ ĐẦU .................................................................................................................................... 1
CHƯƠNG 1. TỔNG QUAN VẤN ĐỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN CỦA HẬU CẦN ĐÔ
THỊ TRONG BÀI TOÁN CHIA SẺ PHƯƠNG TIỆN VÀ BÀI TOÁN GIAO VÀ NHẬN ĐA
LOẠI HÀNG HÓA, ĐA TUYẾN .............................................................................................. 6
1.1. HẬU CẦN ĐÔ THỊ .......................................................................................... 6
1.2. VẤN ĐỀ QUY HOẠCH TRONG HẬU CẦN ĐÔ THỊ .................................. 9
1.3. CÁC MÔ HÌNH HẬU CẦN ĐÔ THỊ ĐIỂN HÌNH ....................................... 10
1.3.1. Mô hình hậu cần đô thị một mức ..................................................................... 11
1.3.2. Mô hình hậu cầu đô thị hai mức ....................................................................... 13
1.4. VẤN ĐỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN TRONG HẬU CẦN ĐÔ THỊ ......... 14
1.4.1. Định tuyến trong bài toán chia sẻ phương tiện ................................................. 15
1.4.2. Định vị và định tuyến trong bài toán giao nhận đa loại hàng hóa, đa tuyến .... 17
1.5. KẾT LUẬN CHƯƠNG .................................................................................. 23
CHƯƠNG 2. VẤN ĐỀ ĐỊNH TUYẾN TRONG BÀI TOÁN CHIA SẺ PHƯƠNG TIỆN .... 24
2.1. PHÁT BIỂU BÀI TOÁN ........................................................................................... 24
2.2. MÔ HÌNH TOÁN HỌC ............................................................................................. 27
2.2.1. Định nghĩa đầu vào........................................................................................... 27
2.2.2. Định nghĩa các biến .......................................................................................... 28
2.2.3. Các hàm mục tiêu ............................................................................................. 29
2.2.4. Các ràng buộc ................................................................................................... 30
2.3. THUẬT TOÁN GIẢI BÀI TOÁN CHIA SẺ PHƯƠNG TIỆN ................................. 31
2.3.1. Kỹ thuật định tuyến trên đồ thị động ................................................................ 31
2.3.1.1. Kỹ thuật phân cấp đỉnh giản lược CH ...................................................... 32
2.3.1.2. Độ phức tạp .............................................................................................. 32
2.3.2. Thuật toán heuristic cho mô hình vận tải trực tiếp ........................................... 33
iv
2.3.3. Thuật toán cho mô hình chia sẻ phương tiện ................................................... 35
2.3.3.1. Cấu trúc chung .......................................................................................... 35
2.3.3.2. Thuật toán tham lam ......................................................................................... 35
2.3.3.3. Thuật toán tìm kiếm địa phương .............................................................. 37
2.4. THỰC NGHIỆM VÀ ĐÁNH GIÁ............................................................................. 38
2.4.1. Dữ liệu thực nghiệm ......................................................................................... 39
2.4.1.1. Xử lý mạng lưới đường giao thông của Tokyo ........................................ 39
2.4.1.2. Chuyển đổi yêu cầu vận tải ...................................................................... 40
2.4.1.3. Xử lý khung tốc độ ................................................................................... 40
2.4.1.4. Định vị kho và bến đỗ của xe taxi ............................................................ 42
2.4.1.5. Bộ dữ liệu thực nghiệm và tham số thực nghiệm ..................................... 42
2.4.2 Kết quả thực nghiệm ......................................................................................... 43
2.5. KẾT LUẬN CHƯƠNG .............................................................................................. 55
CHƯƠNG 3. VẤN ĐỀ ĐỊNH VỊ VÀ ĐỊNH TUYẾN TRONG BÀI TOÁN GIAO VÀ NHẬN
ĐA LOẠI HÀNG HÓA, ĐA TUYẾN ..................................................................................... 56
3.1. TỔNG QUAN BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN
……………………………………………………………………………….56
3.2. BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN VỚI KHUNG
THỜI GIAN VÀ ĐỒNG BỘ ............................................................................................. 57
3.2.1. Phát biểu bài toán ............................................................................................. 57
3.2.2. Mô hình bài toán............................................................................................... 61
3.3. BÀI TOÁN GIAO VÀ NHẬN ĐA LOẠI HÀNG HÓA, ĐA TUYẾN Ở HAI MỨC
VỚI KHUNG THỜI GIAN VÀ ĐỒNG BỘ ..................................................................... 63
3.3.1. Đồng bộ hàng hóa tại điểm trung chuyển......................................................... 68
3.3.2. Mô hình bài toán............................................................................................... 75
3.4. THUẬT TOÁN GIẢI BÀI TOÁN MTT-PDTWS VÀ BÀI TOÁN 2E-MTT-PDTWS
……………………………………………………………………………….79
3.4.1. Cấu trúc chung của thuật toán .......................................................................... 79
3.4.1.1 Thuật toán ALNS giải bài toán MTT-PDTWS ......................................... 80
3.4.1.2 Thuật toán ALNS giải bài toán 2E-MTT-PDTWS ................................... 81
3.4.1.3 Thuật toán heuristic lập lịch vận tải mức 1 cho bài toán 2E-MTT-PDTWS
.................................................................................................................................... 83
3.4.2. Các cấu phần chính của thuật toán ALNS ........................................................ 84
v
3.4.2.1. Khởi tạo lời giải ban đầu .......................................................................... 84
3.4.2.1.1. Khởi tạo lời giải ban đầu cho bài toán MTT-PDTWS ..................... 84
3.4.2.1.2. Khởi tạo lời giải ban đầu cho bài toán 2E-MTT-PDTWS ............... 84
3.4.2.2. Thao tác hủy ............................................................................................. 85
3.4.2.3. Thao tác chỉnh sửa .................................................................................... 87
3.4.2.4. Điều chỉnh trọng số của các thao tác ........................................................ 88
3.4.2.5. Tiêu chí chập nhận lời giải mới và điều kiện dừng .................................. 89
3.5. THỰC NGHIỆM VÀ ĐÁNH GIÁ............................................................................. 90
3.5.1. Dữ liệu thực nghiệm ......................................................................................... 90
3.5.1.1. Dữ liệu thực nghiệm cho bài toán MTT-PDTWS .................................... 90
3.5.1.2. Dữ liệu thực nghiệm cho bài toán 2E-MTT-PDTWS .............................. 92
3.5.2. Thực nghiệm và đánh giá bài toán MTT-PDTWS ........................................... 92
3.5.2.1. Hiệu chỉnh thông số và kết quả thực nghiệm ........................................... 92
3.5.2.2. Đánh giá hiệu năng của thủ tục nâng cao chất lượng lời giải .................. 94
3.5.2.3. Đánh giá kết quả của thuật toán ALNS và thuật toán tìm kiếm Tabu ...... 95
3.5.3. Thực nghiệm và đánh giá bài toán 2E-MTT-PDTWS ..................................... 96
3.6. KẾT LUẬN CHƯƠNG .............................................................................................. 97
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................................................ 99
KẾT LUẬN ....................................................................................................................... 99
HƯỚNG PHÁT TRIỂN .................................................................................................. 101
TÀI LIỆU THAM KHẢO ...................................................................................................... 104
DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN .................................. 110