Titulo Estágio
Algorithms for the multiobjective shortest path problem with constraints
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ECOS/CISUC
Enquadramento
Multiobjective shortest path problems arise in many applications; for instance, GPS systems allow to choose different objectives such as time or cost. In general, there is no shortest path that optimizes all objectives simultaneously since the fastest path may not be the cheapest; just consider highways. Hence, one has to develop algorithms that output a set of “efficient” shortest paths, from which the user chooses the most preferable. Since the number of efficient shortest paths may be too large, one may want to consider only those that do not exceed a given value for each objective function.
Objetivo
The goal of this MSc project is to design, analyse and implement exact algorithms for the multiobjective shortest path problems, considering a constraint that bounds the maximum value for each objective. The student should implement the algorithm, in the most efficient way, and perform a sound experimental analysis. Special care should be taken on the data structures chosen. The final implementation should be publicly available in some git repository. Some algorithms are available for the multiobjective (unconstrained) shortest path problem [1,2,3,4], which can be adapted for the constrained case. Particular dynamic programming techniques that were applied to biobjective knapsack problems should also be considered [5,6].
Plano de Trabalhos - Semestre 1
- Literature review on multiobjective optimization and shortest path algorithms
- Implementation of algorithms for the multiobjective (unconstrained) shortest path problem
- Design of the algorithm for the constrained case
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Implementation of the algorithm for the multiobjective constrained shortest path problem
- Analysis of the algorithm on a benchmark set of instances
- Writing of the final report
Condições
This MSc project arises within an existent collaboration with Prof. Daniel Vanderpooten, from Paris-Dauphine University, and Prof. José R. Figueira, from IST, University of Lisbon. It is targeted for students that would like to deepen their knowledge on algorithms, data structures and efficient implementations. Therefore, the student should have an excellent grade on these topics at BSc and MSc level. The student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
[1] E. Martins, On a multicriteria shortest path problem, European Journal of Operation Research, 16 (1984), pp. 236-237
[2] S. Skriver, K. Andersen, A label correcting approach for solving bicriterion shortest-path problems, Computers & Operations Research, 27 (2000), pp. 507-524
[3] J. Brumbaugh-Smith, D. Shier, An empirical investigation of some bicriterion shortest path algorithms, European Journal of Operational Research, 43 (1989), pp. 216-224
[4] Andrea Raith, Matthias Ehrgott, A comparison of solution strategies for biobjective shortest path problems. Computers & OR 36(4): 1299-1331 (2009)
[5] J.R.Figueira, L.Paquete, M.Simões, D.Vanderpooten, Algorithmic improvements on dynamic programming for the bi-objective {0,1} knapsack problem, Computational Optimization and Applications, 56(1):97-111, 2013.
[6] L.Paquete, M.Jaschob, K.Klamroth, J.Gorski, On a biobjective search problem in a line: formulations and algorithms, Theoretical Computer Science, 507: 61-71, 2013.
Orientador
Luís Paquete
paquete@dei.uc.pt 📩