A comparative study of optimization software performance in vehicle routing problem

Nội dung text: A comparative study of optimization software performance in vehicle routing problem

1. TNU Journal of Science and Technology 226(16): 142 - 149 A COMPARATIVE STUDY OF OPTIMIZATION SOFTWARE PERFORMANCE IN VEHICLE ROUTING PROBLEM Nguyen Thi Lan Vi, Nguyen Truong Thi*, Phan Thi Kim Phung, Nguyen Van Can Can Tho University ARTICLE INFO ABSTRACT Received: 14/9/2021 Vehicle Routing Problem (VRP) is one of the most common problems when designing transportation networks with cost minimization. Revised: 09/11/2021 Therefore, the objective of this study is to identify and select an Published: 10/11/2021 optimization software that can achieve higher efficiency for each type of VRP. Following this consideration, the Mixed-Integer-Linear- KEYWORDS Programming (MILP) models for VRP, Capaciated VRP (CVRP), VRP with time windows (VRPTW), and VRP with pickup & delivery Logistics and time windows (VRPPDTW) are constructed and solved using Optimization software Gurobi, Cplex and Lingo softwares. Numerical examples are given to test the feasibility of the proposed models, and then are used to Transportation compare the effectiveness of these softwares. Moreover, sensitive VRP analysis is conducted to determine which factors have the most Distribution center influence on the cost-objective function. The resulting models suggest that Gurobi may assist decision-makers to obtain better objective values and solution time as compared to the others. NGHIÊN CỨU SO SÁNH HIỆU QUẢ CỦA CÁC PHẦN MỀM TỐI ƯU TRONG BÀI TOÁN ĐỊNH TUYẾN XE Nguyễn Thị Lan Vi, Nguyễn Trường Thi*, Phan Thị Kim Phụng, Nguyễn Văn Cần Trường Đại học Cần Thơ THÔNG TIN BÀI BÁO TÓM TẮT Ngày nhận bài: 14/9/2021 Bài toán định tuyến xe (VRP) là một trong những bài toán được sử dụng nhiều khi thiết kế mạng lưới vận tải tối thiểu chi phí. Vì thế, Ngày hoàn thiện: 09/11/2021 mục tiêu của nghiên cứu này là nhằm xác định và lựa chọn phần Ngày đăng: 10/11/2021 mềm tối ưu phù hợp có thể mang lại hiệu quả cao cho từng dạng bài toán. Theo đó, các mô hình Quy hoạch tuyến tính nguyên (MILP) TỪ KHÓA được đề xuất cho các dạng bài toán VRP, VRP có xem xét tải trọng (CVRP), VRP có xem xét thời gian (VRPTW) và VRP có xem giao Logistics nhận hàng và thời gian giao nhận (VRPPDTW) được xây dựng và Phần mềm tối ưu hóa giải bằng các phần mềm Gurobi, Cplex và Lingo. Các mô hình đề Vận tải xuất được kiểm tra tính khả thi thông qua một ví dụ và sau dó được sử dụng để so sánh sự hiệu quả của các phần mềm này. Bên cạnh đó, VRP nghiên cứu thực hiện phân tích độ nhạy để xác định các yếu tố có ảnh Trung tâm phân phối hưởng lớn nhất đến hàm mục tiêu chi phí. Kết quả từ các mô hình cho thấy, phần mềm Gurobi có thể hỗ trợ người ra quyết định đạt được kết quả tốt hơn về giá trị của hàm mục tiêu và thời gian giải so với các phần mềm khác. DOI: * Corresponding author. Email: ntthi@ctu.edu.vn 142 Email: jst@tnu.edu.vn
2. TNU Journal of Science and Technology 226(16): 142 - 149 1. Giới thiệu Hiện nay, Logistics là một trong những lĩnh vực đang rất phát triển và thu hút nguồn ngân sách lớn của mỗi quốc gia. Theo Ngân hàng thế giới tại Việt Nam (2018), chi phí logistics của Việt Nam chiếm 20,9% GDP, cao hơn so với các nước có trình độ phát triển như EU, Trung Quốc [1]. Trong cơ cấu hoạt động logistic, chi phí vận tải chiếm tỷ trọng cao nhất lên đến 59% [2]. Do đó, các quyết định liên quan đến hoạt động vận tải cần được hoạch định một cách hợp lý. Một trong những giải pháp được đề cập nhiều nhất để giải quyết vấn đề này chính là xây dựng bài toán định tuyến xe. Có nhiều phương pháp khác nhau để giải bài toán VRP bao gồm việc sử dụng các giải thuật hay phần mềm giải tối ưu. Các giải thuật thường được áp dụng phổ biến như: giải thuật đàn kiến (Ant colony) [3], giải thuật PSO (Particle Swarm Optimization) [4] và thuật toán di chuyền (Genetic Algorithm) [5], Nhiều nghiên cứu thực hiện so sánh các giải thuật được sử dụng trong bài toán VRP như nghiên cứu của tác giả Can Yang và các cộng sự (2015) so sánh ba giải thuật heuristic áp dụng cho bài toán VRPTW để tìm ra kết quả tối ưu [6]. Tác giả Lê Quốc Anh (2018) cũng thực hiện nghiên cứu so sánh giải thuật đàn kiến và giải thuật di chuyền cho bài toán định tuyến xe [7]. Việc sử dụng giải thuật có ưu điểm về thời gian giải và có thể hỗ trợ giải các bài toán với quy mô lớn. Tuy nhiên, khi áp dụng các giải thuật cũng có mặt hạn chế trong vấn đề tìm ra các kết quả tối ưu nhất [8]. Các giải thuật khi xây dựng đòi hỏi người sử dụng phải có kiến thức về lập trình, cũng như sự hiểu biết sâu rộng về giải thuật. Do đó, các phần mềm tối ưu hóa với ưu điểm dễ sử dụng và giao diện thân thiện được sử dụng ngày càng phổ biến. Hiện nay, có nhiều phần mềm tối ưu hóa chuyên dụng sử dụng các giải thuật chính xác (Exact optimization) được phát triển và sử dụng rộng rãi như Gams, Gurobi, Cplex hay Lingo. Các phần mềm này được dùng để giải các dạng bài toán tuyến tính (LP), phi tuyến tính (NLP) và tuyến tính nguyên hỗn hợp (MILP), Tuy nhiên, bên cạnh tỉ lệ người dùng, thì sự hiệu quả của các phần mềm này cần được kiểm tra và đánh giá mức độ phù hợp dựa trên các giá trị của hàm mục tiêu và thời gian giải. Từ các nghiên cứu có liên quan, chúng tôi nhận thấy rằng, các nghiên cứu thực hiện so sánh sự hiệu quả của các phần mềm tối ưu trong việc hỗ trợ giải các dạng bài toán VRP khác nhau có giới hạn, mặc dù việc lựa chọn các phần mềm giải có sự ảnh hưởng lớn đến kết quả bài toán. Do đó, nghiên cứu này được thực hiện nhằm hỗ trợ người dùng lựa chọn được phần mềm tối ưu hóa phù hợp trong giải bài toán VRP. 2. Cơ sở lý thuyết Trong thực tế để đưa ra các quyết định phù hợp, các nhà hoạch định vận tải cần xem xét đến nhiều vấn đề liên quan như khả năng chuyên chở của phương tiện, khung thời gian giao và nhận hàng tại mỗi điểm khách hàng, Do đó, bài toán VRP được phân chia thành nhiều dạng khác nhau như CVRP, VRPTW, VRPPDTW, 2.1. Mô hình VRP thuần VRP thuần (classical VRP) là dạng mô hình VRP mà các điểm khách hàng, thời gian di chuyển và thời gian phục vụ tại các điểm khách hàng là một tham số tất định và được biết trước. Dạng bài toán này bao gồm việc thiết kế lộ trình cho các xe giao hàng với mục tiêu chính là xác định tuyến đường di chuyển tối ưu, tối thiểu khoảng cách di chuyển và chi phí vận hành cho mạng lưới. 2.2. Mô hình VRPTW VRPTW là mô hình mở rộng của VRP dựa trên việc xem xét thêm về yếu tố thời gian (Time Window). Mục tiêu của dạng bài toán này là đảm bảo phương tiện giao hàng đúng khung giờ quy định tại các điểm khách hàng. Điển hình như nghiên cứu của tác giả Ugur Bac và cộng sự (2021) đã áp dụng mô hình này đối với xe điện, đồng thời bổ sung thêm các ràng buộc về thời gian di chuyển và sạc lại của xe [9]. 143 Email: jst@tnu.edu.vn
3. TNU Journal of Science and Technology 226(16): 142 - 149 2.3. Mô hình CVRP Bài toán CVRP là dạng bài toán bao gồm một tập hợp xe và tập hợp các điểm giao nhận hàng. Ràng buộc của bài toán sẽ liên quan đến việc đảm bảo khả năng vận chuyển của xe, đồng thời có thể đáp ứng nhu cầu của các điểm khách hàng. Cùng với hướng nghiên cứu đó, tác giả Machado và các cộng sự (2021) đã phát triển mô hình định tuyến xe cho bài toán (CVRP) bằng cách áp dụng giải thuật GRASP (Greedy Randomized Adaptive Search Procedure) [10]. Với mục tiêu hoạch định tuyến đường di chuyển sao cho tối thiểu chi phí vận hành, lựa chọn các loại phương tiện phù hợp để tiết kiệm chi phí và đáp ứng tối đa nhu cầu tại các điểm khách hàng. 2.4. Mô hình VRPPDTW Trong thực tế, hàng hóa không chỉ được vận chuyển từ kho đến điểm khách hàng, mà còn nhận tại một số điểm phân phối đưa về kho và đảm bảo về ràng buộc liên quan đến thời gian giao nhận. Tác giả Alireza và cộng sự (2021) đã nghiên cứu vấn đề giao nhận hàng trong khoảng thời gian quy định và xem xét đến khả năng chuyên chở của xe [11]. Nghiên cứu của tác giả Casazza và các cộng sự (2018) về bài toán VRPPDTW có sự phân chia lượng hàng hóa giao nhận giữa các xe. Mô hình áp dụng thuật toán branch & cut để tìm ra giải pháp tối ưu nhất [12]. 3. Phương pháp nghiên cứu 3.1. Cách tiếp cận - Nghiên cứu lý thuyết về các dạng mô hình toán dùng trong bài toán vận tải. - Xây dựng mô hình toán tối ưu cho bốn dạng bài toán VRP, CVRP, VRPTW và VRPPDTW. - Sử dụng các phần mềm tối ưu hóa khác nhau để giải các dạng mô hình toán VRP. - Phân tích, so sánh hiệu quả và lựa chọn phần mềm giải phù hợp với từng dạng toán. 3.2. Phương pháp - Xây dựng các mô hình toán MILP tương ứng với bốn dạng bài toán VRP khác nhau. - Sử dụng giải thuật chính xác để giải các dạng mô hình dựa trên các phần mềm tối ưu hóa là Gurobi, Cplex và Lingo. - Phân tích độ nhạy nhằm xác định yếu tố ảnh hưởng nhiều nhất đến kết quả tối ưu và dựa trên các yếu tố này để so sánh và lựa chọn phần mềm tối ưu hóa phù hợp với các dạng bài toán. 4. Mô hình toán 4.1. Mô tả bài toán Trong phần này, các mô hình MILP lần lượt được xây dựng tương ứng với bốn dạng bài toán bao gồm: VRP, CVRP, VRPTW, VRPPDTW. Việc xác định các biến, tham số và ràng buộc trong các mô hình sẽ phụ thuộc vào đặc tính của từng dạng bài toán. Tuy nhiên, các dạng bài toán này cùng một hàm mục tiêu duy nhất là tối thiểu chi phí vận tải cho doanh nghiệp. Sau khi xây dựng được các mô hình, nghiên cứu tiếp tục sử dụng các phần mềm hỗ trợ cho việc tìm ra lời giải tối ưu. Hiệu quả của các phần mềm được đánh giá thông qua các yếu tố về thời gian và giá trị hàm mục tiêu tại một thời điểm xem xét so với kết quả tối ưu. 4.2. Giả định Mô hình được xây dựng với một số giả định sau: - Các phương tiện sẽ bắt đầu xuất phát tại kho và quay trở về kho khi kết thúc lộ trình. - Trạng thái hoạt động của các xe tốt, không xảy ra hư hỏng trong quá trình vận chuyển hàng. - Chi phí và vận tốc của xe là không đổi trong suốt quá trình xe di chuyển. - Nhu cầu của khách hàng là tất định và được biết trước. - Tải trọng của các xe bằng với sức chứa của xe. 144 Email: jst@tnu.edu.vn
4. TNU Journal of Science and Technology 226(16): 142 - 149 4.3. Các ký hiệu trong mô hình 4.3.1. Tập hợp N: Tập hợp điểm khách hàng, trong đó 0 là kho {0,1,2. . } K: Tập hợp xe {1,2,3. . 퐾} 4.3.2. Tham số tij : Thời gian di chuyển từ điểm i đến j (giờ) di : Nhu cầu của mỗi điểm si : Thời gian phục vụ tại điểm i (giờ) M : Một giá trị rất lớn qk : Khả năng chuyên chở tối đa của xe k (kg) qpi : Lượng hàng nhận tại điểm i bởi xe k (kg) dij : Khoảng cách di chuyển từ i đến j (km) qdi : Lượng hàng giao tại điểm i bởi xe k (kg) ck : Chi phí di chuyển của xe k (VND/km) qkk : Lượng hàng còn lại trên xe (kg) tmin : Thời gian bắt đầu lộ trình tại kho (giờ) tmax : Thời gian kết thúc lộ trình tại kho (giờ) 4.3.3. Biến số 푖푗: 1, nếu xe k di chuyển từ i đến j, ()ij , ngược lại là 0; 푌푖 : Thời điểm bắt đầu phục vụ tại điểm j của xe k (giờ); 퐹푖푗: Lượng hàng xe vận chuyển trên tuyến đường từ điểm i đến điểm j (kg). 4.4. Hàm mục tiêu Trong nghiên cứu này, mô hình toán để tối ưu hóa chi phí được thiết lập. Mục tiêu là giảm thiểu tổng chi phí bao gồm: chi phí thuê tài xế, chi phí nhiên liệu và chi phí bảo trì. NNK k Min Z=  Xij c k d ij i j j k 4.5. Ràng buộc mô hình 4.5.1. Ràng buộc mô hình VRP Mô hình VRP được xây dựng dựa trên các ràng buộc từ C1- C6. Cụ thể : N k (C1)  X 0 j =1 k K,,,  i j N i j j 0 N k (C2)  X i0 =1 k K,,,  i j N i j i 0 kk XXij−= ji 0 i N, i 0, k K (C3) jN jN k (C4) Xij = 0 k K,,,  i j N i = j KN k i N,0 i (C5) X ij =1 k j i k (C6) Xij 0 i,, j N k K Ràng buộc (C1) và (C2) quy định tất cả các xe bắt đầu lộ trình tại kho và quay lại kho sau khi kết thúc lộ trình. Ràng buộc (C3) đảm bảo liên kết giữa hai điểm khách hàng trên cùng một tuyến đường. Ràng buộc (C4) thể hiện mỗi xe di chuyển không được vòng lại trạm trước đó. Ràng buộc (C5) quy định về số lần phục vụ tại mỗi điểm, mỗi điểm được chỉ định cho một xe và được phục vụ một lần trong toàn bộ lộ trình di chuyển. Ràng buộc (C6) quy định các biến nguyên, dương. 4.5.2. Ràng buộc mô hình VRPTW 145 Email: jst@tnu.edu.vn
5. TNU Journal of Science and Technology 226(16): 142 - 149 Mô hình VRPTW được xây dựng dựa trên các ràng buộc từ C1 - C6 kết hợp với ràng buộc từ C7 – C11. Cụ thể, các ràng buộc từ C7 – C11 được trình bày như sau: kk (C7) Yo= Y j + s j + t j0 j N, k K k (C8) Ytjj=+0 0 k K,  j N , i = 0 kk (C9) Yj= Y i + s i + t ij k K,,,  i j N i j k tmin Y 0 t max k K,  i , j N , i j , j = 0 (C10) (C11) Yjk 0 k K,,  i j N Ràng buộc (C7), (C8), (C9) và (C10) xác định thời điểm đến tại mỗi điểm khách hàng. Ràng buộc (C11) quy định các biến nguyên dương. 4.5.3. Ràng buộc mô hình CVRP Mô hình CVRP được xây dựng dựa trên các ràng buộc từ C1 - C6 kết hợp với ràng buộc từ C12 – C16. Cụ thể, các ràng buộc từ C12 – C16 được trình bày như sau: NN k (C12) di* X ij q k  kK i 0 j i KNKN kk (C13) Fji−=  F ij d i  iN k j i k j i kk Fij −()* q k d i X ij k K,,,  i j N i j (C14) kk (C15) dj* X ij F ij k K,,,  i j N i j k F 0 k K,,  i j N (C16) ij Ràng buộc (C12) quy định tổng nhu cầu tại các điểm khách hàng trong cùng một lộ trình không được vượt quá tải trọng cho phép của xe. Ràng buộc (C13) thể hiện nhu cầu của điểm khách hàng i được xác định thông qua lượng hàng hóa vận chuyển giữa i và j. Ràng buộc (C14), (C15) quy định khối lượng hàng hóa trên xe phải đảm bảo đủ để phục vụ nhu cầu tại mỗi điểm. Ràng buộc (C16) quy định các biến nguyên, dương. 4.5.4. Ràng buộc mô hình bài toán VRPPDTW Mô hình VRPPDTW được xây dựng dựa trên các ràng buộc từ C1 – C11 kết hợp với ràng buộc từ C17 – C21. Cụ thể, các ràng buộc từ C17 – C21 được trình bày như sau: NNN kk (C17) F0 j=  X ij* qd j  kK j i j kk Fij X ij* q k k K,,,  i j N i j (C18) NNNNNN k k k k (C19) Fi00=  X ij qp j +  F j −  X ij qd j  kK i 00 i i j j i i j k k k (C20) Fji F ij − qd j + qd j +(1 − X ij )* M k K,,,  i j N i j Ràng buộc (C17) đảm bảo lượng hàng hóa vận chuyển phải đáp ứng nhu cầu khách hàng. Ràng buộc (C18) quy định lượng hàng hóa còn lại trên xe và lượng hàng hóa nhận lên tại mỗi điểm không được vượt quá tải trọng của xe. Ràng buộc (C19) và (C20) tính toán lượng hàng hóa còn lại trên xe qua mỗi điểm khách hàng. 5. Phân tích kết quả Như đã đề cập trước đó, mỗi bài toán sẽ được xây dựng dựa trên các ràng buộc phù hợp với đặc điểm từng dạng. Bài toán VRPPDTW được xem xét kết hợp đồng thời cả hai yếu tố về khả 146 Email: jst@tnu.edu.vn
6. TNU Journal of Science and Technology 226(16): 142 - 149 năng chuyên chở và thời gian giao hàng, đây cũng là một trong những dạng bài toán phổ biến và được áp dụng nhiều trong thực tế. Do đó dựa trên mô hình này, chúng tôi sẽ thực hiện phân tích kết quả của mô hình toán với các phần mềm giải khác nhau. 5.1. Kết quả bài toán VRPPDTW Trong phần này, để có thể đánh giá và so sánh hiệu quả của các phần mềm, chúng tôi tiến hành giải và phân tích các kết quả từ mô hình VRPPDTW với 1 kho (0) và 24 điểm khách hàng. Các điểm khách hàng trong mạng lưới phân phối chủ yếu là nhà bán lẻ, siêu thị và các cửa hàng bách hóa và thường tập trung nhiều ở khu vực đông dân cư. Vị trí của các điểm khách hàng được thể hiện trong Hình 1. Sau khi tiến hành giải trên các phần mềm tối ưu là Gurobi, Cplex và Lingo thì thu được kết quả ba tuyến đường di chuyển. Trình tự đến tại mỗi điểm khách hàng trong mạng lưới được thể hiện cụ thể trong Hình 1. Hình 1. Kết quả mạng lưới vận tải với 3 tuyến đường di chuyển Các phần mềm giải tối ưu bao gồm: Phần mềm Gurobi phiên bản 9.0.2, ILOG CPLEX phiên bản 20.1 và Lingo phiên bản 18.0 được cài đặt trên máy Core i5 với 8GB RAM và 2.40 GHz CPU. Sau khi tiến hành giải bài toán VRPPDTW trên ba phần mềm, kết quả cho thấy rằng, Gurobi cần 126 giây để tìm được kết quả tối ưu là 763.730 VND. Trong khi đó, Cplex cần 640 giây và Lingo cần 1.309 giây để đạt được kết quả tối ưu trên. Tuy nhiên, để đưa ra kết luận chính xác về mức độ hiệu quả của các phần mềm thì cần xem xét yếu tố nào ảnh hưởng đến thời gian giải mô hình. Do đó, chúng tôi tiến hành phân tích độ nhạy dựa trên các yếu tố biến đổi bao gồm thời điểm xem xét kết quả và số lượng điểm khách hàng phân bổ trong mạng lưới. Mỗi trường hợp sẽ dựa trên hai yếu tố chính là số lượng khách hàng phục với 10, 15, 20, 25 và 30 điểm khách hàng và thời điểm xem xét kết quả tối ưu tại giây thứ 1.000, 1.100 và 1.200. Mục tiêu của việc phân tích độ nhạy nhằm xác định các yếu tố nào sẽ ảnh hưởng lớn nhất đến chi phí, cũng như thời gian tìm ra kết quả tối ưu. Kết quả sau khi phân tích độ nhạy được trình bày trong Bảng 1. Bảng 1. Phân tích ANOVA giá trị hàm mục tiêu với các yếu tố thay đổi Trường hợp Phần mềm Yếu tố F_value P_value Thời điểm xem xét 26,25 0,012 1 Gurobi Số lượng khách hàng 34,27 0,010 Thời điểm xem xét 16,48 0,007 2 Cplex Số lượng khách hàng 22,09 0,024 Thời điểm xem xét 10,96 0,000 3 Lingo Số lượng khách hàng 16,25 0,040 Nghiên cứu xem xét mức ý nghĩa với α = 0,05, dựa trên kết quả phân tích ANOVA cho thấy, các giá trị P trong mỗi trường hợp đều nhỏ hơn mức ý nghĩa (P_value < α = 0,05) là các yếu tố ảnh hưởng đến giá trị hàm mục tiêu. Tuy nhiên, khi xem xét giá trị F qua từng trường hợp thấy 147 Email: jst@tnu.edu.vn
7. TNU Journal of Science and Technology 226(16): 142 - 149 rằng, yếu tố số lượng khách hàng qua mỗi trường hợp đều có F_value lớn hơn yếu tố thời điểm xem xét. Có thể nói rằng, đây là yếu tố ảnh hưởng nhiều nhất đến giá trị hàm mục tiêu, cũng như thời gian giải. Tuy nhiên, nếu chỉ xem xét đối với dạng bài toán VPRPDTW thì chưa thể so sánh được hiệu quả của các phần mềm. Do đó, chúng tôi tiến hành xem xét thêm các dạng bài toán VRP thuần, CVRP và VRPTW với số lượng khách hàng khác nhau để đảm bảo tính chính xác của nghiên cứu. 5.2. Kết quả bốn dạng bài toán tối ưu qua các trường hợp xem xét Tương ứng với mỗi dạng bài toán, chúng tôi sẽ xem xét theo 11 trường hợp về số lượng điểm khách hàng tương ứng từ 10 đến 60 điểm. Kết quả cụ thể được trình bày trong các Hình 2 (a), (b), (c) và (d). (a) (b) (c) (d) Hình 2. Biểu đồ kết quả giá trị hàm mục tiêu: (a) Mô hình VRP, (b) Mô hình VRPTW (c) Mô hình CVRP và (d) Mô hình VRPPDTW Trong phần này, chúng tôi sẽ xem xét các kết quả mô hình tại thời điểm 1.200 giây để so sánh các giá trị hàm mục tiêu. Biểu đồ kết quả bài toán VRP thuần trong Hình 2 (a) cho thấy rằng, đối với các trường hợp từ 10 - 35 điểm khách hàng thì kết quả hàm mục tiêu không có sự khác biệt giữa ba phần mềm. Tuy nhiên, đối với trường hợp 40 điểm khách hàng thì có sự khác biệt, giá trị hàm mục tiêu được giải trên phần mềm Lingo cao hơn so với kết quả tối ưu và kết quả mô hình được giải trên hai phần mềm còn lại. Trường hợp từ 40 - 60 điểm khách hàng có sự khác biệt rõ rệt nhất. Đối với trường hợp 60 điểm khách hàng được xem xét tại thời điểm 1.200 giây cho thấy rằng, kết quả chạy từ phần mềm Gurobi có giá trị gần với kết quả tối ưu nhất và có độ lệch chỉ cao hơn 4% so với kết quả tối ưu. Trong khi đó, kết quả từ phần mềm Cplex lệch 6,4% và kết quả từ phần mềm Lingo lệch 9,8% so với kết quả tối ưu. Điều này chứng minh, đối với các dạng bài toán VRP trên thì phần mềm Gurobi sẽ phù hợp với các dạng bài toán trên và có hiệu quả giải tốt nhất. 6. Kết luận và đề xuất Nghiên cứu đã cung cấp một cái nhìn tổng quát về bài toán định tuyến xe và phương pháp tối ưu hóa chính xác. Các phần mềm tối ưu hóa được xem là công cụ hữu hiệu trong việc giải quyết các bài toán tối ưu hóa bởi tính năng dễ sử dụng và khả năng hỗ trợ tốt cho người ra quyết định. 148 Email: jst@tnu.edu.vn
8. TNU Journal of Science and Technology 226(16): 142 - 149 Kết quả từ nghiên cứu cho thấy rằng, phần mềm Gurobi cho các kết quả tốt hơn so với các phần mềm còn lại trong các giới hạn về số lượng khách hàng và thời gian thử nghiệm. Tuy nhiên, sự hiệu quả của phần mềm này có thể còn phụ thuộc vào sự phức tạp của các dạng bài toán được xem xét. Vì vậy, nghiên cứu trong tương lai cần mở rộng mạng lưới vận tải bằng cách xem xét thêm khách hàng và thời gian giải để đánh giá chính xác hơn về hiệu quả của các mô hình cũng như các phần mềm khi được ứng dụng trong các bài toán vận tải. TÀI LIỆU THAM KHẢO / REFERENCES [1] Song Tan Logistics Joint Stock Company, "Services accounted for 20.9% of logistics Vietnam GDP," 2016. [Online]. Available gdp-ca-nuoc.html. [Accessed Sep. 09, 2021]. [2] The Voice Of VietNam - VOV World, "High logistics costs affect the competitiveness of the economy," 2018. [Online]. Available: canh-tranh-cua-nen-kinh-te-751705.vov. [Accessed Sep. 16, 2021]. [3] F. Yan, "Autonomous vehicle routing problem solution based on artificial potential field with parallel ant colony optimization (ACO) algorithm," Pattern Recognition Letters, vol. 116, pp. 195-199, 2018. [4] Y. Peng and H.-Y. Zhu, "Research on Vehicle Routing Problem with Stochastic Demand and PSO-DP Algorithm with Inver-over Operator," Systems Engineering - Theory & Practice, vol. 28, no. 10, pp. 76-81, 2008. [5] B. M. Baker and M. A. Ayechew, "A genetic algorithm for the vehicle routing problem," Computers & Operations Research, vol. 30, no. 5, pp. 787-800, 2003. [6] C. Yang, Z. Guo, and L. Liu, "Comparison study on slgorithms for Vehicle Routing Problem with Time Windows," Proceedings of the International Conference on Industrial Engineering and Engineering Management, 2015, pp. 257-260. [7] A. Q. Le, "Compare the efficiency of genetic algorithm and ant swarm optimization algorithm for the traveler problem," (in Vietnamese), Institute of Engineering and Technology, Vinh University, vol. 48, no. 3A, pp. 5-14, 2019. [8] Mirabo, "The importance of algorithms in solving problems," 2021. [Online]. Available: [Accessed Sep. 05, 2021]. [9] U. Bac and M. Erdem, "Optimization of electric vehicle recharge schedule and routing problem with time windows and partial recharge: A comparative study for an urban logistics fleet," Sustainable Cities and Society, vol. 70, p. 102883, 2021. [10] A. M. Machado, G. R. Mauri, M. C. S. Boeres, and R. d. A. Rosa, "A new hybrid matheuristic of GRASP and VNS based on constructive heuristics, set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem," Expert Systems with Applications, vol. 184, p. 115556, 2021. [11] A. Fallahtaftia, H. Karimib, E. Ardjmandc, and I. Ghalehkhondabid, Time slot management in selective pickup and delivery problem with mixed time windows, Computers & Industrial Engineering, 2021. [12] M. Casazza, A. Ceselli, and R. Wolfler Calvo, "A branch and price approach for the Split Pickup and Split Delivery VRP," Electronic Notes in Discrete Mathematics, vol. 69, pp. 189-196, 2018. 149 Email: jst@tnu.edu.vn