Abstract
In this paper, we discuss distance measures for a number of different combinatorial optimization problems of which the solutions are best represented as permutations of items, sometimes composed of several permutation (sub)sets. The problems discussed include single-machine and multiple-machine scheduling problems, the traveling salesman problem, vehicle routing problems, and many others. Each of these problems requires a different distance measure that takes the specific properties of the representation into account. The distance measures discussed in this paper are based on a general distance measure for string comparison called the edit distance. We introduce several extensions to the simple edit distance, that can be used when a solution cannot be represented as a simple permutation, and develop algorithms to calculate them efficiently.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bierwirth, C. (1995). “A Generalized Permutation Approach to Job Shop Scheduling with Genetic Algorithms.” OR Spektrum 17, 87–92.
Caprara, A. (1977). “Sorting by Reversal is Difficult.” In Proceedings of the the First Annual International Conference on Computational Molecular Biology (RECOMB'97), ACM Press, New York, pp. 75–83.
Glover, F., M. Laguna, and R. Martí. (2000a). “Fundamentals of Scatter Search and Path Relinking.” Control and Cybernetics 39, 653–684.
Glover, F., A. Løkketangen, and D.L. Woodruff. (2000b). “Scatter Search to Generate Diverse MIP Solutions.” In M. Laguna and J.L.G. Velarde (eds.), Computing Tools for Modeling Optimization and Simulation, Kluwer, Boston, pp. 299–320.
Goldberg, D.E. and J. Richardson. (1987). “Genetic Algorithms with Sharing for Multimodal Function Optimization.” In Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Inc, Mahwah, NJ, pp. 41–49.
P. Greistorfer and S. Voß. (2005). “Controlled Pool Maintenance for Metaheuristics.” In C. Rego and B. Alidaee (eds.), Metaheuristic Optimization Via Memory and Evolution, Kluwer, Boston, pp. 387–424.
Janssens, G.K. (2004). “A Proposition for a Distance Measure in Neighbourhood Search for Scheduling Problems.” Journal of the Chinese Institute of Industrial Engineers 21, 262–271.
Kendall, M. and J. Dickinson Gibbons. (1990). Rank Correlation Methods. Oxford University Press, New York.
Levenshtein, V.I. (1966). “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals.” Soviet Physics-Doklady 10, 707–710.
Maes, M. (1990). “On a Cyclic String-to-String Correction Problem.” Information Processing Letters 35, 73–78.
Mahfoud, S.W. (1992). “Crowding and Preselection Revisited.” In R. Manner and B. Manderick (eds.), Parallel Problem Solving from Nature. Elsevier, Amsterdam, pp. 27–36.
Martí, R., M. Laguna, and V. Campos. (2005). “Scatter Search vs. Genetic Algorithms: An Experimental Evaluation with Permutation Problems.” In C. Rego and B. Alidaee (eds.), Metaheuristic Optimization Via Adaptive Memory and Evolution: Tabu Search and Scatter Search, Kluwer Academic Publishers, Boston, pp. 263–282.
Mauldin, M. (1984). “Maintaining Diversity in Genetic Search.” In Proceedings of the National Conference on Artificial Intelligence, pp. 247–250.
Ronald, S. (1998). “More Distance Functions for Order-Based Encodings.” In Proceedings of the IEEE Conference on Evolutionary Computation. IEEE Press, New York, pp. 558–563.
Siegel, S. and N.J. Castellan. (1988). Nonparametric Statistics for the Behavioral Sciences. McGraw-Hill, London.
Sörensen, K. and M. Sevaux. (2006). “MA❘PM: Memetic Algorithms with Population Management.” Computers and Operations Research 33, 1214–1225.
Ukkonen, E. (1985). “Finding Approximate Patterns in Strings.” Journal of Algorithms 6, 132–137.
Wagner, R.A. and M.J. Fischer. (1974). “The String-to-String Correction Problem.” Journal of the Association for Computing Machinery 21, 168–173.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sörensen, K. Distance measures based on the edit distance for permutation-type representations. J Heuristics 13, 35–47 (2007). https://doi.org/10.1007/s10732-006-9001-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-006-9001-3