Development of evolutionary algorithms for determining the k most vital arcs in shortest path problem

Development of evolutionary algorithms for determining the k most vital arcs in shortest path problem

0.00 Avg rating0 Votes
Article ID: iaor20021377
Country: South Korea
Volume: 26
Issue: 2
Start Page Number: 47
End Page Number: 58
Publication Date: Jun 2001
Journal: Journal of the Korean ORMS Society
Authors: ,
Keywords: programming: network
Abstract:

The purpose of this study is to present methods for determining the k most vital arcs (k-MVAs) in shortest path problem (SPP) using evolutionary algorithms. The problem of finding the k-MVAs in SPP is to find a set of k arcs whose simultaneous removal from the network causes the greatest increase in the shortest distance between two specified nodes. Generally, the problem of determining the k-MVAs in SPP has been known as NP-hard. Therefore, to deal with problems of the real world, heuristic algorithms are needed. In this study we present three kinds of evolutionary algorithms for finding the k-MVAs in SPP, and then to evaluate the performance of proposed algorithms.

Reviews

Required fields are marked *. Your email address will not be published.