Back
Texte intégral
Doctoral thesis

Efficient combinatorial optimization algorithms for logistic problems

Show more…
    04.09.2018

132 p

Thèse de doctorat: Università della Svizzera italiana, 2018

Optimization
Routing
Stochastic combinatorial optimization
Metaheuristics
Exact algorithms
Orienteering problem
Sequential ordering problem
Capacitated vehicle routing
Orienteering problem with stochastic travel and service times
Variable neighborhood search
Monte Carlo sampling
English 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%.
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1318819
Statistics
Document views: 191 File downloads:
  • 2018INFO011.pdf: 106