I am trying to solve a shortest path problem through Dijkstra's algorithm. However in my case, cost between nodes (nodes $i$ and $j$) are more than one- two nodes are compared based on two different properties and this results in two different cost values, $C_1(i,j)$ and $C_2(i,j)$. I would like Dijkstra to find a solution which takes $C_1$ and $C_2$ account, together. I have considered a linear combination ($αC_1+βC_2$), but distances are coming from different distributions- one normal and other is not. Therefore, I am not sure whether linearly combining them after scaling is mathematically correct way of doing that. Also, I would very happy to have some references for that, if possible.
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ This is multi-objective optimization. What you propose is called "weighted sum". It's a possible way to handle multiple objectives. It's not mathematically incorrect, but there are other ways that you might want to consider en.wikipedia.org/wiki/Multi-objective_optimization#Solution $\endgroup$– fontanfFeb 21, 2022 at 11:12
-
1$\begingroup$ As @fontanf notes, the weighted sum approach, sometimes known as an Archimedean sum math.stackexchange.com/questions/4320897/…), is just one possible approach. I would be surprised if the differences in how distances are distributed would have any bearing on whether or not the approach is useful. $\endgroup$– prubin ♦Feb 21, 2022 at 16:41
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
You could consider that $C_2$ measures for example time, and you could impose that the shortest path based on $C_1$ may not be larger than a given threshold $T$ based on $C_2$. In other words, you can solve this as a shortest path with a side constraint, and iteratively decrease the threshold. This cannot be solved with Dijkstra, but easily with a linear programming approach:
$$ \min \; \sum_{(i,j)\in A} c^1_{ij}x_{ij} $$ subject to flow conservation constraints and $$ \sum_{(i,j)\in A} c^2_{ij}x_{ij} \le T $$
Note that variables should be declared as integer.
-
$\begingroup$ "Easily" may need to be qualified here as the ILP potentially still takes exponential time to solve. But this is perhaps a necessity, since the original problem is NP-hard as can be shown by reduction from the partition problem. $\endgroup$ Feb 22, 2022 at 2:34
$\begingroup$
$\endgroup$
The bi-objective shortest path problem is a quite well-studied problem. You may find an overview over solution approaches in the paper A comparison of solution strategies for biobjective shortest path problems by A. Raith and M. Ehrgott. You can find it here : https://doi.org/10.1016/j.cor.2008.02.002
$\begingroup$
$\endgroup$
5
I have not worked through the details, but I suspect that it would be possible to modify Dijkstra's algorithm to find all nondominated paths between two nodes. A path is nondominated if no other path is lower in both arc costs. The solution would likely not be unique, so the ultimate decision maker would need to pick one of the nondominated paths.
-
$\begingroup$ In the article linked in @Sune’s answer, it is stated that the problem is NP-hard. Is this compatible with the fact that Dijkstra’s algorithm could be modified to solve the problem (while maintaining a polynomial complexity)? $\endgroup$– KuifjeFeb 21, 2022 at 22:06
-
$\begingroup$ I'm not sure. The adaptation I had in mind might be one of the ones covered in the lit review (but I'm not about to read all the references to find out). It is possible that the adapted labeling mechanism would produce an "intractable" number of labels at nodes, so in that sense yes, it is compatible with NP-hardness. Then again, if you are willing to find only some nondominated solutions, I think the labeling can be kept in check. For instance, at each node you might retain only labels for the nondominated path there with minimal $C_1$ and the nondominated path with minimal $C_2$. $\endgroup$– prubin ♦Feb 21, 2022 at 22:46
-
$\begingroup$ I took a look at the article and read (part of) it (and diagonally), and if my understanding is correct, the authors do mention a labelling algorithm like you suggest, with good results! $\endgroup$– KuifjeFeb 21, 2022 at 22:58
-
-
2$\begingroup$ Ehrgott's book "Multicriteria optimization" (2nd edition) provides both a label setting and a label correcting algorithm for multi-objective SP problems (Alg. 9.1 and 9.2 respectively). In chapter 9 it is also shown that the bi objective SP problem is NP-complete, #P-complete, and intractable. $\endgroup$– SuneFeb 22, 2022 at 8:56