VRPPD

VRPPD stands for Vehicle Routing Problem with Pickup and Delivery. It generalizes the classic Vehicle Routing Problem (VRP) where each customer request has a pickup site and a delivery site. A fleet of vehicles with limited capacity must service all requests by transporting goods from pickups to deliveries while minimizing a cost objective such as total distance. Each pickup must be served before its corresponding delivery, and vehicle capacity cannot be exceeded along any route. Routes typically start and end at depots, and each request is serviced exactly once.

Constraints include precedence (pickup before delivery) and vehicle capacity; additional constraints may involve time windows, driver hours, fixed depots, and fleet heterogeneity. The objective is often to minimize travel distance or time, though other goals such as minimizing the number of vehicles or lateness may also be used.

Variants include VRPPD with time windows (VRPPDTW), multiple pickups and deliveries per route, multiple depots or a heterogeneous fleet, and synchronized or split deliveries. Some models incorporate stochastic travel times or demand, while others assume deterministic data. Hybrid models combine exact methods with heuristics to handle large instances efficiently.

Solution approaches include exact formulations such as mixed-integer programming solved by branch-and-cut for small to moderate instances, reflecting the NP-hard nature of VRPPD, and a range of heuristics and metaheuristics for larger problems. Common strategies include route construction with savings, precedence-aware local search, and metaheuristics such as genetic algorithms, ant colony optimization, tabu search, and simulated annealing.

Applications include urban logistics, parcel and courier networks, and e-commerce delivery, as well as certain healthcare and recycling operations. VRPPD provides a foundational model for systems requiring coordinated pickups and deliveries under capacity and time constraints, and it is studied in dynamic and real-time settings as data and automation improve.