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

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ế, 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 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.
Nội dung trích xuất từ tài liệu:
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 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: https://doi.org/10.34238/tnu-jst.5035 * Corresponding author. Email: ntthi@ctu.edu.vn http://jst.tnu.edu.vn 142 Email: jst@tnu.edu.vn 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ệ ...