2012 Diploma Thesis Title:

  A Cutting Plane Method for the Team Orienteering Problem with Pickups, Deliveries, Time Windows and Capacity Constraints

Abstract

This Diploma thesis addresses a routing problem where a fleet of capacitated vehicles with limited available resources must serve selected customers. Each customer has a unique pick-up and delivery point, and is associated with time windows, as well as with a profit. The goal is to maximize the total profit collected. This problem is formulated based on a) the Team Orienteering Problem (TOP) and b) the Pick-up and Delivery Problem with Time Windows (PDPTW), taking into account constraints for vehicle capacity, time windows, and precedence between each pickup and delivery points. We enhance the Branch and Price method, an exact method implemented for this problem in Baklagis (2012), by applying heuristic and exact methods based on the Cutting Plane theory. These methods use a set of inequalities that decrease the feasible subspace of the problem as much as possible. In fact, this is the main focus of the thesis, i.e. the use of cutting planes in this complex routing problem. We present the mathematical model, the proposed methods, and an extensive set of computational experiments, which study the effect of different inequality types on the results obtained by each method. The contribution of this thesis is that it addresses for the first time the TOP with pick-ups and deliveries by combining the two methods mentioned above, in order to test their efficiency regarding the computational time and the computational efforts of the Branch and Cut Paradigm in comparison with the Branch and Price method.