Minimum-cost flow algorithms: a performance evaluation using the Brazilian road network Online publication date: Thu, 14-Feb-2019
by Carolina Luisa Dos Santos Vieira; Mônica Maria Mendes Luna; Jovane Medina Azevedo
World Review of Intermodal Transportation Research (WRITR), Vol. 8, No. 1, 2019
Abstract: In this paper, we evaluate the practical performance of four algorithms for solving the minimum-cost flow problem on road networks. While most computational testing has been based on artificially generated networks, for this study we used 215 real-world test instances, solved over the Brazilian road network. We verified that, differently from the literature, Network Simplex was the best performing algorithm in practice for this context, both in terms of speed and robustness. Features such as the number of supply and demand nodes influenced runtime, besides network topology and spatial syntax. On the other hand, the supplied volume and the ratio of supply/demand nodes were not good performance predictors. Our evaluation also showed that efficiency may be tied to algorithmic structure. The results should be particularly useful to support the choice of a MCF algorithm for evaluation of transportation networks, allowing reduction of cost for processing analyses of flow allocation.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the World Review of Intermodal Transportation Research (WRITR):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook