The Multi-objective Shortest Path (MOSP) problem is a classic network optimization problem that aims to find all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies on multi-objective search with A* (MOA*) have demonstrated strong performance on challenging MOSP instances. This paper presents a novel search framework that enables efficient parallelization of MOA* through different objective orderings and a unique upper-bounding strategy that, in certain cases, allows the problem dimensionality to be reduced to one. Results demonstrate that the proposed framework can significantly improve the performance of MOA*, with speedups increasing proportionally to the number of objectives.