Multitask-Based Evolutionary Optimization for Vehicle Routing Problems in Autonomous Transportation

In autonomous transportation, the vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW) plays a crucial role in enhancing transportation efficiency, thereby garnering significant research attention over the past decade. However, due to the increased complexity of VRPSPDTW, traditional heuristic algorithms have been inadequate in solving this problem. To address this challenge, this paper proposes a multitask-based evolutionary algorithm (MBEA) with knowledge transfer designed specifically for solving VRPSPDTW in autonomous transportation. MBEA tackles large-scale VRPSPDTW instances by utilizing multiple auxiliary tasks to aid the optimization process. Initially, MBEA generates k different auxiliary tasks by randomly selecting a subset of customers from the original VRPSPDTW. Subsequently, an evolutionary multitasking approach is employed to generate offspring solutions. This enables the transfer of valuable routing information among tasks, facilitating the evolutionary search for the original VRPSPDTW. Experimental studies conducted on a practical test suite of large-scale VRPSPDTW instances validate the superiority of our proposed algorithm over several recently proposed approaches. Note to Practitioners-The vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW) is prevalent in autonomous transportation and finds application in various industrial sectors. It arises when manufacturing companies need to collect scrap products from customers for recycling purposes or deliver purchased commodities within specified time windows. However, traditional optimization methods face challenges in effectively addressing these problems due to their large-scale requirements and the necessity to provide satisfactory service. Thus, this paper proposes a multitask-based evolutionary algorithm with knowledge transfer that aims to obtain optimal solutions for VRPSPDTW. Our algorithm utilizes multiple auxiliary tasks to facilitate the optimization process for the original large-scale VRPSPDTW. Experimental results demonstrate the effectiveness of our approach in dealing with practical large-scale VRPSPDTW within a reasonable time frame.

Automated summary

In this paper, a multitask-based evolutionary algorithm (MBEA) with knowledge transfer is proposed to solve the vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW) in autonomous transportation. The algorithm tackles large-scale VRPSPDTW instances by utilizing multiple auxiliary tasks, facilitating the evolutionary search process. Experimental results demonstrate the effectiveness of the proposed algorithm in dealing with practical VRPSPDTW problems.