Abstract:
We consider the biobjective shortest path (BSP) problem as the natural extension
of the single objective shortest path problem. BSP problems arise in various
applications where networks usually consist of large numbers of nodes and arcs.
Since obtaining the set of efficient solutions to a BSP problem is more difficult
(i.e. NP-hard and intractable) than solving the corresponding single objective
problem there is a need for fast solution techniques. Our aim is to compare
different strategies for solving the BSP problem. We consider a standard label
correcting method, a purely enumerative near shortest path approach, and the
two phase method, investigating different approaches to solving problems arising
in phase 1 and phase 2. In particular, we propose to combine the two phase
method with ranking in phase 2. In order to compare the different approaches,
we investigate their performance on three different types of networks. We employ
grid networks and random networks, as is generally done in the literature.
Furthermore, road networks are utilized to compare performance on networks
with a structure that is more likely to actually arise in applications.