运筹与管理2025，Vol.34Issue(12)：107-114,8.DOI:10.12005/orms.2025.0382
一种基于学习的模拟退火算法求解逆向物流中车辆路径—装载问题
A Learning-based Simulated Annealing Algorithm for Vehicle Routing-Loading Problem in Reverse Logistics
摘要
Abstract
Reverse logistics refers to the process of collecting products from consumers and returning them to retailers or manufacturers.In this process,each returned product has its own specific value and weight.Since truck drivers have limited working hours,the challenge lies in how to efficiently plan the vehicle route within the specified time and simultaneously optimize the loading strategy to maximize profits.This has become a critical issue that logistics companies need to address.Therefore,the Vehicle Routing-Loading Problem(VRLP)is an important optimization problem in reverse logistics. In VRLP,multiple customer sites are involved,with each site containing several items of known profit and weight.The optimization goal of the problem is to plan vehicle route efficiently within a specified time,visit multiple sites to collect items,and at the same time,maximize the total value of collected items without excee-ding the vehicle's loading capacity.VRLP is a complex NP-hard problem.Its complexity primarily arises from the need to consider multiple interrelated factors,such as vehicle travel time constraints,loading capacity limita-tions,and the value and weight of the goods.These factors are intertwined,making the problem extremely chal-lenging to solve.Traditional exact solution methods often cannot find the optimal solution within a reasonable time frame.In contrast,heuristic algorithms can provide satisfactory feasible solutions in a shorter amount of time,making them well-suited for solving such problems.VRLP originates from real-world applications in reverse logistics and can solve many practical issues in logistics operations.Therefore,developing and researching efficient algorithms to solve VRLP can not only improve the operational efficiency of logistics companies but also provide important theoretical support and practical references for the academic community. To address the NP-hard nature of VRLP,this paper proposes an efficient learning-based simulated annealing algorithm.The algorithm consists of three important components:a learning-based random greedy initialization method,a simulated annealing optimization procedure and a learning probability update mechanism.The algo-rithm first initializes a probability learning matrix and then executes a series of iterations.In each iteration,the algorithm first generates a high-quality initial solution using a learning-based random greedy method,and then updates the initial solution using the simulated annealing procedure to obtain an optimized solution.Finally,the algorithm dynamically updates the probability learning matrix by comparing the initial and optimized solutions,and the probability learning matrix,in turn,guides the creation of high-quality initial solutions.Experimental results show that the proposed algorithm can efficiently solve VRLP.Specifically,the algorithm outperforms comparison algorithms in the literature in terms of solution quality in large and extremely large test cases,offering a new approach to solving the vehicle routing-loading problem in reverse logistics. Future research can focus on several aspects.First,given the NP-hard nature of VRLP,developing efficient exact algorithms remains an important research direction,aiming to provide optimal solutions for medium-and small-scale problems.Second,future studies should consider more real-world factors,such as customer time windows,customer priorities and satisfaction and multi-vehicle coordinated scheduling,to enhance the practicality and adaptability of the problem.Additionally,integrating machine learning techniques,especially deep reinforcement learning,to solve VRLP is also an exciting direction for future research.关键词
逆向物流/路径—装载/模拟退火/背包问题Key words
reverse logistics/routing-loading/simulated annealing/knapsack problem分类
管理科学引用本文复制引用
郑永洪,吴鹏,陆永亮..一种基于学习的模拟退火算法求解逆向物流中车辆路径—装载问题[J].运筹与管理,2025,34(12):107-114,8.基金项目
国家自然科学基金资助项目(72371076) （72371076）
