Advanced search
2 files | 1.68 MB

Speeding up Martins' algorithm for multiple objective shortest path problems

Sofie Demeyer (UGent) , Jan Goedgebeur (UGent) , Pieter Audenaert (UGent) , Mario Pickavet (UGent) and Piet Demeester (UGent)
Author
Organization
Abstract
The latest transportation systems require the best routes in a large network with respect to multiple objectives simultaneously to be calculated in a very short time. The label setting algorithm of Martins efficiently finds this set of Pareto optimal paths, but sometimes tends to be slow, especially for large networks such as transportation networks. In this article we investigate a number of speedup measures, resulting in new algorithms. It is shown that the calculation time to find the Pareto optimal set can be reduced considerably. Moreover, it is mathematically proven that these algorithms still produce the Pareto optimal set of paths.
Keywords
Stop condition, IBCN, Bidirectional routing, Pareto optimal set, Labeling algorithm, Multiobjective shortest path problem, RANKING

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 473.36 KB
  • 5937 i.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.20 MB

Citation

Please use this url to cite or link to this publication:

Chicago
Demeyer, Sofie, Jan Goedgebeur, Pieter Audenaert, Mario Pickavet, and Piet Demeester. 2013. “Speeding up Martins’ Algorithm for Multiple Objective Shortest Path Problems.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 11 (4): 323–348.
APA
Demeyer, S., Goedgebeur, J., Audenaert, P., Pickavet, M., & Demeester, P. (2013). Speeding up Martins’ algorithm for multiple objective shortest path problems. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 11(4), 323–348.
Vancouver
1.
Demeyer S, Goedgebeur J, Audenaert P, Pickavet M, Demeester P. Speeding up Martins’ algorithm for multiple objective shortest path problems. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH. 2013;11(4):323–48.
MLA
Demeyer, Sofie et al. “Speeding up Martins’ Algorithm for Multiple Objective Shortest Path Problems.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 11.4 (2013): 323–348. Print.
@article{4410352,
  abstract     = {The latest transportation systems require the best routes in a large network with respect to multiple objectives simultaneously to be calculated in a very short time. The label setting algorithm of Martins efficiently finds this set of Pareto optimal paths, but sometimes tends to be slow, especially for large networks such as transportation networks. In this article we investigate a number of speedup measures, resulting in new algorithms. It is shown that the calculation time to find the Pareto optimal set can be reduced considerably. Moreover, it is mathematically proven that these algorithms still produce the Pareto optimal set of paths.},
  author       = {Demeyer, Sofie and Goedgebeur, Jan and Audenaert, Pieter and Pickavet, Mario and Demeester, Piet},
  issn         = {1619-4500},
  journal      = {4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH},
  keywords     = {Stop condition,IBCN,Bidirectional routing,Pareto optimal set,Labeling algorithm,Multiobjective shortest path problem,RANKING},
  language     = {eng},
  number       = {4},
  pages        = {323--348},
  title        = {Speeding up Martins' algorithm for multiple objective shortest path problems},
  url          = {http://dx.doi.org/10.1007/s10288-013-0232-5},
  volume       = {11},
  year         = {2013},
}

Altmetric
View in Altmetric
Web of Science
Times cited: