Capacitated Vehicle Routing Problem With Pickup and Delivery in Robotic Mobile Fulfillment Systems

Abstract

This paper addresses the capacitated vehicle routing problem with pickup and delivery (CVRPPD) in robotic mobile fulfillment systems (RMFSs), focusing on planning routes for robots to transport goods. The CVRPPD in RMFSs has two unique features compared to the classic vehicle routing problem: robots have open starting and ending points, meaning they do not need to start or return to a depot, and there may already be goods on the robots. Based on these features, a mixed integer programming model is formulated for the CVRPPD in RMFSs, aiming to minimize transportation costs. An adaptive large neighborhood search (ALNS) heuristic, combined with adaptive local search, is proposed to solve the problem. The performance of the ALNS heuristic is evaluated through computational experiments. In small-scale instances, the average percentage deviation in objective values compared to the CPLEX solver is 22.04%. In large-scale instances from a real project, the average percentage deviation compared to the greedy algorithm (GA) is -5.8%. Extensive computational results indicate that the proposed heuristic algorithm performs well in terms of solution quality and solving time.

Keywords

• Vehicle routing problem
• metaheuristic algorithm
• robotic mobile fulfillment system