💻 computer science

A New Meta-Heuristic for Improving General Multi-Start Procedures, With an Application to the Planar p-Median Location Problem

This paper proposes a general, low-cost post-optimization meta-heuristic that enhances multi-start algorithms by iteratively generating and improving offspring from an elite set of solutions, successfully improving the best-known results for all 48 tested planar p-median instances within comparable run times.

Original authors: Zvi Drezner, Jack Brimberg

Published 2026-07-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zvi Drezner, Jack Brimberg

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the absolute best spot to build five new pizza shops in a giant, flat city. You want to minimize the total distance everyone has to walk to get their slice. This is the Planar p-Median Problem. It sounds simple, but the city is a maze of traps. If you just pick a spot and walk around looking for a better one, you might get stuck on a small hill thinking it's the highest peak, when a massive mountain is just over the next ridge. In math-speak, these hills are called "local optima," and for this problem, there could be millions of them.

For decades, researchers have used a strategy called Multi-Start. Think of this as hiring 800,000 different scouts (or starting 800,000 separate pizza delivery routes) to run around the city from random spots. Each scout runs until they get stuck on a local hill, and then you pick the best result from all of them. It works, but it's like throwing a million darts at a board and hoping one hits the bullseye.

The New Trick: The "Elite Squad" and the "Baby Steps"

The authors, Zvi Drezner and Jack Brimberg, propose a clever new meta-heuristic (a smart rule for finding solutions) called RPT (which stands for Repeated POST). They argue that instead of just keeping the single best result from your 800,000 scouts, you should keep a small "Elite Squad" of the top 5 best results you found.

Here is the magic part:

The Mix-and-Match: Take two different "Elite" solutions (two different sets of pizza shop locations). Imagine them as parents.
Creating Offspring: Draw a line through the city. Take the shops from Parent A that are on one side of the line, and the shops from Parent B that are on the other side. You've just created a brand new "child" solution—a hybrid map that combines the best parts of both parents.
The Polish: Run the standard improvement algorithm on this new child. Maybe it gets stuck on a new hill, but it might be a higher hill than before.
Repeat: If this new child is better than your current best, you keep it in the Elite Squad and try mixing it with others again. You keep doing this until you can't find any better "children."

The paper calls the initial mixing phase POST (a post-optimizing step). The full RPT strategy takes this a step further. Instead of running one giant batch of 800,000 scouts, it breaks the work into smaller batches. It runs the POST process on a smaller group, finds the best 5, mixes them, and then repeats this whole cycle many times (specifically, 700 times in their best tests).

