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

Fangyan Dong*, Kewei Chen, Kaoru Hirota

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

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 languageEnglish
Pages (from-to)1729-1739
Number of pages11
JournalJournal of Electronic Measurement and Instrument
Volume2
Publication statusPublished - 2004
Externally publishedYes
EventConference Proceedings of the Sixth International Conference on Electronic Measurement and Instruments - Taiyuan, China
Duration: 18 Aug 200321 Aug 2003

Keywords

  • Combinatorial Optimization Problem (COP)
  • Neighborhood
  • Traveling Salesman Problem (TSP)
  • Vehicle Routing Problem (VRP)

Fingerprint

Dive into the research topics of 'Neighborhood-based dynamic quantitative evaluation of solution for COP and its application in TSP/VRP'. Together they form a unique fingerprint.

Cite this