# Shortest path problem with multiple objectives

I would like to solve a shortest path problem on a graph $$\mathcal{G}= (\mathcal{V},\mathcal{A})$$, which comes to minimize : $$$$\label{eq:1} \underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\sum_{(i,j)\in\mathcal{A}}a_{ij}x_{ij}\biggr\}$$$$ in which $$a_{ij}$$ is a non negative scalar quantifying the cost of arc $$(i,j)$$, $$x_{ij}\in\{1,0\}$$ whether the arc $$(i,j)$$ is in the path or not and, with constraints : $$$$\label{eq:2} \forall i\in\mathcal{V}\;,\quad y_{i}= \sum_{j\,/\,(i,j)\in\mathcal{A}}x_{ij} - \sum_{j\,/\,(j,i)\in\mathcal{A}}x_{ji} = \begin{cases} 1 &,\,\text{if}\; i=s \\ -1 &,\,\text{if}\; i=t \\ 0 &,\,\text{if}\; i\notin \{s,t\} \end{cases}$$$$ where $$s$$ and $$t$$ are respectively the starting and terminal nodes.

The cost $$a_{ij}$$ of arc $$(i,j)$$ usually encodes many objectives :

• fuel consumption
• time of travel, the shorter the better
• whether nodes $$i$$ or $$j$$ are in a forbidden or restreint zone

A typical shortest path algorithm will give one optimized path with respect to how various objectives are weighted in the cost.

Is there a different formulation that would allow for an algorithm to give simultaneously several paths for different weighting of objectives ? like genetic algorithm are able to do ?

• This sounds too broad to answer. The answer will likely depend on what specifically you mean by what paths you want (how should the choice depend on the weighting of objectives? this isn't specified) and how you plan to weight objectives.
– D.W.
Jun 20, 2023 at 19:12

For instance, if we use Dijkstra's Algorithm as the base method (perhaps not actually applicable to this case, just an example), we first could generate the cost trees based on each of the objectives. Thus now each node corresponds to a vector $$\mathbf{c}_{node}\in\mathbb{R}^N$$ for the $$N$$ different objectives. Thus now for each set of objectives (represented by vector $$\mathbf w$$), we can search through the nodes while using the dot product $$\mathbf{c}_{node}\cdot\mathbf{w}$$ as the loss.
• Thanks for your answer, yes different objective are independent of each other. I could run a shortest path algorithm for each objective (meaning that the cost $a_{ij}$ only reflects one of the objective) so as to obtain several paths optimized for distinct objectives. Is this what you meant by "Thus shortest path algorithms can be used for the graphs of different objective costs separately" ? Jun 20, 2023 at 8:47