What They Found (and What They Didn't)

The authors tested this on 48 different city maps (24 with evenly spread customers, 24 with clumpy, uneven clusters). They used two different "scout" algorithms: the classic ALT (Cooper's old-school method) and a newer, fancier one called CLUST.

The Result: In every single one of the 48 test cases, the RPT(CLUST) method found a better solution than the standard Multi-Start approach. (Note: The standard RPT(ALT) method improved results significantly but did not find new best-known solutions for all 48 instances; this specific achievement belongs to the RPT method when paired with the CLUST algorithm).
The Speed: Here is the kicker. The extra time it took to do this mixing and matching was almost nothing. For the 24 uniform instances, the average time to run the standard ALT method was about 257.68 minutes. The RPT method took about 257.45 minutes. They actually got better results in roughly the same amount of time.
The Improvement: For the standard ALT method, the solutions were on average about 0.80% worse than the best known results. RPT shaved that down to 0.53%. In some specific cases, the improvement was massive, cutting the error by over 60% or 70%.

When they used the newer, slower CLUST algorithm, the results were even more impressive. The standard CLUST method found solutions that were already very good, but RPT found new best-known solutions for all 24 uniform instances and all 24 non-uniform instances. In fact, for the uniform tests, the RPT method with a specific setting (I = 1,000) found the best known solution in 14 out of 24 cases on its own. If you combined the results from different settings (I=1,000 and I=10,000), the new best known solution was found in 21 out of 24 cases. For the non-uniform tests, the RPT method found the best known solution in 13 out of 24 cases on its own, and if you combined the results from different settings, it found the best known solution in all 24 cases.

What They Rule Out

The paper is very clear about what this method is not.

It is not a magic wand that guarantees the perfect global optimum every time. The authors explicitly state: "If the multi-start heuristic finds the optimal solution, then of course RPT cannot improve it." If you already found the absolute best possible answer, RPT can't make it better.
It is not a method that requires you to run the computer for days longer. They argue that the extra time is "negligible."
They also suggest that you don't need to obsess over finding the "perfect" parameters (like exactly how many scouts to use). They tested different group sizes (like 1,000 vs 10,000) and found they performed similarly, suggesting that "any selection of reasonable parameters will perform similarly well."

How Sure Are They?

The authors are very confident in their numbers because they ran actual simulations on a desktop computer with an Intel i7 processor. They didn't just guess; they measured the results.

They used statistical tests (paired t-tests) and found the improvements were statistically significant (with p-values as low as $6.7 \times 10^{-5}$ ).
They claim the method works for "general multi-start improvement algorithms," but they only demonstrated it on the Planar p-Median problem. They suggest it could work on other problems (like clustering), but they haven't proven it yet.

The Takeaway

Think of the old way of solving these problems as throwing a million darts and hoping one hits the bullseye. The new RPT method is like taking the five best darts you've thrown so far, cutting them in half, and gluing the best halves together to make a new, super-dart. Then you throw that new dart. If it hits better, you keep it and try again.

The paper suggests that this "mix-and-match" approach is a powerful, low-cost way to squeeze out better solutions from existing algorithms without needing to wait days for the computer to finish. It turns a "good enough" search into a "great" search, almost for free.

Technical Summary: A New Meta-Heuristic for Improving General Multi-Start Procedures

Problem Statement
The paper addresses the challenge of solving optimization problems characterized by a vast number of local optima, specifically the planar $p$ -median location problem. This problem involves locating $p$ facilities in a continuous plane to minimize the weighted sum of Euclidean distances to $n$ demand points. The objective function is non-convex, and for large instances (e.g., 10,000 demand points and 100 facilities), the solution space may contain millions of local minima. Standard multi-start heuristics, which execute an improvement algorithm from $N$ random starting solutions and return the single best local optimum found, often fail to locate the global optimum or even high-quality solutions within reasonable timeframes.

Methodology
The authors propose a new meta-heuristic framework called RPT (Repeated POST), which functions as a post-optimization layer for any general multi-start improvement algorithm. The framework consists of two main components:

The POST (Post-Optimization) Procedure:
- Instead of discarding all but the single best solution after a multi-start run, POST retains an "elite subset" of the $K$ best non-repeating solutions found (the authors use $K=5$ ).
- Offspring Generation: For every pair of solutions in this elite set, the algorithm generates "offspring." In the context of the planar $p$ -median, this is achieved by drawing a line through the center of gravity of the combined facility locations of the two parents. Facilities from one parent located on one side of the line are combined with facilities from the other parent on the opposite side.
- Local Search: The improvement algorithm is applied to each generated offspring.
- Iteration: If the best offspring improves upon the current best solution, the process repeats: a new elite set of size $K$ is selected from the offspring, and new offspring are generated. The process terminates when no further improvement is found.
The RPT (Repeated POST) Meta-Heuristic:
- To manage computational resources, RPT divides the total budget of $N$ starting solutions into $L$ smaller batches, each containing $I$ starting solutions (where $I \times L \approx N$ ).
- The POST procedure is executed $L$ times. Each execution starts with $I$ random solutions, identifies the best $K$ from that batch, and performs the offspring generation and improvement cycle.
- Finally, a single POST execution is performed on the best $K$ solutions found across all $L$ batches to ensure the final output is the global best found during the entire process.

Key Contributions

General Applicability: The paper presents a general post-optimizing procedure applicable to any multi-start heuristic, not limited to the specific problem tested.
Efficiency: The authors demonstrate that the additional computational effort required for the post-optimization phase is negligible compared to the initial multi-start phase. This is because the offspring are derived from high-quality solutions, requiring fewer iterations for the improvement algorithm to converge compared to random starts.
New Best Solutions: The methodology successfully identifies new best-known solutions for all 48 test instances of the planar $p$ -median problem (24 uniform and 24 non-uniform), outperforming previous state-of-the-art algorithms.

Experimental Results
The authors tested the RPT framework using two different improvement algorithms:

RPT(ALT): Using Cooper's classic ALT (Alternating Locate-Allocate) algorithm. With $N=800,000$ starting solutions, RPT reduced the average percentage deviation from the best-known solution by over 40% for uniform instances and over 30% for non-uniform instances, with virtually identical run times to the standard multi-start ALT.
RPT(CLUST): Using the newer, more powerful CLUST (Cluster) algorithm. Due to CLUST's higher computational cost, $N$ $N$ was reduced to 80,000. RPT(CLUST) improved the best-known solution for all 48 instances.
- For uniform instances, the average deviation from the best-known solution was reduced to 0.004% (RPT1 variant).
- For non-uniform instances, the average deviation was reduced to 0.010%.
- Statistical analysis (paired t-tests) confirmed that the improvements were statistically significant compared to the baseline multi-start approaches and other parameter settings.

Significance and Claims
The paper claims that the RPT meta-heuristic effectively implements a "Less is More" principle. By processing smaller batches of solutions ( $I \ll N$ ) and iteratively refining the elite subset through offspring generation, the algorithm explores the solution space more effectively than a single massive multi-start run, without increasing the total execution time.

The authors state that the method is easy to implement and requires only the retention of a small set of elite solutions during the multi-start phase. They conclude that RPT significantly enhances the performance of existing multi-start procedures for the planar $p$ -median problem and suggest that it holds promise for improving solutions in other models solved via multi-start heuristics. The paper does not claim to solve the NP-hard nature of the problem optimally but rather to find superior local optima that are closer to the global optimum than previously achieved.

The New Trick: The "Elite Squad" and the "Baby Steps"

What They Found (and What They Didn't)

What They Rule Out

How Sure Are They?

The Takeaway

More like this