TY - JOUR

T1 - A comparison of solution strategies for biobjective shortest path problems

AU - Raith, Andrea

AU - Ehrgott, Matthias

PY - 2009/4

Y1 - 2009/4

N2 - 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 and label setting method, a purely enumerative near shortest path approach, and the two phase method, investigating different approaches to solving problems arising in phases 1 and 2. In particular, we investigate 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.

AB - 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 and label setting method, a purely enumerative near shortest path approach, and the two phase method, investigating different approaches to solving problems arising in phases 1 and 2. In particular, we investigate 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.

KW - Biobjective shortest path problem

KW - Two phase method

KW - Label correcting algorithm

KW - Label setting algorithm

KW - Near shortest path algorithm

U2 - 10.1016/j.cor.2008.02.002

DO - 10.1016/j.cor.2008.02.002

M3 - Journal article

VL - 36

SP - 1299

EP - 1331

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 4

ER -