0
$\begingroup$

I would like to solve a shortest path problem on a graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$, which comes to minimize : \begin{equation} \label{eq:1} \underset{\{x_{ij}\}}{\text{argmin}}\biggl\{\sum_{(i,j)\in\mathcal{A}}a_{ij}x_{ij}\biggr\} \end{equation} 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 : \begin{equation} \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} \end{equation} 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 ?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 20, 2023 at 19:12

1 Answer 1

0
$\begingroup$

I think one possibility would be to run normal shortest path algorithms on separate graphs which respectively encode the differing objectives, and then search across possible paths in the graph.

The rationale behind this is that the different objective costs are independent of each other. Thus shortest path algorithms can be used for the graphs of different objective costs separately.

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.

$\endgroup$
2
  • $\begingroup$ 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" ? $\endgroup$
    – deb2014
    Jun 20, 2023 at 8:47
  • $\begingroup$ @deb2014 Yep. Simply do multiple shortest path plus a search. $\endgroup$ Jun 20, 2023 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.