The vehicle routing problem with pickups and deliveries on some special graphs

AbstractThe vehicle routing with pickups and deliveries (VRPD) problem is defined over a graph G=(V,E). Some vertices in G represent delivery customers who expect deliveries from a depot, and other vertices in G represent pickup customers who have available supply to be picked up and transported to a depot. The objective is to find a minimum length tour for a capacitated vehicle, which starts at a depot and travels in G while satisfying all the requests by the delivery and pickup customers, without violating the vehicle capacity constraint, and returns to a depot. We study the VRPD problem on some special graphs, including trees, cycles and warehouse graphs when the depots are both exogenously and endogenously determined. Specifically, we develop linear time algorithms for the VRPD problem on tree graphs and polynomial algorithms on cycle and warehouse graphs