Optimization Algorithms for Different Routing Problems

In this thesis, we develop exact and heuristic methods for routing problems with various features. In Chapter 2 we study the Pickup and Delivery Problem with Time Windows and Last-in-First-out Loading (PDPTWL), a routing problem that aims at minimizing the cost to serve a set of customers (consisting of pickup and delivery locations) within their time windows, using a fleet of capacitated vehicles and handling their loads with a Last-in-First-out policy. We propose an exact iterative branch-and-price method using column generation to solve the linear relaxation of a set partitioning formulation, where variables correspond to (non-necessarily elementary) routes. Reduced-cost variable fixing is applied to reduce the number of variables in the problem. The bound obtained at the root node is tight and can be computed in a few seconds. The exact method is competitive with the state of the art. In Chapter 3 we study the Single Liner Shipping Service Design problem (SLSSD), which arises in the optimization of the global liner shipping network. In this context, the container carriers follow fixed tours publicly announced, ensuring all ports are visited with a weekly schedule; the objective of the problem is optimizing one of those tours, ensuring requests are satisfied complying with specified path duration constraints. We develop efficient Iterated Local Search heuristics that can find very good solutions for the SLSSD with very limited computing time (e.g., a few seconds), so they could be used as components for algorithms optimizing more complex global-scale liner shipping networks. In Chapter 4 we study the two-stage Robust Orienteering Location-Routing Problem (ROLRP), in which the decision-maker determines the set of depots to open in the first stage and solves a multi-depot team orienteering problem in the second stage. We study the features of ROLRP in depth through extensive experimentation, implementing different Robust Optimization methods inspired by the literature (i.e., column-and-constraint generation, branch-and-price, and cut-generation), considering different uncertainty sets and varying problem parameters. The column-and-constraint generation and the cut-generation methods are the most efficient, solving almost all test instances with up to 100 customers, and we assess the value of the recourse stage, which provides significant savings.