×

A low complexity method for the optimization of network path length in spatially embedded networks. (English) Zbl 1311.90016

Summary: The average path length of a network is an important index reflecting the network transmission efficiency. In this paper, we propose a new method of decreasing the average path length by adding edges. A new indicator is presented, incorporating traffic flow demand, to assess the decrease in the average path length when a new edge is added during the optimization process. With the help of the indicator, edges are selected and added into the network one by one. The new method has a relatively small time computational complexity in comparison with some traditional methods. In numerical simulations, the new method is applied to some synthetic spatially embedded networks. The result shows that the method can perform competitively in decreasing the average path length. Then, as an example of an application of this new method, it is applied to the road network of Hangzhou, China.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI