Efficient combinatorial optimization algorithms for logistic problems
Staff - Faculty of Informatics
Date: 4 September 2018 / 13:30 - 15:00
USI Lugano Campus, room CC-351, Main building (Via G. Buffi 13)
You are cordially invited to attend the PhD Dissertation Defense of Vasileios PAPAPANAGIOTOU on Tuesday, September 4 2018 at 13h30 in room CC-351 (Main building)
The field of logistics and combinatorial optimization features a wealth of NP-hard problems that are of great practical importance. For this reason it is important that we have efficient algorithms to provide optimal or near-optimal solutions. In this work, we study, compare and develop Sampling-Based Metaheuristics and Exact Methods for logistic problems that are important for their applications in vehicle routing and scheduling. More specifically, we study two Stochastic Combinatorial Optimization Problems (SCOPs) and finally a Combinatorial Optimization Problem using methods related to the field of Metaheuristics, Monte Carlo Sampling, Experimental Algorithmics and Exact Algorithms. For the SCOPs studied, we emphasize studying the impact of approximating the objective function to the quality of the final solution found.
We begin by examining Solution Methods for the Orienteering Problem with Stochastic Travel and Service Times (OPSTS). We introduce the state-of-the-art before our contributions and proceed to examining our suggested improvements. The core of our improvements stem from the approximation of the objective function using a combination of Monte Carlo sampling and Analytical methods. We present four new Evaluators (approximations) and discuss their advantages and disadvantages. We then demonstrate experimentally the advantages of the Evaluators over the previous state-of-the-art and explore their trade-offs. We continue by generating large reference datasets and embedding our Evaluators in two Metaheuristics that we use to find realistic near-optimal solutions to OPSTS. We demonstrate that our results are statistically significantly better than the previous state-of-the-art.
In the next chapter, we present the 2-stage Capacitated Vehicle Routing Problem with Stochastic Demands inspired by an environmental use case. We propose four different solution approaches based on different approximations of the objective function and use the Ant Colony Metaheuristic to find solutions for the problem. We discuss the trade-offs of each proposed solution and finally argue about its potentially important environmental application.
Finally, focus on exact methods for the Sequential Ordering Problem (SOP). Firstly, we make an extensive experimental comparison of two exact algorithms existing in the literature from different domains (cargo and transportation and the other compilers). From the experimental comparison and application of the algorithms in new contexts we were able to close nine previously open instances in the literature and improve seventeen more. It also led to insights for the improvement of one of the methods (The Branch-and-Bound Approach - B&B). We proceed with the presentation of the improved version that led to the closing of eight more instances and speeding up the previous version of the B&B algorithm by 4%-98%.
- Prof. Luca Maria Gambardella, IDSIA, Switzerland (Research Advisor)
- Prof. Roberto Montemanni, IDSIA, Switzerland (Research co-Advisor)
- Prof. Evanthia Papadopoulou, Università della Svizzera Italiana, Switzerland (Internal Member)
- Prof. Fernando Pedone, Università della Svizzera Italiana, Switzerland (Internal Member)
- Prof. Agostino Bruzzone, University of Genoa, Italy (External Member)
- Prof. Bernard Ries, University of Fribourg, Switzerland (External Member)