The recent Variable Neighborhood Search (VNS) metaheuristic combines local
search with systematic changes of neighborhood in the descent and escape fr
om local optimum phases. When solving large instances of various problems,
its efficiency may be enhanced through decomposition. The resulting two lev
el VNS, called Variable Neighborhood Decomposition Search (VNDS), is presen
ted and illustrated on the p-median problem. Results on 1400, 3038 and 5934
node instances from the TSP library show VNDS improves notably upon VNS in
less computing time, and gives much better results than Fast Interchange (
FI), in the same time that FI takes for a single descent. Moreover, Reduced
VNS (RVNS), which does not use a descent phase, gives results similar to t
hose of FI in much less computing time.