An ant colony optimization based on local search for the vehicle routing problem with simultaneous pickup-delivery and time window

The Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Window (VRPSPDTW) is an important logistics distribution problem. Due to the complexity of this problem, there are few researches on it and lack of relevant solutions. To solve this problem, this paper proposes to use the ant colony optimization (ACO) for the first time, which a swarm intelligence optimization algorithm. An ant colony optimization algorithm with destory and repair strategies (ACO-DR) is proposed on the basis of ACO. Firstly, ACO-DR designs a random transition rule with direction to improve the probability of the algorithm to search the target and to enhance the global search ability of the algorithm. Secondly, because the positive feedback property of ACO, it is easy for the algorithm to fall into the local optimum. Therefore, two local operators, the destory operator and the repair operator, are added to avoid this phenomenon. Finally, to verify the performance of the proposed ACO-DR algorithm, it is tested on Solomon benchmark and Gehring-Homberge benchmark and compared with the state-of-the-art algorithms. The experimental results show that the ACO-DR algorithm is feasible and provides a new effective algorithm for solving VRPSPDTW problem. Besides, the proposed algorithm also has practical implications for vehicle routing problem and the results show that it is applicable and effective in practical problems. & COPY; 2023 Published by Elsevier B.V.

Automated summary

This paper proposes a new optimization algorithm called ACO-DR based on the ant colony optimization (ACO) to solve the Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Window (VRPSPDTW). ACO-DR improves the search probability and global search ability by designing a random transition rule and introducing destroy and repair strategies to avoid falling into local optima. Experimental results show that ACO-DR outperforms state-of-the-art algorithms on Solomon benchmark and Gehring-Homberge benchmark, providing an effective solution for VRPSPDTW problem.