Let us consider school buses. Let a 'Bus Route' be a sequence of bus stops travelled by a single school bus (day after day). Let a 'Bus Stop' be a combination of Latitude (Lat), Longitude (Lon) and Time-of-Day (ToD). That is, a bus may stop at the same Lat/Lon to pick up kids in the morning and again in the afternoon to drop them off. Furthermore, a bus may stop at a certain Lat/Lon at 7am to pick up high school kids, drop them at school, and then visit the same Lat/Lon at 7:30am to pick up middle school kids, and again at 8am to pick up elementary school kids.

Suppose that a bus sends its Lat/Lon/ToD every time it activates its stop-arm (which it does when it stops to let kids on/off the bus). Suppose we have the Lat/Lon/ToD information for a particular bus for 20 consecutive days.

In a perfect world the bus would make every stop at approximately the same time every day. In the imperfect world in which we live these things happen:

When there are no kids waiting at a bus stop in the morning the driver does not stop (so no Lat/Lon/Tod get sent). On any given day there may or may not be kids at any given bus stop.

When no kid are waiting to get off the bus a given stop the bus will not stop (so no Lat/Lon/Tod gets sent).

So, if there are "in fact" 30 stops, on some days the bus will make 30 stops, on other days it may make 20 stops, etc.

Let's assume that algorithms are already in place to analyze the Lat/Lon/ToD tuples for the 20 days worth of data and correctly identify a set of Bus Stops.

Placing the Bus Stops into the correct order would be a simple matter except that:

On some days the bus may visit stops in one order and some days in a different order. So, if Bus Stops are labelled with letters, on one day the path might be: A C D F H I J L N

and on the next day the order might be:


(Notice there is a sequence "D F H" in the first and "D H F" in the second) This can happen for several reason, including:

a) different drivers have different ideas about what is the best route. b) the driver made a mistake, missed a stop, and has to go back.

ASSUME: there is nobody to ask, "What is the correct route (sequence of stops)?"

PROBLEM: using only the collected data, how can we construct the sequence "most likely" to be correct?

To be clear, this is not an optimization problem; I do not seed to find the "best" route. Rather, if, for example, the bus made exactly the same sequence of stops on 19 of 20 days and on the one odd day the order of two stops was reversed (compared to the other 19) then the "correct" route would be the sequence traveled on the 19 days. What I seek to do is to infer what is most likely the intended route by analyzing when and where the bus actually stops given that drivers skip some stops on some days and sometimes visit some days in different sequence on different days

Thanks for any help you can offer.

Regards, Matt


To be clear, this is not an optimization problem; I do not seed to find the "best" route.

Actually this is an optimization problem! Just instead of optimizing for shortest length or fastest time, you're optimizing for highest likelihood:

What I seek to do is to infer what is most likely the intended route [...]

Now you just have to figure out your model for likelihood.

For example, say that the bus drives$$ \left[\mathrm{A}\right]{\rightarrow}\left[\mathrm{B}\right]{\rightarrow}\left[\mathrm{C}\right] $$half the time, then$$ \left[\mathrm{A}\right]{\rightarrow}\left[\mathrm{C}\right]{\rightarrow}\left[\mathrm{B}\right] $$the other half of the time. But, it tends to do the first route on odd-numbered days, unless it's raining. Except, the driver "Bob" reverses this pattern, whereas "Suzzy" always does the first one and "Atomic Robot #7" always does the second one. What do you infer from that?

Math has no opinion on this topic. For example, if you choose to believe that whatever "Bob" does is always correct, even if every other driver disagrees with him, that's your belief; math doesn't object.

So, what you need to do is construct a model for assessing how likely you believe a particular solution is given a set of data, then optimize for likelihood given the data.


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.