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 &quot;average&quot; 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.
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]