# Is there an algorithm that can ensure everyone gets bussed to their destination on time, while minimizing the time spent on a bus?

Suppose I am a bus transportation company. I have n buses. I want to change the bus routes so that the "average" commuter spends as little time on the bus as possible, while being able to arrive at as close to their final bus station at their desired time as reasonably possible.

Inputs: Origin bus stations, destination bus stations, and desired time of arrival for each passenger.

Constraints: The average commuter shall arrive no earlier than 15 minutes prior to their desired time of arrival.

As far as I am aware, no readily available (commercial or otherwise) solution exists.

• I encourage you to edit your question to flesh it out. What information do you have, i.e., what are the inputs to the algorithm? What approaches have you already considered? Are they satisfactory? If not, in what ways do they fall short? What are the relevant constraints on bus routes? How would you propose to formalize the problem in the language of computer science? How many buses, commuters, etc. do you have? – D.W. Jan 14 at 21:13

This problem is NP-hard. You can reduce the Hamiltonian-Cycle problem to this problem. Given an instance of the Hamiltonian-Cycle problem, fix a vertex $$v$$. Assume there is exactly one bus and $$2n - 2$$ passengers, where $$n$$ is the number of vertices in the graph. We set the passengers such that one passenger wants to travel from $$v$$ to each other city in the graph and one to travel from each other vertex to $$v$$.
Claim. The given graph admits a Hamiltonian-Cycle, if and only if the total travelled distance is $$2\frac{n (n-1)}{2}$$.
Proof. An optimal route is a Hamiltonian-Cycle from $$v$$ [try to see why]