ickup and Delivery Problems (PDPs) are a relevant class of vehicle routing problems in which objects or people need to be collected and distributed. These problems have many applications in logistics, ambulatory services and robotics. In this thesis, we survey the static and dynamic PDPs appearing in the literature, we provide a classification scheme for them, and we show the relations between these problems. We then analyze the complexity of counting the number of feasible solutions of a well known PDP, and of a related scheduling problem, and we show that both problems are hard, namely,... |