The multidimensional scaling (MDS) aims at finding coordinates for a set of n objects in a (low) q dimensional space that best fits dissimilarity information. To build a perception map to represent the relative positions of objects under study, the mapping dimension used is generally 2. The application area for MDS is mostly psychology and marketing. Unfortunately, the procedure is very sensitive to the parameters used and to the quality of the optimization performed. In this paper, we propose a reliable and flexible algorithm that allows the researcher to study the impact of the Minkowsky parameter (used to define distance measure between objects) on the results. The core of the algorithm is the use of the Variable Neighborhood Search (VNS) metaheuristic. The algorithm developed is tested with benchmark data (Morse code data). The choice of the best Minkowsly parameter is then discussed through the use of generated data and real data collected in an experiment where respondents had to rate pairs of national and private brands on the basis of their dissimilarities. The impact of distance measure on the quality of the perceptual maps is evaluated through the computation of Stress. Two perceptual maps are generated with different distance measures in order to examine their differences.