Improved robust shortest paths by penalized investments

¹ Department of Computer Science, Pontificia Universidad Catolica de Chile Santiago, Chile
² Department of Industrial Engineering, Faculty of Engineering, Universidad de Talca, Curicó 3340000, Chile
³ MGN, Rio de Janeiro 20210-030, Brazil
⁴ Universidade Federal do Rio de Janeiro, COPPE & IM, Rio de Janeiro, Brazil.

^* Corresponding author: acandia@utalca.cl

Received: 4 September 2020
Accepted: 29 May 2021

Abstract

Connectivity after disasters has become a critical problem in the management of modern cities. This comes from the need of the decision-makers to ensure urgent medical attention by providing access to health facilities and to other relevant services needed by the population. Managing congestion could help maintain some routes operative even in complex scenarios such as natural disasters, terrorist attacks, protests, or riots. Recent advances in Humanitarian Logistics have handled this problem using different modeling approaches but have principally focused on the response phase. In this paper, firstly, we propose a penalized variant of an existing mathematical model for the robust s–t path problem with investments. With the aim of solving the robust several-to-one path problem with investments, and due to the high complexity of this new problem, a heuristic is proposed. Moreover, this approach allows us to improve travel times in both specific paths and in a set of routes in a systemic framework. The new problem and the proposed heuristic are illustrated by an example, which corresponds to a typical city network, that provides a concrete vision of the potential application of the framework. Lastly, some managerial insights are given by the analysis of results exhibited in the example network.