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?


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.