# 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, 2021 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]

• What about a general solution, where your assumptions don't hold? Jan 15, 2021 at 20:12
• which assumptions? Jan 15, 2021 at 21:11
• Narek: The assumptions of exactly 1 bus and 2n-2 passengers. Jan 15, 2021 at 22:13
• these are the reduced instance. Since they are special cases of your problem, your problem is at least as hard. Jan 15, 2021 at 22:28
• So, how do you go about solving the initial problem? Apr 8, 2021 at 18:42

I have a feeling that the best solution is reinforcement learning. Simply put, with the data in hand (or simulated data), label the rewards as median or mean time spent on the bus and median or mean amount of time before desired time of arrival, with a possible consequence that arrival after the median time results in no long-term reward (we don't want commuters to be late.)