 |
2-5 Jun 2019 Seville (Spain)
|
|
|
|
Scientific Program > Tutorials
Tuesday, June 5, 9:00 - 9:45 (Room 1&2)
Speaker: JESÚS SÁNCHEZ-ORO CALVO
Chairman: Ana D. López-Sánchez
Implementing efficient code without dying in the effort
We all agree that the success of a research work relies on the quality of the proposed algorithm. However, many times we are so focused on the algorithmic part of our work that we forget the relevance of implementing an efficient code to solve the problem. Indeed, a bad implementation of an effective algorithm may result in a disaster, since it will not be able to outperform previous works in reasonable computing time. Therefore, it is important to dedicate an important part of the research to select the correct data structures for solution representation, for instance.
In this tutorial we will start from a direct and inefficient solution for a well-known routing problem, and we will see some tips and tricks to increase the performance of the algorithm. We will analyze the complexity of the operations performed over the selected data structures in order to reduce the time complexity of the most used operations. Finally, once we have achieved an efficient version of the algorithm, we will focus on fast and simple parallelizations for the code, with the aim of taking advantage of the multiple processors available in every computer.
Tuesday, June 5, 9:00 - 9:45 (Room Antonio Machado)
Speaker: ROBERTO ROBERTI
Chairman: Alfredo G. Hernández-Díaz
Multi-Trip Vehicle Routing Problems: Variants, Formulations, and Exact Methods
Multi-Trip Vehicle Routing Problems (MTVRP) generalize the well-known VRP by allowing vehicles to perform multiple trips per day. MTVRPs have received much attention lately because of their relevance in a variety of real-life applications, in particular in city logistics and last-mile delivery. Several variants of the MTVRP have been investigated, and a number of exact algorithms have been proposed. The literature indicates that different MTVRPs can be solved with different formulations, but it seems that none of the available formulations dominates the others from a computational viewpoint. Moreover, the complexity of MTVRPs can make instances with just 25 customers challenging to solve to optimality even when resorting to dedicated mathematical formulations.
In this tutorial, we will give an overview of the MTVRP variants studied in the literature and outline the main formulations highlighting corresponding advantages and limitations, both from a theoretical and a computational viewpoint. After motivating the need for additional research on MTVRPs, we will describe a novel formulation featuring an exponential number of variables and constraints. We will also describe an exact solution framework, based on this new formulation, we have recently proposed in Paradiso et al, An Exact Solution Framework for Multi-Trip Vehicle Routing Problems with Time Windows (forthcoming in Operations Research). This solution framework allowed us to solve instances with up to 50 customers, outperforming the state-of-the-art methods for four variants of the MTVRP with Time Windows.
| Online user: 1 | RSS Feed |
|
