Routing Problems with Objective Function of Increasing Complexity

Routing problems are a key issue in supply-chain and distribution systems today, and they are becoming increasingly complex, due to new factors that are entering the logistic network: the fast development of telecommunication makes not only the perception but also the changes of the world more rapid, stochastic and difficult to forecast, moreover, the ever common merging of companies leaves distribution planners with bigger and more complex problems to solve. For these reasons there is an ever increasing interest on routing models that are dynamic, stochastic, rich of constraints, and thus have objective functions more and more complex. Moreover, the mathematical formulation and modeling of an optimization problem is a key step, that not only influences the methods of solutions, but most importantly determines the impact of solutions and solutions methods on the real world. In this project we aim at two main goals. The first one is the formal analysis and comparison among different modeling approaches, in order to better understand the role of the model formulation and of the type of uncertainty. Such analysis is particularly useful, since in the literature there is a notable need for systematic comparisons between the different modeling philosophies. We also propose a modeling approach based on imprecise probabilities that is new to the optimization field, and is quite general. Its main advantage is that it makes realistic assumptions on the stochasticity of the problem data, and may cope with real data limitations such as poorly known or unknown dependencies, small sample sizes, inconsistencies in the quality of input data, non-constant distributions. Moreover, some common modeling approaches (such as stochastic routing problems or routing with interval data) may be seen as particular cases of the one based on imprecise probabilities. The second goal of this project is the design of algorithms, particularly metaheuristics and local search algorithms, that can effectively deal with the uncertainty of the input data, and with the complex objective functions to be minimized. In the past years we developed several state-of-the-art algorithms for routing problems, and experienced with different ways of expressing (un)certainty in the data of the problem: deterministic, stochastic, dynamic, and with interval data. The encouraging results we obtained, especially with the application of metaheuristics, suggest us to deepen our investigations on some aspects, such as the use of different objective function approximations and their impact on the solution quality and convergence speed of the algorithms. A particular care will be taken in performing fair comparisons among metaheuristics and other techniques based on mathematical programming and exact methods.