Journal
JOURNAL OF HEURISTICS
Volume 13, Issue 1, Pages 35-47Publisher
SPRINGER
DOI: 10.1007/s10732-006-9001-3
Keywords
distance measures; edit distance; permutation-type representations
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available