An exact method for the biobjective shortest path problem for large-scale road networks

• DOI: 10.1016/j.ejor.2014.11.003
• Publication Date: 2014-11-06T19:37:19Z
• Authors: Daniel Duque; Leonardo Lozano; Andrés L. Medaglia
• Keywords: Enumeration

Abstract The Biobjective Shortest Path Problem (BSP) is the problem of finding (one-to-one) paths from a start node to an end node, while simultaneously minimizing two (conflicting) objective functions. We present an exact recursive method based on implicit enumeration that aggressively prunes dominated solutions. Our approach compares favorably against a top-performer algorithm on two large testbeds from the literature and efficiently solves the BSP on large-scale networks with up to 1.2 million nodes and 2.8 million arcs. Additionally, we describe how the algorithm can be extended to handle more than two objectives and prove the concept on networks with up to 10 objectives.