Gerardo Berbeglia (co-supervised by Prof. Gilbert Laporte and Prof. Jean-François Cordeau).  HEC, Universite de Montreal:

Complexity Analyses and Algorithms for Pickup and Delivery Problems

Gerardo's thesis deals with the theoretically and computationally challenging problem of pickup and delivery problems in vehicle routing. Such problems have a wide applicability in practice, including demand-responsive transportation systems such as Dial-a-Ride, elevator dispatching, and bicycle-sharing systems. The thesis contains several far-reaching theoretical and algorithmic contributions in the context of both static and dynamic problems. Highlights include showing that the complexity of counting solutions to the Travelling Salesman Problem with Pickup and Delivery is #P-complete, i.e., the problem of counting the number of solutions is computationally hard; showing that the pickup and delivery problem with partial routes is NP-hard in the strong sense; and using constraint programming and tabu search on the Dial-a-Ride problem to obtain useful practical results.