A Model for the Capacitated Vehicle Routing Problem with Pickup and Delivery Considering Package Returns

Abstract (EN)

Following the COVID-19 pandemic, online purchasing has grown rapidly. The logistics industry has prioritized route planning, which relates to the Capacitated Vehicle Routing Problem with Pickup and Delivery (CVRPPD), to reduce operational costs. However, existing studies have not yet examined route planning in cases where packages are returned due to reasons such as incorrect addresses, absence of the recipient, or refusal of acceptance. This research, therefore, develops a mathematical model for logistics route planning with capacity constraints, which supports both pickup and delivery while accounting for the probability of package returns. The authors studied maps of various sized cities in the United States and found that the probability of a package return is correlated with the probability of delivery failure followed a sigmoid curve. The calculated probability of failure showed similar results across all routing methods. In terms of distance and processing time, the Saving Algorithm yielded results comparable to the Nearest Neighbor Heuristic but significantly lower than Simulated Annealing. Regarding the probability of failure, the Saving Algorithm provided slightly lower results than the other methods. This mathematical model can be practically applied to route planning, helping to increase efficiency and reduce transportation costs, while also providing assurance to operators regarding package transportation in the event of returns.