# Constrained Graph Optimization - Algorithm to connect thousands of nodes while minimizing cost for bus routing?

I'm trying to make public transportation better by working with my city to rearrange the bus routes to minimize travel time for users with certain constraints - up to b buses and k kilometers of travel.

I've simplified the problem to 3162 (n) nodes (bus stops) each with a certain importance, with the goal of minimizing travel time between any two stops, weighted by the importance of the stops.

So I'm trying to generate a series of up to b Eulerian paths (bus routes) of up to total length k that together minimize the cost of traveling from any node to any other node. In other words, minimize:

$$L_{total}=\sum_{A=0}^{n}{\sum_{B=0}^{n}{\textrm{importance}(A)*\textrm{importance}(B)*\frac{\textrm{time}(A, B)}{\textrm{distance}(A, B)}}}$$

while ensuring that the total traveled distance for all routes remains below k and only b routes exist. Note that $$\textrm{time}(A, B)$$ above is path dependent depending on the bus routes, but $$\textrm{distance}(A, B)$$ is absolute, which I'm using taxicab distance for. This normalizes time to expected time by distance.

I've got my model down, now I'm trying to figure out how I actually go about generating routes. Given 3162 nodes, that's 9.995 million possible links between nodes, and I likely need to construct over 200 routes, each most likely to consist of 3 - 30 stops. Brute forcing this one just isn't practical.

As an engineering problem, how do I efficiently generate this set of routes?

EDIT

I mistakenly left out part of the cost function: time. Sorry :)

• You hire a mathematical consultant. – Gerry Myerson Oct 20 '18 at 11:14