Bi-objective Routing and Goods Collection Optimization in Vehicle Routing Problems with Simultaneous Pickup and Delivery

This study addresses the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) considering a heterogeneous fleet and time window constraints with the two objectives of minimizing the total routing cost and maximizing the quantity of collected pickups. This problem arises in real-world logistics systems where vehicles deliver goods to customers while simultaneously (optionally) collecting items for return, all within predefined customer service time windows. We formulate this problem as a bi-objective optimization model, and present and compare two heuristics to solve it, an ϵ-constraint-based heuristic, and a Non-dominated Sorting Genetic Algorithm II (NSGA-II) metaheuristic. Computational experiments demonstrate the trade-offs between delivery efficiency and pickup maximization, and show that NSGA-II outperforms the ϵ-constraint-based heuristic in terms of solution quality. NSGA-II reduced routing cost by about 5-13% on the tested instances compared to the ϵ-constraint heuristic while generating a diverse Pareto front of trade-off solutions.