THE COMBINATION OF MAX-MIN ANT SYSTEM AND ITERATED LOCAL SEARCH HEURISTIC FOR CAPACITATED P-MEDIAN PROBLEM
Rapeepan Pitakaso, Sombat Sindhuchao
>> Download ebook <<
We present the Max-Min ant system (MMAS) based heuristic to solve the capacitated p-medians problems (CPMP). We use the MMAS to select the p-locations that are going to be opened as the medians out of m customers. The remaining (m-p) customers will be assigned to be served by the pre-selected p medians. The customers will be assigned to the closest median if that median still has enough capacity while other heuristics use the location to decide which sets of customers are closest to them and decide to serve these customers until the its capacity is full. Two phases of local search have been applied. The first phase is to change a client into a median and this median into a client seeking an improvement of the objective function (by the first improvement rule). The second phase of local search is to change the client(s) between two medians. Each ant selects p-medians and the local search is applied, then the best ant, in each iteration, is selected to apply the iterated local search (ILS). ILS consists of two phases, local search and perturbation. The result shows that when MMAS works with ILS, the solution quality is significantly improved. The best ant will be iteratively perturbing and the local search is applied (two phases local search) until a predefined number of iterations is reached then the ILS phase ends. The algorithm that we proposed here, an algorithm which combines the MMAS and ILS, outperforms the best existing heuristics published so far.
