This talk concerns the problem of finding a Hamiltonian route for a capacitated vehicle serving a set of customers. Each customer delivers and/or require known demands of some products. A product can have single or multiple sources and destinations. The routing costs are known, and the problem is to find the shortest route if one exists. We write a mathematical model for this problem and develop a branch-and-cut technique for the exact solution. We also show some preliminary computational results on small instances.

Given a vehicle and a set of customers who have some explicit pickup and delivery requests, the Pickup and Delivery Problem (PDP) consists of designing vehicle routes so that all customer requests are satisfied. Each request specifies a pickup and a delivery location. The vehicle must visit each pickup location before its corresponding delivery one. With this constraint, the PDP can be seen as a TSP with precedence constraints. We will review polyhedral results existent in the literature and propose new classes of valid inequalities. We will give conditions under which some classes of inequalities are facets for the PDP polytope. Preliminary numerical results for a branch-and-cut algorithm will be presented.

This talk presents an exact column generation algorithm for the pickup and delivery problem with time windows. Computational tests show that instances with up to 500 requests can be solved to optimality when time windows are tight. We also show how dial-a-ride problems can be solved using column generation

This paper addresses a variation of the traveling salesman problem with pickup and delivery in which loading and unloading operations have to be executed in a LIFO (Last-in-First-Out) order. We present tabu search and variable neighbourhood search metaheuristics based on three exchange operators specially adapted to this problem. We also evaluate the performance of the metaheuristics on instances from TSPLIB.