Solving the bi‐objective capacitated p‐median problem with multilevel capacities using compromise programming and VNS

• Author: Martino Luis,Chandra Ade Irawan,Arif Imran
• Published date: 01 January 2020
• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12485

Intl. Trans. in Op. Res. 27 (2020) 361–380

DOI: 10.1111/itor.12485

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Solving the bi-objective capacitated p-median problem with

multilevel capacities using compromise programming and VNS

Chandra Ade Irawana, Arif Imranband Martino Luisc

aNottingham University Business School China, Universityof Nottingham Ningbo China, Ningbo, China

bDepartment of Industrial Engineering, Institut TeknologiNasional, Bandung 40124, Indonesia

cOthman Yeop Abdullah GraduateSchool of Business, Universiti Utara Malaysia, Sintok, Malaysia

E-mail: chandra.irawan@nottingham.edu.cn[Irawan]; arifimr@yahoo.com [Imran]; martino@uum.edu.my [Luis]

Received 5 February2017; received in revised form 10 October 2017; accepted 17 October 2017

Abstract

A bi-objective optimisation using a compromise programming (CP) approach is proposedfor the capacitated

p-median problem (CPMP) in the presence of the fixed cost of opening facility and severalpossible capacities

that can be used by potential facilities. As the sum of distances between customers and their facilities

and the total fixed cost for opening facilities are important aspects, the model is proposed to deal with those

conflicting objectives.We develop a mathematicalmodel using integer linear programming (ILP) to determine

the optimal location of open facilities with their optimal capacity. Two approaches are designed to deal with

the bi-objective CPMP, namely CP with an exact method and with a variable neighbourhood search (VNS)

based matheuristic. New sets of generated instances are used to evaluate the performance of the proposed

approaches. The computational experiments show that the proposed approaches produce interesting results.

Keywords:capacitated p-median problem; bi-objective; compromise programming; VNS

1. Introduction

The aim of the p-median problem (PMP) is to seek the location of pfacilities among mdiscrete

potential sites in such a way as to minimise the sum of the distances between customers and their

associated facilities.The PMP was originally formulated by ReVelle and Swain (1970). This problem

is also known as the minisum location problemwhich is categorised as NP-hard (Kariv and Hakimi,

1979). In the capacitated version of the p-median problem (CPMP), each customer has a fixed de-

mand where each potential facility has a known capacity. Each facility must serve the demand of its

customers without violating its capacity. This capacity constraint significantly multiplies the com-

plexity of the problem. Therefore, CPMP falls into NP-hard problems (Garey and Johnson, 1979).

In many real case applications, when finding the best location for the facilities, the fixed cost

for opening facilities is usually taken into account. The fixed cost of a potential facility may be

C

2017 The Authors.

International Transactionsin Operational Research C

2017 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.

362 C. A. Irawan et al. / Intl. Trans. in Op. Res.27 (2020) 361–380

dependent on its location and its capacity. One possible decision that has to be made isto deter mine

the optimal location of open facilities and their corresponding capacity in order to minimise the

sum of distances between facilities and their associated customers. As there is always a limited

budget available, the decision makers should consider the total fixed cost for opening facilities.

In the literature these two objectives are usually combined though both objectives may appear

conflicting. When unlimited budget is available, the open facilities will use a large capacity to ensure

that customers will be served by their nearest facilities. In this case, the problem may be considered

as the uncapacitated PMP.

In this paper, we investigate the capacitated PMP in the presence of two conflicting objectives. To

the best of our knowledge, there is no paper in the literature studying such a problem.

The main contributions of this paper are as follows:

rto develop a new mathematical model for the bi-objective capacitated PMP using compromise

programming (CP) method, and

rto propose an effective variable neighbourhood search (VNS) to solve the bi-objective CPMP.

The paper is organised as follows. Section 2 provides a brief review of the past efforts at the

capacitated PMP. In Section 3, mathematical models for the classical CPMP along with the

new bi-objective CPMP are presented. A description of CP method for solving the bi-objective

CPMP is given in Section 4. The proposed VNS to solve the problem is described in Section 5.

Section 6 presents computational results using the generated dataset. A summary of our findings

and some avenues for future research are also provided in the last section.

2. Literat ure review

The earliest works on the CPMP were done by Mulvey and Beck (1984) who designed two algo-

rithms to tackle capacitated clustering problems and Pirkul (1987) who used the Lagrangian relax-

ation technique to solve communication network deployment problems. Osman and Christofides

(1994) integrated simulated annealing and tabu search to deal with the CPMP. Maniezzo et al.

(1998) studied the CPMP by proposing a bionomic algorithm and an effective local search. Bal-

dacci et al. (2002) dealt with the CPMP using a set partitioning formulation technique. The pro-

posed technique was tested on benchmark instances from the literature and also on new sets of

instances which the authors generated by considering bounds on the cluster cardinality and in-

compatibilities between entities. Lorena and Senne (2004) applied a column-generation method to

solve the CPMP by incorporating the Lagrangean/surrogate relaxation to determine new bounds

and new productive columns through a modified knapsack subproblem. Ahmadi and Osman

(2005) integrated the Greedy Random Adaptive Search Procedure and the Adaptive Memory

Programming (AMP) to create a greedy random adaptive memory search method in tackling the

CPMP.

Scheuerer and Wendolsky (2006) addressed the CPMP by proposing a scatter search heuristic.

Several new best found solutions were obtained when the proposed scatter search heuristic was

tested on benchmark instances from the literature. D´

ıaz and Fern´

andez (2006) hybridised a scatter

search and path relinking algorithm for solving the CPMP. Fleszar and Hindi (2008) designed an

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies