Title: Selecting the robust constrained shortest path under uncertainty

Authors: Sadjad Moradi; Nemat Allah Taghi-Nezhad

Addresses: Department of Mathematics, Faculty of Basic Sciences, Sahand University of Technology, Tabriz, Iran ' Department of Mathematics, Faculty of Basic Sciences and Engineering, Gonbad Kavous University, Gonbad, Iran

Abstract: This article deals with the problem of finding a constrained shortest path on a network in which, each arc is introduced by two factors, length and time. Distance parameter is minimised and travel time is limited. Since travel time on a path depends on many factors that are constantly changing, time parameter is considered as a random variable and we assume that it is limited in specified interval. Considering the uncertainty budget, the problem is firstly modelled in the form of a Γ-robust model and then an efficient optimal method is presented to solve the problem for different levels of conservatism so that we can choose the best level of conservatism by comparing the results. The results of the implementation of the solution algorithm on different networks show that it is possible to obtain a reliable route, in which the probability of violation of travel time constraint decreases by increasing the conservatism level. However, as the level of conservatism increases, the length of the optimal robust path increases.

Keywords: shortest path problem; robust path; uncertainty budget; conservatism level.

DOI: 10.1504/IJISE.2022.122867

International Journal of Industrial and Systems Engineering, 2022 Vol.40 No.4, pp.533 - 550

Received: 25 Dec 2019
Accepted: 04 Jun 2020
Published online: 13 May 2022 *

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