1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ – D.W. Jan 14 at 21:13
1
$\begingroup$

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]

$\endgroup$
4
  • $\begingroup$ What about a general solution, where your assumptions don't hold? $\endgroup$ – moonman239 Jan 15 at 20:12
  • $\begingroup$ which assumptions? $\endgroup$ – narek Bojikian Jan 15 at 21:11
  • $\begingroup$ Narek: The assumptions of exactly 1 bus and 2n-2 passengers. $\endgroup$ – moonman239 Jan 15 at 22:13
  • $\begingroup$ these are the reduced instance. Since they are special cases of your problem, your problem is at least as hard. $\endgroup$ – narek Bojikian Jan 15 at 22:28
0
$\begingroup$

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.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.