A revised Variable Neighborhood Search for the Discrete Ordered Median Problem

Paweł Olender and Wlodzimierz Ogryczak ()

European Journal of Operational Research, 2019, vol. 274, issue 2, 445-465

Abstract: The paper presents a revised Variable Neighborhood Search (VNS) heuristic method for the Discrete Ordered Median Problem (DOMP). This method introduces a regularization concept that intensifies the searching process for problems with a not strictly monotonic objective function. This allows better quality solutions to be reached, and is especially helpful for the n-center problem. At the same time, the redesigned interchange algorithm is used to boost the computational performance. This serves as the local search and limits the searching process in non-promising directions. It determines new solutions gradually, rejecting those that cannot be better than the current one. In addition, less calculation is required to determine and evaluate new solutions, due to exploiting information from the current solution. Instead of sorting the whole cost vector at each objective function evaluation, the method sorts only the cost components that are actually changing, and updates the ordered cost vector of the current solution. To evaluate the performance, the proposed method is compared with the original VNS for DOMP, along with other existing methods for DOMP from the literature. Exhaustive computational experiments were carried out, utilizing a widely-used set of problem instances from OR-library. The comparison shows that the proposed revised VNS outperforms the other methods, both in computing time and in solution quality.

Keywords: Combinatorial optimization; Discrete Ordered Median Problem; Variable Neighborhood Search; Discrete location; Ordered weighted averaging (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718308610
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:274:y:2019:i:2:p:445-465

DOI: 10.1016/j.ejor.2018.10.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().