Premium
A defensive maximal covering problem on a network
Author(s) -
Berman O.,
Drezner T.,
Drezner Z.,
Wesolowsky G. O.
Publication year - 2009
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00660.x
Subject(s) - tabu search , mathematical optimization , simulated annealing , computer science , ranging , perspective (graphical) , operations research , mathematics , artificial intelligence , telecommunications
Consider a situation where p facilities need to be located by a leader, on the nodes of a network, to provide maximum coverage of demand generated at nodes of the network. At some point in the future it is expected that one of the links of the network will become unusable either due to a terrorist attack or a natural disaster (by the follower). The follower's objective is which link to remove. The leader's objective is to cover the most demand following such a damage to a link. The problem is formulated and analyzed from the leader's perspective. An efficient approach to solving the follower's problem is constructed. The leader's problem is solved heuristically by an ascent algorithm, simulated annealing, and tabu search, using the efficient algorithm for the solution of the follower's problem. Computational experiments on 40 test problems ranging between 100 and 900 nodes and 5–200 facilities provided good results.