CQUniversity
Browse

File(s) not publicly available

An efficient modified greedy algorithm for the p-median problem

conference contribution
posted on 2017-12-06, 00:00 authored by Michael DzatorMichael Dzator, J Dzator
The fundamental objectives of locating facilities can be summarized into three categories. The first category refers to those designed to cover demand within a specified time or distance. This objective gives rise to location problems which are known as the Location Set Covering Problem (LSCP) and the Maximal Covering Location Problem (MCLP). The LSCP seeks to locate the minimum number of facilities required to ‘cover’ all demand or population in an area. The MCLP is to locate a predetermined number of facilities to maximize the demand or population that is covered. The second category refers to those designed to minimize maximum distance. This results in a location problem known as the p-center problem which addresses the difficulty of minimizing the maximum distance that a demand or population is from its closet facility given that p facilities are to be located. The third category refers to those designed to minimize the average weighted distance or time. This objective leads to a location problem known as the p-median problem. The p-median problem finds the location of p facilities to minimize the demand weighted average or total distance between demand or population and their closest facility. The p-median problemis a typical combinatorial optimization problem with many practical applications such as location of warehouses, schools, health centers, shops etc. Greedy algorithms are the simplest algorithms to design however it is not easy to understand its capability and limitations. A greedy algorithm solves a global optimization problem by making a sequence of locally optimal decisions. That is a greedy algorithm always chooses the next step of an algorithm that is locally optimal. For example for Facility Location Problem we will consider the facilities for which decisionsr egarding locally optimal locations will be made. The decisions that are made regarding where to locate successive facilities by a greedy method are permanent. That is the greedy algorithms make permanent decisions about the construction of a solution, based on the restricted consideration such as choosing alocation that gives a minimum cost. Greedy algorithms for facility location problems are constructive in principle. They are designed to give solutions of fairly good quality without using much time that is needed to compute better quality solutions by other algorithms. The most natural and simple heuristic for the p-median problem is the greedy algorithm. For the p-median problem to locate facilities, this algorithm picks amost ‘cost-effective’ facility until every required number of facilities p is located. We propose a modified form of the myopic (greedy) algorithm for the p-median problem. The new algorithmis simple and it gives relatively quality solutions. We demonstrated the importance of the removal of extreme values from a distance matrix before locating the first facility. The modification of the algorithm involves the removal of the extreme or large values from each column of the distance matrix. We then determine the first facility (1-median) after the removal of the extreme values. We revert to the original distance matrix after the first facility (1-median) is located. We then determine the additional facilities using the original distance matrix. We compare the results obtained by the original Myopic algorithm with the modified version using the 400 random problems. The results demonstrate the efficiency and superiority of our new method.

History

Start Page

1855

End Page

1861

Number of Pages

7

Start Date

2015-01-01

Finish Date

2015-01-01

ISBN-13

9780987214355

Location

Gold Coast, Australia

Publisher

The Modelling and Simulation Society of Australia and New Zealand

Place of Publication

Brisbane, Qld.

Peer Reviewed

  • Yes

Open Access

  • No

Era Eligible

  • Yes

Name of Conference

International Congress on Modelling and Simulation

Usage metrics

    CQUniversity

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC