Biography
Dr. Yong Wang
Dr. Yong Wang
North China Electric Power University, China
Title: Two Probability Models for Traveling Salesman Problem Based on Frequency Quadrilaterals
Abstract: 

Traveling salesman problem (TSP) is one of well-known NP-hard problems in combinatorial optimization. Karp has shown that there is no polynomial-time algorithm for TSP unless P=NP. The recent research demonstrates that TSP on sparse graphs can be resolved in shorter time than TSP on complete graph. Here, we present two probability models based on frequency quadrilaterals, which give the basis to convert a TSP complete graph into the sparse graphs. As one chooses N frequency quadrilaterals to compute the frequency of an edge, the first probability model illustrates that the edges in the optimal Hamiltonian cycle usually have the bigger frequency than a common edge. Moreover, the frequency of an optimal Hamiltonian cycle edge increases according to n until it reaches the maximum frequency 5 as n is big enough, where n is the TSP scale. The average frequency of an edge conforms to the log-normal distribution. It implies that the number of edges with big frequency will be very small. Thus, in theory we can cut many edges with low frequency and a sparse graph with a small number of edges will be generated for TSP. We explored the observations with a few real-world TSP instances.

Biography: 

Yong Wang is an associate professor at the North China Electric Power University, Beijing. He obtained his Ph.D. degree on manufacturing engineering of aeronautics and astronautic at Beihang University, Beijing, China, the master degree on vehicle engineering at Beihang University, Beijing, China, and the bachelor degree on manufacturing engineering of aircraft at Nanjing University of Aeronautic and Astronautics, Nanjing, China. His research interests include Combinatorial Optimization, Decision theory, Graph algorithms, Applied probability and their applications in industrial engineering.