Neighborhood-based dynamic quantitative evaluation of solution for COP and its application in TSP/VRP

From the viewpoint of real engineering applications, the general Combinatorial Optimization Problem (COP) is studied with fuzzy set theory. Since the known cost information between the elements of COP is normalized into the real number [0,1], the concept of neighborhood degree is guided to measure the scale from the nearest (smallest cost) to the farthest (biggest cost) with fuzzy evaluation. The Total Neighborhood Measure (TNM) is proposed for estimating the quality of the incumbent solution in dynamic exploring process, and the Partial Neighborhood Measure (PNM) is also proposed, where the inferior portion of the solution can be detected and improved in the next heuristics operation. The properties and main role of the whole neighborhood measure are shown by the TSP (Traveling Salesman Problem) experiments, which the various tour data (benchmark, random and fractal type) are used and the scales are adjustable at 30-5000. Another experiment with vehicle dispatch and delivery problem is also down, where the poor tour (for vehicles) is detectable by the TNM and the poor trip (sub-tour for delivery job) can be caught through PNM. The algorithm using above strategy can avoid unnecessary parameter setting and press the useless and duplicate operation down. It is confirmed that the whole computational process is 15-30% faster than usual evolutionary method.