旅行商问题
遗传算法
计算机科学
数学优化
算法
2-选项
数学
作者
Gabriel Soares,Teobaldo Bulhões,Bruno Petrato Bruck
标识
DOI:10.1016/j.ejor.2024.05.010
摘要
This paper deals with a generalization of the classic traveling salesman problem where each customer is associated with a release date, defined as the time at which the desired product becomes available at the depot. In this problem, a single uncapacitated vehicle is allowed to perform multiple trips in order to satisfy all demands. However, the vehicle cannot start a route unless all the products associated with the demands in the route are released. As a consequence, there might be a waiting time before starting the next route. The objective of the problem is to minimize the completion time of the service, defined as the time at which the vehicle returns to the depot after satisfying all demands. We propose a hybrid genetic algorithm that incorporates more advanced mechanisms to evaluate individuals and to ensure population diversity. We also introduce a novel dynamic programming splitting algorithm that converts a sequence of visits to customers, the so-called giant-tour, into the best set of routes that respects the sequence. Computational experiments performed on 522 benchmark instances show that our approach is able to find all 154 known optimal solutions from the literature. In addition, we were able to improve the best-known upper bounds for 364 instances in significantly shorter computational times when compared to the state-of-the-art.
科研通智能强力驱动
Strongly Powered by AbleSci AI