Title: Minimum-cost flow algorithms: a performance evaluation using the Brazilian road network

Authors: Carolina Luisa Dos Santos Vieira; Mônica Maria Mendes Luna; Jovane Medina Azevedo

Addresses: Departamento de Engenharia de Produção e Sistemas, Universidade Federal de Santa Catarina, Campus Reitor João David Ferreira Lima, s/n, Trindade, 88040-900 – Florianópolis – SC, Brazil ' Departamento de Engenharia de Produção e Sistemas, Universidade Federal de Santa Catarina, Campus Reitor João David Ferreira Lima, s/n, Trindade, 88040-900 – Florianópolis – SC, Brazil ' Centro de Ciências de Administração e Socioeconômicas (ESAG), Universidade do Estado de Santa Catarina, Av. Madre Benvenuta, 2007, Itacorubi, 88035-901 – Florianópolis – SC, Brazil

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.

Keywords: minimum-cost flow; experimental study; Brazilian road network; algorithms performance; network simplex.

DOI: 10.1504/WRITR.2019.097836

World Review of Intermodal Transportation Research, 2019 Vol.8 No.1, pp.3 - 21

Received: 28 Jun 2017
Accepted: 07 Feb 2018

Published online: 14 Feb 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article