A new general purpose line probe routing algorithm

Although there are many sophisticated routing techniques to achieve the routing goal, old general purpose routing algorithms are still being used inside the routing process. This paper presents a new general purpose line probe routing algorithm. Our algorithm was compared to an implementation based on the Hetzel interval labeling technique. It aims to exploit frequent routing cases where Hetzel algorithm suffers high performance losses. The experiments show that the proposed algorithm is very fast, presenting a runtime hundreds of times lesser than the Hetzel algorithm, while being sub-optimal.