040711 DK PhD-M: MIP - Solution methods and Applications (2008W)

Part I: Pickup and Delivery Vehicle Routing Problems

The first part of the seminar will cover models and algorithms for pickup and delivery vehicle routing problems. We will first present a classification of the different problems that have been studied in the literature and an overview of the main solution approaches. We will then focus on branch-and-cut and branch-and-price methods for the pickup and delivery problem with time windows. We will also describe some meta-heuristics for this problem. We will finally describe some special cases such as the travelling salesman problem with LIFO loading.

Part II: Benders Decompositions and Applications in Logistics and Transportation

The second part will address some integrated planning problems which are well suited for a primal decomposition approach. We will first introduce the general Benders decomposition methodology. We will then explain its application to three families of problems: the assignment of locomotives and cars to passenger trains, the integrated routing of aircraft and scheduling of crews, and the design of logistics networks. In each case, we will describe the application context and show how Benders decomposition can lead to efficient solution algorithms.