Страница публикации

An effective heuristic for large-scale fault-tolerant k-median problem

Авторы: Vasilyev I., Ushakov A.V., Maltugueva N., Sforza A.

Журнал: Soft Computing

Том: 23

Номер: 9

Год: 2019

Отчётный год: 2018

Издательство:

Местоположение издательства:

URL:

Аннотация: We address a general fault-tolerant version of the k-median problem on a network. Unlike the original k-median, the objective is to find k nodes (medians or facilities) of a network, assign each non-median node (customer) to rj distinct medians, and each median nodes to rj- 1 other medians so as to minimize the overall assignment cost. The problem can be considered in context of the so-called reliable facility location, where facilities once located may be subject to failures. Hedging against possible disruptions, each customer is assigned to multiple distinct facilities. We propose a fast and effective heuristic rested upon consecutive searching for lower and upper bounds for the optimal value. The procedure for finding lower bounds is based on a Lagrangian relaxation and a specialized effective subgradient algorithm for solving the corresponding dual problem. The information on dual variables is then used by a core heuristic in order to determine a set of primal variables to be fixed. The effectiveness and efficiency of our approach are demonstrated in a computational experiment on large-scale problem instances taken from TSPLIB. We show that the proposed algorithm is able to fast find near-optimal solutions to problem instances with almost 625 million decision variables (on networks with up to 24978 vertices).

Индексируется WOS: 1

Индексируется Scopus: 1

Индексируется РИНЦ: 0

Публикация в печати: 1

Добавил в систему: