Solving the minimum route problem by means of a hybrid algorithm in presence of turn penalities

Two methods are normally used to solve the minimum route problem for transportation networks with turn penalties and prohibitions. The first method uses node expansion to represent turn penalties and prohibitions. Each node representing a street intersection, where turn penalties and prohibitions occur, is replaced by several nodes with virtual links connecting them. Using this method it is possible to solve the shortest path tree (S.P.T.) problem with a classic node-labelling algorithm. This solution presents many problems: the design of expanded network is a difficult and time-consuming process, the addition of virutal nodes and links can substantially increase the total dimension of the graph and the computational time, model results contain a large amount of information (on virtual links) not usually used. The second method does not require virtual links or nodes; in this case a link-labelling algorithm is utilized in order to solve the S.P.T. problem. This algorithm enormously increases the computational time where the turn penalties and prohibitions are significant. In this paper a new procedure is presented. The proposed ‘hybrid’ algorithm permits solution of the S.P.T. problem by coming to a mix between node-labelling and link labelling methods. The simultaneous labelling of nodes and links is the principoal characteristic of the ‘hybrid’ algorithm; the procedure assures low computational times and, at the same time, avoids the transportation network expansion. Performances of this ‘hybrid’ procedure have been compared with the existing methods on two real networks.