Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 1729-1739 |
Number of pages | 11 |
Journal | Journal of Electronic Measurement and Instrument |
Volume | 2 |
Publication status | Published - 2004 |
Externally published | Yes |
Event | Conference Proceedings of the Sixth International Conference on Electronic Measurement and Instruments - Taiyuan, China Duration: 18 Aug 2003 → 21 Aug 2003 |
Keywords
- Combinatorial Optimization Problem (COP)
- Neighborhood
- Traveling Salesman Problem (TSP)
- Vehicle Routing Problem (VRP)