  Bi-objective search is a well-known algorithmic problem, concerned with
finding a set of optimal solutions in a two-dimensional domain. This problem
has a wide variety of applications such as planning in transport systems or
optimal control in energy systems. Recently, bi-objective A*-based search
(BOA*) has shown state-of-the-art performance in large networks. This paper
develops a bi-directional and parallel variant of BOA*, enriched with several
speed-up heuristics. Our experimental results on 1,000 benchmark cases show
that our bi-directional A* algorithm for bi-objective search (BOBA*) can
optimally solve all of the benchmark cases within the time limit, outperforming
the state of the art BOA*, bi-objective Dijkstra and bi-directional
bi-objective Dijkstra by an average runtime improvement of a factor of five
over all of the benchmark instances.
