×

Triangle inequality in routing problems. (English) Zbl 0748.90014

Summary: A node routing problem generally has the objective of minimizing the total distance travelled by routing the vehicles through the various nodes. In order to obtain the absolute minimum solution for any routing problem, reduction of the distance matrix to satisfy the triangle inequality is necessary before any routing algorithm is applied. This problem of reduction can also be viewed as the problem of finding the shortest paths in directed, weighted graphs or networks. A brief survey of existing algorithms and an algorithm based on a new labelling procedure is presented in this paper. Use of the proposed algorithm is demonstrated with the help of a simple 6 node example.

MSC:

90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite