A dynamic programming heuristic for the P-median problem

✍ Scribed by Michelle Hribar; Mark S. Daskin

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 682 KB
• Volume: 101
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(96)00218-4

✦ Synopsis

A new heuristic algorithm is proposed for the P-median problem. The heuristic restricts the size of the state space of a dynamic programming algorithm. The approach may be viewed as an extension of the myopic or greedy adding algorithm for the P-median model. The approach allows planners to identify a large number of solutions all of which perform well with respect to the P-median objective of minimizing the demand weighted average distance between customer locations and the nearest of the P selected facilities. In addition, the results indicate regions in which it is desirable to locate facilities. Computational results from three test problems are discussed. 9 1997 Elsevier Science B.V.