Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Nghiên cứu và phát triển các thuật toán giải quyết các bài toán tối ưu trong giao thông vận tải người và hàng hóa

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

15
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tóm tắt Luận án Tiến sĩ Khoa học máy tính "Nghiên cứu và phát triển các thuật toán giải quyết các bài toán tối ưu trong giao thông vận tải người và hàng hóa" đề xuất một thuật toán thích nghi và dựa trên dữ liệu để học quy trình Poison không thuần nhất nhằm dự đoán các yêu cầu vận chuyển trong tương lai giúp giảm thiểu khoảng cách không tải của phương tiện.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Khoa học máy tính: Nghiên cứu và phát triển các thuật toán giải quyết các bài toán tối ưu trong giao thông vận tải người và hàng hóa

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN VĂN SƠN NGHIÊN CỨU VÀ PHÁT TRIỂN CÁC THUẬT TOÁN GIẢI QUYẾT CÁC BÀI TOÁN TỐI ƯU TRONG GIAO THÔNG VẬN TẢI NGƯỜI VÀ HÀNG HÓA Ngành: Khoa học máy tính Mã số: 9480101 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Hà Nội - 2023
Công trình được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: 1. TS. Phạm Quang Dũng 2. PGS. TS. Nguyễn Xuân Hoài Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Trường họp tại Trường Đại học Bách khoa Hà Nội Vào hồi …….. giờ, ngày ….. tháng ….. năm ……… Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam
GIỚI THIỆU Ngành giao thông vận tải đóng vai trò quan trọng trong phát triển kinh tế và kết nối giữa các vùng. Điều này càng đúng hơn trong nền kinh tế toàn cầu, bao gồm sự tăng cường hợp tác kinh tế liên quan đến sự di chuyển của người và hàng hóa. Bài toán tìm lộ trình tối ưu cho các xe phục vụ các yêu cầu vận chuyển được gọi là Bài toán Định tuyến Xe (VRP). Đây là một bài toán thuộc lớp NP-khó. Hàng ngàn bài báo trên thế giới đã được dành cho vấn đề này. Nhiều nhà nghiên cứu đã đề xuất nhiều mô hình và thuật toán cho VRP và các biến thể của nó. Việc nghiên cứu và mở rộng bài toán với sự kết hợp của các yếu tố thực tế làm tăng khả năng ứng dụng của bài toán VRP vẫn là một vấn đề mang tính thời sự. Vì vậy, luận án này nhằm nghiên cứu và đề xuất những biến thể mới của VRPs, xem xét một số yếu tố trong thế giới thực để mở rộng VRPs một cách linh hoạt và thực tế hơn. Do tầm quan trọng thực tế của VRP, mục tiêu chính của luận án này là mở rộng các bài toán VRP hiện có một cách linh hoạt và thực tế hơn. Điều quan trọng là các biến thể mới được xây dựng và các thuật toán phù hợp được phát triển để giải quyết chúng một cách hiệu quả nhất có thể. Theo khảo sát từ các công trình khoa học cũng như hoạt động vận hành thực tế của các công ty vận tải, hoạt động định tuyến thường được phân thành hai kịch bản: tĩnh và động. Do đó, luận án tập trung vào hai trường hợp điển hình này của các bài toán VRP. Đối với bài toán VRP tĩnh, các tác giả trong Vidal et al. 2020 tuyên bố rằng một trong những mục tiêu quan trọng nhất của bài toán định tuyến là cân bằng phân bổ khối lượng công việc để đảm bảo các kế hoạch được chấp nhận, duy trì sự hài lòng và tinh thần của nhân viên, giảm thời gian làm thêm giờ và để giảm tắc nghẽn trong sử dụng tài nguyên. Do sức chứa hạn chế, quy mô đội xe cố định và hạn chế về thời gian, các xe phải vận chuyển các sản phẩm từ nhiều trung tâm phân phối đến khách hàng và thực hiện nhiều chuyến đi. Tuy nhiên, một số chuyến đi của các phương tiện được lập kế hoạch chở quá ít hàng hóa trong các thực tế do ràng buộc thời gian chặt. Vì vậy, luận án này đề xuất một biến thể mới của bài toán VRP tĩnh trong đó xét đến hầu hết các ràng buộc đã được nghiên cứu kỹ lưỡng và bao gồm một ràng buộc mới về giới hạn dưới của tải trọng chưa từng được nghiên cứu trong các công trình. Luận án này mô hình hóa bài toán xem xét dưới dạng quy hoạch nguyên tuyến tính hỗn hợp (MILP), phân tích các thách thức của các ràng buộc mới về giới hạn dưới tải trọng và đề xuất một khung tìm kiếm lân cận lớn thích ứng (ALNS) để giải quyết nó. Đối với bài toán VRP động, một mô hình vận chuyển người mới 1
được nghiên cứu, đây là phần mở rộng của bài toán chia sẻ chuyến đi do Li et al. 2014 đề xuất. Trong mô hình đó, người và hàng hóa có thể chia sẻ chuyến đi trên cùng mạng lưới taxi và thông tin về các yêu cầu trong tương lai được dự đoán. Một mô hình toán học mới và một thuật toán học dựa trên dữ liệu được đề xuất. Đồng thời, một thuật toán điều phối lịch trình taxi khai thác các thông tin dự đoán cũng được phát triển trong luận án này. Động lực nghiên cứu Việc tối ưu hóa giao thông vận tải đã trở thành một vấn đề lớn trong những năm gần đây. Bài toán định tuyến là một thách thức mới đối với ngành giao thông vận tải: nâng cao năng suất và giảm chi phí bằng cách tăng số lượng khách hàng được phục vụ, giảm thời gian và chi phí vận chuyển để đạt được kế hoạch nguồn nhân lực tốt và hoạt động hiệu quả. Nghiên cứu về VRP không chỉ mang lại lợi ích cho các công ty vận tải mà còn cho cả xã hội. Điều này thúc đẩy chúng tôi lấp đầy khoảng trống trong tài liệu về một số bài toán VRP bằng cách kết hợp các yếu tố trong thế giới thực để mở rộng các bài toán này một cách linh hoạt và thực tế hơn. Phương pháp Phương pháp luận của luận văn này như sau: • Nghiên cứu lý thuyết các biến thể của bài toán VRP. • Phân tích các công trình khoa học liên quan đến các bài toán được xem xét. • Thiết kế các mô hình thực tế và hữu ích cho bài toán VRP đang xem xét. • Đề xuất các thuật toán metaheuristic hiệu quả để giải quyết các mô hình VRP nghiên cứu. Phạm vi nghiên cứu Các bài toán VRP là các bài toán rất phức tạp bao gồm nhiều bài toán con và biến thể. Do đó, phạm vi của luận án này là nghiên cứu hai bài toán định tuyến giao thông thực tế điển hình cho hai loại VRP, tĩnh và động. Trong lớp bài toán VRP tĩnh, bài toán phân phối hàng hóa được nghiên cứu. Bài toán xem xét sự kết hợp các ràng buộc thực tế để giải quyết các vấn đề thực tế tại một trong những công ty sữa lớn nhất Việt Nam. Trong lớp bài toán VRP động, bài toán lập lịch trình taxi động với thông tin dự báo được nghiên cứu. Bài toán này được mở rộng từ bài toán VRP chia sẻ chuyến đi mới do Li et al. 2014 đề xuất, trong đó người và hàng hóa được phục vụ trên cùng một mạng lưới taxi. 2
Các bài toán được xem xét đều là các bài toán N P -khó. Hơn nữa, sự kết hợp của các ràng buộc thực tế làm cho vấn đề trở nên thách thức hơn. Vì vậy, luận án chủ yếu tập trung vào các thuật toán heuristic/metaheuristic để giải quyết các bài toán đề xuất. Đóng góp chính Luận án này có ba đóng góp chính bao gồm: • Với mục tiêu phát triển các mô hình vận chuyển hàng hóa để giải quyết các vấn đề thực tế của doanh nghiệp, luận án đề xuất một bài toán vận chuyển sản phẩm mới có tính đến hầu hết các ràng buộc đã được nghiên cứu kỹ lưỡng, đặc biệt là với một ràng buộc mới về giới hạn dưới tải trọng chưa được nghiên cứu trong các công trình khoa học. Luận án xây dựng bài toán dưới dạng mô hình MILP và đề xuất một số thuật toán metaheuristic hiệu quả để giải bài toán đó. Các thí nghiệm được thực hiện trong các tình huống khác nhau để kiểm tra hiệu quả của các thuật toán. • Đối với mô hình vận tải hành khách, một biến thể mới của mô hình định tuyến vận tải taxi chia sẻ trong kịch bản động được phát triển trong luận án này. Trong mô hình này, người và hàng hóa được phục vụ trong cùng một mạng lưới taxi, trong đó hệ thống định tuyến cần đề xuất tuyến đường tốt nhất cho tài xế taxi không tải để cơ hội nhận được nhu cầu vận chuyển mới cao khi taxi rảnh rỗi. Chúng tôi đề xuất một thuật toán hiệu quả để định tuyến các taxi và khai thác các thông tin dự đoán. • Luận án này cũng đã đề xuất một thuật toán thích nghi và dựa trên dữ liệu để học quy trình Poison không thuần nhất nhằm dự đoán các yêu cầu vận chuyển trong tương lai giúp giảm thiểu khoảng cách không tải của phương tiện. Kết quả thực nghiệm chứng minh rằng việc áp dụng cải tiến hướng di chuyển trong định tuyến dựa trên dự đoán nhu cầu dẫn đến di chuyển linh hoạt và hiệu quả di chuyển tổng thể. Nghiên cứu này đã liên kết các vấn đề giao thông với học máy, vốn được kỳ vọng sẽ giải quyết các vấn đề giao thông truyền thống. Cấu trúc luận án Luận án được bố cục như sau: • Chương 1 cung cấp một số kiến thức nền tảng về bài toán VRP và các thuật toán giải quyết các bài toán VRP. • Chương 2 trình bày bài toán phân phối sản phẩm, mô hình, các thách thức và thuật toán ALNS được điều chỉnh để giải quyết bài toán. Trong thuật 3
toán đề xuất, giải pháp ban đầu được tạo và sau đó các chiến lược tìm kiếm lân cận lớn thích nghi được áp dụng để cải thiện chất lượng của giải pháp . Hiệu suất của thuật toán đề xuất được so sánh với hiệu suất của các phương pháp phỏng đoán khác bằng cách tiến hành các thử nghiệm số mở rộng để đánh giá khả năng áp dụng của thuật toán được đề xuất trong các ứng dụng trong thế giới thực. • Chương 3 nghiên cứu bài toán định tuyến taxi chia sẻ hành khách và bưu kiện trong kịch bản động. Một phương pháp học tập dựa trên dữ liệu được phát triển để dự đoán các yêu cầu vận chuyển mới và một thuật toán hiệu quả được đề xuất để định tuyến taxi và khai thác các yêu cầu được dự đoán trong tương lai. • Chương Kết luận tổng kết các kết quả nghiên cứu và định hướng nghiên cứu trong tương lai. 4
Chương 1 KIẾN THỨC CƠ SỞ 1.1 Bài toán tối ưu hóa Các bài toán tối ưu hóa (OP) là các bài toán trong đó cần xác định một tập hợp các biến quyết định chưa biết {x}n sao cho hàm mục tiêu f được tối thiểu 1 hóa / cực đại hóa và một số ràng buộc được thỏa mãn (Boyd et al. 2004) (từ bây giờ chúng ta sẽ chỉ xem xét mục tiêu tối thiểu hóa). Định nghĩa 1. (Boyd et al. 2004) Dạng chuẩn của một bài toán tối ưu hóa là: Tối thiểu hóa f (x) thỏa mãn gj (x) = 0, j = 1, . . . , m∗ , gj (x) ≤ 0, j = m∗ + 1, . . . , m, xi ∈ Di , ∀i = 1, . . . , n trong đó x = {x1 , x2 , . . . , xn } là véc tơ biến quyết định, m là tổng số ràng buộc, m∗ là tổng số ràng buộc dạng phương trình và Di là miền xác định của xi . 1.2 Vehicle Routing Problem and các bài toán mở rộng 1.2.1 Bài toán định tuyến xe với ràng buộc tải trọng Bài toán VRP tiêu chuẩn là bài toán định tuyến xe có ràng buộc tải trọng (CVRP), trong đó một đội xe cố định đồng nhất được lập lộ trình để phục vụ nhu cầu của một tập khách hàng vận chuyển hàng hóa từ một kho cụ thể với chi phí vận chuyển nhỏ nhất. 1.2.2 Bài toán định tuyến xe giao và nhận với ràng buộc thời gian Một biến thể quan trọng của VRP là bài toán định tuyến xe nhận và giao hàng với khung thời gian (PDVRPTW). Trong PDVRPTW, bài toán yêu cầu tìm một hoặc nhiều tuyến với chi phí tối thiểu để phục vụ một số yêu cầu của khách hàng, trong đó mỗi yêu cầu được xác định bởi điểm nhận hàng, điểm giao hàng tương ứng và nhu cầu (hàng hóa hoặc hành khách) được vận chuyển giữa các vị trí này trong khoảng thời gian xác định trước. 5
Hình 1.2: Rich vehicle routing problem. 1.2.3 Bài toán định tuyến taxi chia sẻ lộ trình Hầu hết các mô hình chia sẻ chuyến đi đều dựa trên bài toán định tuyến xe phục vụ yêu cầu dựa trên cuộc gọi (DARP) nổi tiếng. DARP bao gồm việc thiết kế các lộ trình cho đội xe chở một số người từ điểm đón tới điểm trả theo yêu cầu. Gần đây, Li et al. 2014 đã đề xuất mô tả về bài toán lập lộ trình taxi chia sẻ (SARP) động trong đó người và hàng hóa được phục vụ bởi cùng một mạng lưới taxi. Các tác giả trong Li et al. 2014 đã trình bày các công thức MILP cho SARP với một số ràng buộc thực tế. 1.2.4 Bài toán định tuyến xe phong phú Xu hướng mới chủ yếu tập trung vào việc áp dụng VRP và các mở rộng của chúng cho các vấn đề trong cuộc sống thực bằng cách kết hợp nhiều ràng buộc thực tế. Bài toán đó được gọi là bài toán định tuyến xe phong phú (RVRP). Hình 1.2 trình bày một số biến thể và mở rộng của bài toán VRPs. 1.3 Phương pháp luận cho bài toán VRP Nhiều phương pháp khác nhau để giải quyết VRP đã được nghiên cứu. Các phương pháp VRP hiện tại có thể được chia thành hai loại: phương pháp giải chính xác và phương pháp không đầy đủ. 6
Chương 2 MÔ HÌNH HÓA VÀ GIẢI QUYẾT MỘT BIẾN THỂ MỚI BÀI TOÁN ĐỊNH TUYẾN TĨNH 2.1 Giới thiệu Trong các kịch bản định tuyến tĩnh, một công ty nhận được lượng lớn nhu cầu từ các khách hàng có vị trí khác nhau mỗi ngày. Họ thường định tuyến các phương tiện để phục vụ những khách hàng này vào một thời điểm cố định (ví dụ: 8 giờ sáng). Công ty sở hữu một đội xe cố định (xe tự sở hữu) và có thể thuê một số xe từ một số công ty logistics bên thứ ba (xe thuê ngoài) khi cần. Do sức chứa hạn chế, quy mô đội xe cố định và hạn chế về khung thời gian, các phương tiện phải vận chuyển các hàng hóa từ nhiều trung tâm phân phối đến khách hàng và thực hiện nhiều chuyến đi. Tổng trọng lượng sản phẩm vận chuyển trong mỗi chuyến phải nằm trong khoảng cho phép tùy thuộc vào tải trọng của phương tiện vận hành. Sự hiện diện của các ràng buộc giới hạn dưới tải trọng làm cho vấn đề trở nên khó khăn hơn. Những yêu cầu thực tế này đến từ một trong những công ty phân phối sữa lớn nhất Việt Nam. Với trung bình trên 1000 điểm khách hàng mỗi lần lập kế hoạch, công ty phải mất ít nhất một ngày làm việc để lên kế hoạch lộ trình. Theo hiểu biết tốt nhất của chúng tôi, ràng buộc giới hạn dưới của tải trọng chưa được nghiên cứu trong các công trình khoa học cho lớp bài toán VRP tĩnh. Bên cạnh đó, sự kết hợp của các ràng buộc thực tế làm cho bài toán trở nên phức tạp hơn rất nhiều. Các đóng góp chính của chương này là: • Chương này đề xuất một mô hình bài toán VRP tĩnh mới có tính ứng dụng cao, với sự kết hợp của các thuộc tính sau: – Có ba loại điểm không gian: các bãi đỗ xe, các trung tâm phân phối và các điểm khách hàng. – Mỗi xe có thể thực hiện nhiều chuyến và lấy hàng tại các trung tâm phân phối khác nhau trong mỗi chuyến. – Tổng trọng lượng hàng trong mỗi chuyến trên xe phải lớn hơn hoặc bằng trọng lượng tối thiểu quy định. – Thời gian phục vụ tại mỗi điểm phụ thuộc vào trọng lượng hàng được tải lên/dỡ xuống. 7
– Mỗi xe có một tập các khách hàng không được phép phục vụ và một tập các khách hàng được chỉ định phục vụ. • Bài toán nghiên cứu được mô hình hóa dưới dạng mô hình quy hoạch nguyên tuyến tính hỗn hợp (MILP). Một số thử nghiệm được thực hiện trên các kịch bản thực quy mô nhỏ, các phiên bản tiêu chuẩn và các kịch bản tự sinh được giải bằng trình tối ưu hóa GUROBI nhằm xác thực mô hình. • Chương này cũng phân tích những thách thức của ràng buộc cận dưới tải trọng, coi ràng buộc này là một ràng buộc mềm và đưa nó (với một hệ số xác định) vào hàm mục tiêu để so sánh. Luận án đã xuất ba thuật toán xây dựng thích nghi hiệu quả để giải quyết vấn đề này. 2.2 Mô tả bài toán và mô hình hóa 2.2.1 Mô tả bài toán Một hệ thống lập lịch xe nhận được một số lượng lớn yêu cầu vận chuyển các sản phẩm sữa từ trung tâm phân phối đến khách hàng trong một thời điểm cố định. Mỗi yêu cầu bao gồm thông tin về vị trí của khách hàng, khoảng thời gian cần phục vụ và trọng lượng cần vận chuyển. Hệ thống thực hiện lập lịch trình và định tuyến một đội xe không đồng nhất thực hiện nhiều chuyến đi: một xe khởi hành từ bãi đỗ xe, thực hiện một chuỗi các chuyến đi và quay trở lại khu vực đỗ xe trong một ngày làm việc. Bài toán này nhằm đạt được số lượng khách hàng được phục vụ lớn nhất, số lượng xe cần thiết tối thiểu và lộ trình xe chạy tốt nhất để tổng quãng đường di chuyển là nhỏ nhất. Một ví dụ về hành trình của các xe được minh họa trong Hình 1.2 trong đó hành trình của một xe được định tuyến theo trình tự các điểm 0, 1, 2, 3, 4, 5, 6, 7, 8, 0. Xe này thực hiện 2 chuyến, hàng hóa trên mỗi chuyến được xếp tại các trung tâm phân phối khác nhau. Trong khi xe khác phải chạy theo hành trình 9, 10, 11, 12, 13, 10, 14, 15, 16, 9. Hàng hóa giao cho khách hàng trên các chuyến khác nhau được xếp tại cùng một trung tâm phân phối trong hành trình này. Giới hạn sức chứa là [70, 110] cho mỗi xe. 8
Hình 1.2: Một ví dụ về hành trình của các xe trong bài toán MTDLC-VR. 2.2.2 Kí hiệu và định nghĩa 2.2.3 Mô hình toán học Chúng tôi định nghĩa số khách hàng không được phục vụ bởi gr = η − i∈C yi , số xe cần thiết bởi gv = k∈K fk z k,1 , và tổng quãng đường di chuyển bởi gc = q(k) k,q k∈K q=1 (i,j)∈E di,j xi,j . Bài toán MTDLC-VR được mô tả dưới dạng toán học như sau: Tối thiểu hóa F = f gr + gv + gc (2.1) subject to • Ràng buộc về luồng của hành trình q(k) q(k) xk,q i,j = xk,q , ∀k ∈ K, ∀i ∈ V j,i (2.2) j∈δ + (i) q=1 j∈δ − (i) q=1 • Ràng buộc về luồng trên mỗi chuyến xk,q = i,j xk,q , ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀i ∈ C j,i (2.3) j∈δ + (i) j∈δ − (i) • Nếu xe k quay trở lại trung tâm phân phối dp thì nó phải phục vụ chuyến tiếp theo xk,q−1 = j,dp xk,q , ∀k ∈ K, ∀q = 2, 3, . . . , q(k), ∀dp ∈ D dp,j (2.4) j∈δ − (dp) j∈δ + (dp) • Thời điểm khởi hành của các xe bằng thời điểm sớm nhất bắt đầu phục vụ của bãi đỗ. sk,1 = e(p(k)), ∀k ∈ K p(k) (2.5) 9
Bảng 2.1: Các tập hợp và tham số Kí hiệu Định nghĩa PK Tập các bãi đỗ xe. Với mỗi bãi đỗ pk ∈ PK: [e(pk), l(pk)]: khung thời gian làm việc của bãi pk. P Tập các sản phẩm. Mỗi sản phẩm p ∈ P : w(p): trọng lượng của một đơn vị sản phẩm p. D Tập các trung tâm phân phối. Mỗi trung tâm dp ∈ D: [e(dp), l(dp)]: khung thời gian của trung tâm phân phối dp. twait (dp): thời gian đợi để có thể truy cập trung tâm phân phối dp. tunit (dp): khoảng thời gian cần thiết để tải một đơn vị sản phẩm tại trung tâm dp. C Tập các khách hàng. Số lượng khách hàng được kí hiệu bởi η. Với mỗi khách hàng c ∈ C: [e(c), l(c)]: khung thời gian của mỗi khách hàng c. twait (c): thời gian đợi để truy cập điểm khách hàng c. tunit (c): thời gian cần thiết để dỡ tải một đơn vị sản phẩm tại điểm khách hàng c. d(c, p): trọng lượng yêu cầu của sản phẩm p cho khách hàng c. V Tập tất cả các điểm. V = PK ∪ D ∪ C K Danh sách các xe. K = {0, 1, 2, . . . , κ − 1}, với mỗi xe k ∈ K: p(k) ∈ P : bãi đỗ của xe k. fk : hệ số ưu tiên sử dụng xe k. c(k): giới hạn dưới của tải trọng xe k. c(k): giới hạn trên của tải trọng xe k. q(k): số chuyến tối đa trong ngày của xe k. E Tập các cạnh (i, j), ∀(i, j) ∈ (PK × D) ∪ (D × C) ∪ (C × C) ∪ (C × D) ∪ (C × PK) và i ̸= j δ + (i) = {j | (i, j) ∈ E} δ − (i) = {j | (j, i) ∈ E} dmw (i, p) Tham số đại diện cho nhu cầu trọng lượng của sản phẩm p tại điểm i, ∀i ∈ V, ∀p ∈ P . dmw (i, p) = 0, ∀i ∈ PK ∪ D, ∀p ∈ P . dmw (i, p) = dm(i, p) ∗ w(p), ∀i ∈ C, ∀p ∈ P . dr(i) Tham số đại diện cho khoảng thời gian phục vụ tại điểm i, ∀i ∈ V . dr(pk) = 0, ∀pk ∈ PK. dr(dp) = twait (dp), ∀dp ∈ D. dr(i) = twait (i) + p∈P dmw (i, p)tunit (i), ∀i ∈ C. rc(k, c) Giới hạn truy cập của xe k tới khách hàng c, ∀c ∈ C, ∀k ∈ K. rc(k, c) = 1: xe k có thể truy cập khách hàng c rc(k, c) = 0: ngược lại. rp(k, p) rp(k, p) = 1: xe k được cho phép chở sản phẩm p, ∀k ∈ K, ∀p ∈ P . rp(k, p) = 0: ngược lại. vc(k, c) vc(k, c) bằng 1 nếu khách hàng c là một khách hàng được chỉ định trước của k, bằng 0 nếu ngược lại, ∀k ∈ K, ∀c ∈ C. ti,j thời gian di chuyển từ điểm i tới điểm j, ∀(i, j) ∈ E. di,j quãng đường di chuyển từ điểm i tới điểm j, ∀(i, j) ∈ E. f Hệ số phạt đối với một yêu cầu của khách hàng không được phục vụ. M M là một hằng số lớn. 10
Bảng 2.2: Biến mô hình Kí hiệu Định nghĩa xk,q i,j Một biến nhị phân bằng 1 nếu xe k di chuyển trên cạnh (i, j) trong chuyến thứ q; bằng 0 nếu ngược lại, ∀k ∈ K, ∀(i, j) ∈ E, ∀q = 1, 2, . . . , q(k). k,q wp Tổng trọng lượng của sản phẩm p vận chuyển bởi xe k trong chuyến thứ q, ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀p ∈ P . yi Một biến nhị phân bằng 1 nếu khách hàng i được phục vụ; bằng 0 nếu ngược lại, ∀i ∈ C. z k,q Một biến nhị phân bằng 1 nếu xe k thực hiện chuyến thứ q; bằng 0 nếu ngược lại, ∀k ∈ K, ∀q = 1, 2, . . . , q(k). sk,q i Một biến để xác định thời gian bắt đầu phục vụ tại điểm i của xe k trong chuyến thứ q, ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀i ∈ C. • Ràng buộc thời điểm bắt đầu phục vụ tại điểm khách hàng ngay sau điểm trung tâm phân phối trên hành trình của xe sk,q + ti,j + dr(i) + M (xk,q − 1) + i i,j wp tunit (i) ≤ sk,q , k,q j (2.6) p∈P ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀(i, j) ∈ D × C • Ràng buộc thời điểm bắt đầu phục vụ tại các điểm không phải trung tâm phân phối. sk,q + ti,j + dr(i) + M (xk,q − 1) ≤ sk,q , i i,j j (2.7) ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀(i, j) ∈ (PK × D) ∪ (C × C) ∪ (C × PK), i ̸= j • Ràng buộc thời điểm bắt đầu phục vụ tại điểm cuối cùng của mỗi chuyển sk,q−1 + ti,j + dr(i) + M (z k,q − 1) + M (xk,q−1 − 1) ≤ sk,q , i i,j j (2.8) ∀k ∈ K, ∀q = 2, 3, . . . , q(k), ∀(i, j) ∈ C × D • Ràng buộc khung thời gian phục vụ tại mỗi điểm sk,q + M ( i xk,q − 1) ≤ l(i), i,j (2.9) j∈δ + (i) sk,q + M (1 − i xk,q ) ≥ e(i), i,j (2.10) j∈δ + (i) ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀i ∈ V • Ràng buộc xác định tổng trọng lượng sản phẩm được tải tại trung tâm phân phối k,q wp = dmw (i, p)xk,q , ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀p ∈ P i,j (2.11) (i,j)∈E 11
• Ràng buộc đối với tải trọng của xe wp + M (z k,q − 1) ≤ c(k), k,q (2.12) p∈P wp + M (1 − z k,q ) ≥ c(k), k,q (2.13) p∈P ∀k ∈ K, ∀q = 1, 2, . . . , q(k) • Mỗi khách hàng chỉ được phục vụ 1 lần bởi 1 xe q(k) xk,q ≤ 1, ∀j ∈ C i,j (2.14) k∈K q=1 i∈δ − (j) • Mỗi trung tâm phân phối được thăm một lần trong mỗi chuyến xk,q = z k,q , ∀k ∈ K, ∀q = 1, 2, . . . , q(k) dp,j (2.15) dp∈D j∈C • Mỗi xe khởi hành tại bãi đỗ nhiều nhất một lần. xk,1 p(k),dp = z k,1 , ∀k ∈ K (2.16) dp∈D • Mỗi xe phải quay trở lại bãi đỗ nhiều nhất một lần q(k) xk,q = z k,1 , ∀k ∈ K j,p(k) (2.17) q=1 j∈C • Ràng buộc quan hệ giữa các biến quyết định z k,q ≤ xk,q , ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀(i, j) ∈ E i,j (2.18) (i,j) xk,q ≤ z k,q , ∀k ∈ K, ∀q = 1, 2, . . . , q(k), ∀(i, j) ∈ E i,j (2.19) q(k) xk,q = yj , ∀j ∈ C i,j (2.20) k∈K q=1 i∈δ − (j) • Ràng buộc thứ tự các chuyến z k,q+1 ≤ z k,q , ∀k ∈ K, ∀q = 1, 2, . . . , q(k) − 1 (2.21) • Ràng buộc giới hạn có thể truy cập khách hàng của mỗi xe q(k) xk,q ≤ M.rc(k, i), ∀k ∈ K, ∀i ∈ V j,i (2.22) q=1 j∈δ − (i) 12
• Ràng buộc giới hạn sản phẩm có thể chở của mỗi xe q(k) k,q wp ≤ M.rp(k, p), ∀k ∈ K, ∀p ∈ P (2.23) q=1 • Ràng buộc phải phục vụ các khách hàng được xác định trước của mỗi xe q(k) vc(k, i) ≤ xk,q , ∀k ∈ K, ∀i ∈ C j,i (2.24) q=1 j∈δ − (i) 2.3 Phương pháp 2.3.1 Các kí hiệu dùng cho thuật toán metaheuristic Do độ phức tạp tính toán rất lớn, trình tối ưu hóa GUROBI chỉ có thể giải quyết các kịch bản nhỏ của bài toán MTDLC-VR. Vì vậy, một trong những đóng góp của chúng tôi là đề xuất các thuật toán metaheuristic để xử lý các kịch bản lớn của bài toán. Để đơn giản hóa việc trình bày các thuật toán được đề xuất, chúng tôi đưa ra một số ký hiệu được tóm tắt như sau. 2.3.2 Phân tích thách thức của ràng buộc mới về tải trọng tối thiểu trong bài toán MTDLC-VR 2.3.2.1 Thách thức đối với các thuật toán xây dựng Trong phần này, chúng tôi phân tích thách thức gặp phải khi xây dựng giải pháp ban đầu trong trường hợp giới hạn dưới tải trọng được coi là một ràng buộc cứng. 2.3.3 Các thuật toán xây dựng điều chỉnh với thủ tục chia chuyến Trong phần này, dựa trên các thuật toán xây dựng được sử dụng rộng rãi SA, SW và GIA, chúng tôi đề xuất ba thuật toán xây dựng phù hợp được sử dụng trong giai đoạn khởi tạo lời giải ban đầu. Dựa trên ý tưởng về phương pháp RF- CS, các thuật toán SA, SW và GIA được tinh chỉnh cho bài toán MTDLC-VR bằng cách tạm thời nới lỏng ràng buộc (2.13). 2.3.4 Một thuật toán ALNS được cải tiến với thủ tục chia chuyến Phần này đề xuất thuật toán ALNS được cải tiến (A-ALNS) để xử lý các kịch bản lớn của bài toán MTDLC-VR. Thuật toán A-ALNS sử dụng tám toán tử loại bỏ và tám toán tử chèn. Chúng tôi đề xuất sáu toán tử (R2, R5, I1, I2, I5 và I6) 13
và chọn một số toán tử phù hợp trong các công trình khoa học theo kinh nghiệm của chúng tôi. Các toán tử thích hợp được lấy từ Ropke et al. 2006 và được sửa đổi một chút để phù hợp với bài toán này. Toán tử chèn sử dụng quy trình phân tách để chia một chuyến tham quan khổng lồ thành các chuyến đi khả thi và đảm bảo các ràng buộc (2.12)-(2.13). Do sự phức tạp của bài toán, có thể không tìm thấy cải tiến nào sau một số lần lặp lại (cụ thể là số maxStable). Để tránh bị kẹt trong tối ưu cục bộ, một trong những ý tưởng chính của thuật toán này là tăng số lượng khách hàng bị loại bỏ. Điều đó có nghĩa là thuật toán đề xuất cố gắng vượt qua các điểm cao nguyên bằng cách thực hiện một bước nhảy lớn. Bên cạnh đó, có thể thấy nguyên lý bánh xe quay hoạt động tốt với số lần lặp lớn. Tuy nhiên, đối với các phiên bản lớn, thời gian xử lý của mỗi lần lặp sẽ lâu hơn do không gian tìm kiếm lớn. Vì vậy, chúng tôi đề xuất phương pháp cập nhật trọng số thích ứng để nhanh chóng tìm toán tử tốt, trong đó trọng số của toán tử được cập nhật sau mỗi lần lặp và liên quan đến sự thay đổi giá trị của hàm mục tiêu. 14
1 Một giải pháp ban đầu Sinit được tạo bởi một thuật toán xây dựng cải tiến; 2 Khởi tạo xác suất cho từng toán tử; 3 Sbest ← Scur ← Sinit ; 4 Một số ngẫu nhiên σ ∈ [θη, γη] được sinh; 5 it ← 0; 6 while chưa gặp điều kiện dừng do 7 Một toán tử xóa OR và một toán tử chèn OI được chọn ngẫu nhiên theo xác suất; 8 ⟨R∗ , Snew ⟩ ← RmOpApplying(σ, OR , Scur ); // xem mục 2.3.4.2 9 R ∗ ← R ∗ ∪ R∗ ; 10 ⟨R∗ , Snew ⟩ ← InsOpApplying(R∗ , OI , Snew ); // xem mục 2.3.4.3 11 if F (Snew ) < F (Scur ) then 12 if F (Snew ) < F (Sbest ) then 13 UpdateOperatorScores(OR , OI , Sbest , Snew , π1 ); 14 Sbest ← Snew ; 15 Generate a random number σ ∈ [θη, γη]; 16 it ← 0; 17 end 18 else 19 UpdateOperatorScores(OR , OI , Scur , Snew , π2 ); 20 Scur ← Snew ; 21 end 22 end 23 else 24 R ∗ ← R ∗ \ R∗ ; 25 UpdateOperatorScores(OR , OI , Snew , Scur , π3 ); 26 if it + + > maxStable then 27 Một số ngẫu nhiên σ ∗ ∈ [0, θη] được sinh; 28 σ ← σ + σ∗; 29 end 30 end 31 Cập nhật xác xuất (??); // xem mục 2.3.4.1 32 end Algorithm 1: ALNS(θ, γ, π1 , π2 , π3 ) 15
2.3.4.1 Phương pháp chọn các toán tử 2.3.4.2 Các toán tử xóa 2.3.4.3 Các toán tử chèn 2.4 Các thí nghiệm số 2.4.1 Kịch bản và cài đặt Theo những gì chúng tôi biết, bài toán được mô tả trong Chương này xem xét một số ràng buộc trong đời thực chưa từng được nghiên cứu trong các công trình khoa học. Do đó, không có nghiên cứu trước đây và bộ dữ liệu tiêu chuẩn được tìm thấy để so sánh. Bên cạnh đó, một lý do chính là không dễ để có được các trường hợp tiêu chuẩn phù hợp. Vì vậy, để đánh giá hiệu quả của thuật toán và khả năng ứng dụng trong thực tế, chúng tôi thử nghiệm trên một số tập dữ liệu từ các nguồn khác nhau được mô tả như sau. 2.4.2 Thí nghiệm 1: Xác thực mô hình bài toán Mô hình được giải bằng GUROBI Optimizer. Chúng tôi nhận thấy rằng các giải pháp mà mô hình của chúng tôi tìm thấy tương đương với giải pháp tốt nhất trong bộ dữ liệu chuẩn của Solomon đã được báo cáo. Những kết quả này cho thấy rằng mô hình của chúng tôi được xác thực. Bảng 2.3 cho biết kết quả của mô hình A-ALNS và MILP là giống nhau. Ngoài ra, các thử nghiệm này cho thấy rằng thuật toán được đề xuất có thể tìm ra các giải pháp tối ưu trong các trường hợp nhỏ rất nhanh so với GUROBI và GUROBI không thể giải quyết mô hình MILP cho các kịch bản có hơn 25 khách hàng trong vòng hai giờ. Lý do chính là mô hình MILP sử dụng nhiều biến phụ trợ để tuyến tính hóa các ràng buộc. Do đó, mô hình MILP không thực tế đối với các bài toán lớn (nó không mở rộng quy mô nếu số lượng biến tăng lên), chủ yếu vì lý do thời gian tính toán. 16
Bảng 2.3: Sự so sánh giữa kết quả của MILP và A-ALNS. MILP model A-ALNS Ins gr gv gc t gr gv gc t RG-1-2-2-2-6 0 1200 145 0.57 0 1200 145 3.69 RG-2-2-2-2-6 0 1200 118 0.34 0 1200 118 0.89 RG-1-2-2-3-8 0 1800 169 4325.14 0 1800 169 4.12 RG-2-2-2-3-8 0 1800 154 4259.2 0 1800 154 5.08 RG-1-2-4-4-25 0 2400 402 7521.64 0 2400 402 17.03 RG-2-2-4-4-25 0 2400 391 7681.02 0 2400 391 19.89 RG-1-2-4-4-50 0 2400 725 13724.62 0 2400 725 402.12 RG-2-2-4-4-50 0 2400 697 14018.26 0 2400 697 544.1 E21 -1-2-4-6-5 0 20610 9982 0.84 0 20610 9982 4.28 E21 -2-2-4-6-5 0 20610 9657 1.58 0 20610 9657 4.75 E21 -1-2-2-2-25 0 200382 21682 6982.5 0 200382 21682 14.34 E21 -2-2-2-2-25 0 197950 20793 7282.02 0 197950 20793 15.21 E21 -1-2-2-4-50 0 401256 38017 11021.72 0 401256 38017 388.62 E21 -2-2-2-4-50 0 401256 37882 12018.88 0 401256 37882 412.44 E21 -1-2-2-4-75 0 426272 58544 67472.13 0 426272 58544 1214.75 E21 -2-2-2-4-75 0 426272 58007 75721.47 0 426272 58007 1493.2 2.4.3 Thí nghiệm 2: So sánh hiệu quả giữa các thuật toán xây dựng cải tiến 2.4.4 Thí nghiệm 3: Sự hiểu quả của thuật toán A-ALNS 2.4.4.1 Tinh chỉnh tham số 2.4.4.2 Sự hiệu quả của các toán tử chèn và toán tử xóa 2.4.4.3 Sức mạnh của chiến lược A-ALNS Trong phần này, chúng tôi tiến hành các thử nghiệm để đánh giá mức độ mạnh mẽ của chiến lược A-ALNS. Chúng tôi nhận thấy rằng khoảng 84,64% đến 99,52% tổng số khách hàng được phục vụ trong hầu hết các trường hợp với std_gr nhỏ hơn hoặc bằng 26,11, phạm vi của ρ2 là [0, 89, 10, 86]. Chúng tôi thấy rằng sự tồn tại của giới hạn dung lượng giới hạn dưới khiến các yêu cầu có quá ít trọng lượng và khoảng thời gian eo hẹp sẽ bị từ chối. Kết quả cũng cho thấy rằng trong hầu hết các trường hợp, số lượng khách hàng chưa được phục vụ của A-ALNS thấp hơn từ 31,48% đến 91,43% so với các thuật toán xây dựng. Thuật toán A-ALNS tiếp tục hoạt động tốt hơn thuật toán LS. Tổng số khách hàng chưa phục vụ mỗi ngày của A-ALNS được cải thiện đáng kể so với thuật toán LS, với tỷ lệ cải thiện duy trì cực kỳ ổn định từ 10,87% đến 73,33%. Đối với các kịch bản lớn của bài toán MTDLC-VR có các ràng buộc phức tạp, kết quả này được giải thích là do cơ chế cân bằng giữa tăng cường và đa dạng hóa của thuật toán A-ALNS tốt hơn so với thuật toán LS. 17
2.4.5 Thí nghiệm 4: Phân tích nhạy của ràng buộc giới hạn dưới Hình 1.2 trình bày số lượng yêu cầu vi phạm giới hạn dưới tải trọng được tìm thấy bởi bốn thuật toán. Số lượng yêu cầu tăng nhanh khi giới hạn dưới của sức chứa của xe được tăng lên. Chúng ta thấy rằng các đường cong có độ dốc thấp từ c(k) = 10% đến c(k) = 60%. Ngược lại, nó tăng nhanh từ c(k) = 60%. Nó cũng chỉ ra rằng ràng buộc cận dưới có ảnh hưởng lớn đến giá trị hàm mục tiêu. Vì vậy, mỗi nhà quản lý phải cân đối giữa mục tiêu tăng tỷ lệ lấp đầy xe tối thiểu và tăng số lượng khách hàng được phục vụ tối đa. Giá trị tỷ lệ giữa 40% và 50% được chấp nhận. Kết quả cũng cho thấy thuật toán vGIA vẫn tốt hơn so với các thuật toán xây dựng khác và thuật toán A-ALNS có số lượng yêu cầu bị vi phạm thấp nhất. Hình 1.2: Số lượng yêu cầu bị xóa khỏi giải pháp khi vi phạm ràng buộc cận dưới tải trọng. 2.5 Tổng kết Chương Chương này xem xét một bài toán lập lịch trình tĩnh mới của VRP, được gọi là vấn đề định tuyến xe đa trung tâm đa chuyến với các ràng buộc về tải trọng giới hạn dưới. Nghiên cứu này lấp đầy khoảng trống trong các công trình khoa học về bài toán này bằng cách kết hợp một số ràng buộc trong thế giới thực, một số ràng buộc đã được xem xét và một số khác chưa được nghiên cứu. Bài toán xem xét được mô hình hóa bằng mô hình MILP và các thách thức về ràng buộc tải trọng giới hạn dưới được phân tích. Kết quả nghiên cứu trong Chương này được công bố trong bài báo [1] trong Danh mục các công trình đã công bố. Đối với các công việc trong tương lai, kịch bản trực tuyến của bài toán MTDLC-VR sẽ được điều tra trong đó các yêu cầu không được biết trước và được tiết lộ trực tuyến trong quá trình thực hiện lịch trình 18