Less is more approach: basic variable neighborhood search for the obnoxious p‐median problem

• Author: Nenad Mladenović,Jun Pei,Panos M. Pardalos,Raca Todosijević,Abdulaziz Alkandari
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12646
• Date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 480–493

DOI: 10.1111/itor.12646

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Less is more approach: basic variable neighborhood search

for the obnoxious p-median problem

Nenad Mladenovi´

ca,b, Abdulaziz Alkandaric,JunPei

d,e, Raca Todosijevi´

cf,g and

Panos M. Pardalosh

aEmirates College of Technology, Abu Dhabi, United Arab Emirates

bUral Federal University, Yekaterinburg, Russia

cCollege of TechnologicalStudies, Public Authority for Applied Education and Training, Kuwait City, Kuwait

dSchool of Management, Hefei University of Technology,Anhui Sheng, China

eKey Laboratory of ProcessOptimization and Intelligent Decision-Making, Ministry of Education, Hefei, China

fLAMIH UMR CNRS 8201, Universit´

e Polytechnique Hauts-de-France,59313 Valenciennes Cedex 9, Famars, France

gMathematical Institute of the Serbian Academy of Science and Arts, Kneza Mihaila 36, 11000 Belgrade, Serbia

hDepartment of Industrial and Systems Engineering, Faculty of Engineering, University of Florida, Gainesville, FL

32611-6595, USA

E-mail: nenadmladenovic12@gmail.com [Mladenovi´

c]; abdl_alkandari@hotmail.com [Alkandari];

feiyijun198612@126.com [Pei];racatodosijevic@gmail.com [Todosijevi´

c]; pardalos@ufl.edu [Pardalos]

Received 21 December 2017; receivedin revised form 10 February 2019; accepted 11 February 2019

Abstract

The goal of the less is more approach (LIMA) for solving optimization problems that has recently been

proposed in Mladenovi´

c et al. (2016) is to find the minimum number of search ingredients that make a

heuristic more efficient than the currently best. In this paper, LIMA is successfully applied to solve the

obnoxious p-median problem (OpMP). More precisely, we developed a basic variable neighborhood search

for solving the OpMP, where the single search ingredient, the interchange neighborhood structure,is used. We

also propose a new simple local search strategy for solving facility location problems, within the interchange

neighborhood structure, whichis in between the usual ones: first improvement and best improvementstrategies.

We call it facility best improvement local search. On the basis of experiments, it appeared to be more efficient

and effective than both first and best improvement. According to the results obtained on the benchmark

instances, our heuristic turns out to be highly competitive with the existing ones, establishing new state-of-

the-art results. For example, four new best-known solutions and 133 ties are claimed in testing the set with

144 instances.

Keywords:heuristic; less is more; obnoxious location; heap data structure; facility best improvement

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.