Modified Dijkstra to find most optimized shortest

Question

This is a follow-up question for a question I asked at here. The problem is mapped to a graph with say non-negative weights on edges (no preference if it can be directed or not). However, along with a weight which is actually distance, we also have another property which is data coverage of the edge which can be important factor which route to select given how severe I need internet on my phone (for real-time gaming for example I need good bandwidth). So overall, we want to somehow find a trade-off between the length of the path and network bandwidth to solve the problem of finding most optimized and shortest path between two cities. However, an important feature is that the algorithm should be dynamic. Once we arrived to a node, depending on our current state of need we might change the pre-determined path.

OK. For simplicity, let's say each edge is associated with two properties: A) a distance or travel time or whatever, as a regular weight, and B) network bandwidth as a secondary property to show how good network is.

For constraints and objective function, say we want to minimize the total distance (or travel time), but depending to our current state, we also want to minimize the total disconnection time or maximize the total sum of path bandwidths. Optionally, say we can not tolerate total continuous disconnection time of more than a threshold T. So this can be a constraint on the problem. The simplest of such objective functions can be f()=total time of travel + a*time of disconnection. The a co-efficient determines how important connectivity can be for us at each time.

To tackle the fact that edges can have partial disconnections, after a bit of think, I came into a solution that let's insert nodes in between. That makes the problem easier to solve. So basically each route either has disconnection, or connection with a bandwidth of specific value.

A first-version solution that came into my mind was to accumulate the total continuous disconnection times whenever we are computing a path, so it can not go beyond the threshold T. And whenever we reached a route with connection (regardless of bandwidth for a simpler problem), we just reset the accumulation. Further to account for bandwidth, since we also have value for connection bandwidth, we can just deduct the value of connection bandwidth from the total accumulated disconnection time (does it work?!)

One important thing is to consider the following example figure. Not exceeding the total disconnection threshold shouldn't lead to go through a very far route which increases the total time of travel! For that, I thought about this general approach: Solve the problem for disconnection threshold of say T1, T2, ...Tk, compute the best path (or a set of best paths maybe?!), and compute the corresponding total travel time for each. Then apply the objective function that we have above and see what is the most optimum solution. We can further pin point the solution between two samples to find more optimum solution using a binary-search-like approach.

Please, can someone please help me to solve the problem? Apparently my solution is not correct, and if it was, even not possible in polynomial time. Maybe approximation algorithms?! Any helps to find a solution is highly appreciated. Feel free to add more details or assumptions, or revise the problem. The problem is harder than what I thought.

Answer 1

First of all finding the perfect answer to this question for the whole network is computationally infeasible. See http://phys.org/news/2015-05-maths-congestionsprings-traffic.html for an article outlining some of the practical complexity and numerical instability that you'll encounter. As well as a demonstration that adding roads can make the whole network worse.

However we can solve it in practice reasonably well for exactly the IP networking problem that you're looking at. A google search gave me https://www.cs.princeton.edu/~jrex/papers/opthand04.pdf as a suggestion for where to start learning the literature.