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

A graph clustering based decomposition approach for large scale p-median problems

Авторы: Masone A., Sforza A., Sterle C., Vasilyev I.

Журнал: International Journal of Artificial Intelligence

Том: 16

Номер: 1

Год: 2018

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

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

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

URL:

Проекты:

DOI:

Аннотация: The p-median problem (PMP) is the well known network optimization problem of discrete location theory. In many real applications PMPs is defined on very large scale networks, for which ad-hoc exact and/or heuristic methods have to be developed. To this aim, in this work we propose a heuristic decomposition approach which exploits the decomposition of the network into disconnected components obtained by a graph clustering algorithm. Then, in each component several PMPs are solved for suitable ranges of p by a Lagrangian dual and simulated annealing based algorithm. The solution of the whole initial problem is obtained combining all the PMPs solutions through a multi-choice knapsack model. The proposed approach is tested using several graph clustering algorithms and compared with the results of the state-of-the-art heuristic methods.

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

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

Индексируется УБС: Нет

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

Индексируется ВАК: Нет

Индексируется CORE: Нет

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