An Accelerated-Limit-Crossing-Based Multilevel Algorithm for the p-Median Problem.

Area of Science:

• Operations Research
• Combinatorial Optimization

Background:

• The p-median problem is a key facility location problem.
• Heuristic algorithms rely on identifying backbone (optimal) and fat (non-optimal) variables.
• Existing methods like limit crossing (LC) are computationally expensive and sensitive to upper bounds.

Purpose of the Study:

• To design an efficient heuristic algorithm for the p-median problem.
• To overcome limitations of existing methods for identifying backbone and fat variables.
• To develop a novel algorithm that integrates backbone/fat variable identification into heuristic design.

Main Methods:

• Development of the accelerated-LC (ALC) procedure, performing Lagrangian relaxation (LR) only once.
• Introduction of a dynamic pseudo upper bound mechanism to eliminate sensitivity.
• Integration of ALC and pseudo upper bounds into a multilevel algorithm (ALCMA).

Main Results:

• ALCMA determines backbone/fat variables in O(1) time after a single LR.
• The algorithm effectively reduces search spaces and eliminates upper bound sensitivity.
• ALCMA achieves superior average solution quality compared to existing heuristic algorithms.

Conclusions:

• ALCMA provides an efficient and robust method for heuristic design in p-median problems.
• The approach significantly improves upon the speed and accuracy of identifying structural variables.
• This work offers a practical advancement for solving large-scale p-median instances.