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.

A graph clustering based decomposition approach for large scale p-median problems / Masone, Adriano; Sforza, Antonio; Sterle, Claudio; Vasilyev, Igor. - In: INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE. - ISSN 0974-0635. - 16:1(2018), pp. 116-129.

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

Masone, Adriano;Sforza, Antonio;Sterle, Claudio;
2018

Abstract

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.
2018
A graph clustering based decomposition approach for large scale p-median problems / Masone, Adriano; Sforza, Antonio; Sterle, Claudio; Vasilyev, Igor. - In: INTERNATIONAL JOURNAL OF ARTIFICIAL INTELLIGENCE. - ISSN 0974-0635. - 16:1(2018), pp. 116-129.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/700354
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact