Tóm tắt Luận á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

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 NP -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}n1 sao cho hàm mục tiêu f được tối thiểu 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 fkz k,1, và tổng quãng đường di chuyển bởi gc =∑ k∈K ∑q(k) q=1 ∑ (i,j)∈E di,jx k,q i,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 ∑ j∈δ+(i) q(k)∑ q=1 xk,qi,j = ∑ j∈δ−(i) q(k)∑ q=1 xk,qj,i , ∀k ∈ K, ∀i ∈ V (2.2) • Ràng buộc về luồng trên mỗi chuyến∑ j∈δ+(i) xk,qi,j = ∑ j∈δ−(i) xk,qj,i , ∀k ∈ K, ∀q = 1, 2, . . . , q(k),∀i ∈ C (2.3) • 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∑ j∈δ−(dp) xk,q−1j,dp = ∑ j∈δ+(dp) xk,qdp,j , ∀k ∈ K, ∀q = 2, 3, . . . , q(k),∀dp ∈ D (2.4) • 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 p(k) = e(p(k)), ∀k ∈ 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,qi,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). wk,qp 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. zk,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,qi 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,qi + ti,j + dr(i) +M(x k,q i,j − 1) + ∑ p∈P wk,qp tunit(i) ≤ sk,qj , (2.6) ∀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,qi + ti,j + dr(i) +M(x k,q i,j − 1) ≤ sk,qj , (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−1i + ti,j + dr(i) +M(z k,q − 1) +M(xk,q−1i,j − 1) ≤ sk,qj , (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,qi +M( ∑ j∈δ+(i) xk,qi,j − 1) ≤ l(i), (2.9) sk,qi +M(1− ∑ j∈δ+(i) xk,qi,j ) ≥ e(i), (2.10) ∀k ∈ K, ∀q = 1, 2, . . .