Genetic Algorithm Trip Matching

One of the great things about using our custom device to track mileage is that it gives you access to the Auto-Trip Description feature. The server learns what trips you take. If it recognizes a trip similar to one you’ve already categorized, it will automatically categorize and label it for you. The system places a * in front of any trips that have been automatically categorized. I go through these trips at the end of the month and remove the * after I’ve validated that they were labeled and categorized correctly.

To date, this system has been fairly simplistic. If the start and end points of two trips are close, the most recent trip you’ve made was considered the “match”. For 80% of cases, this algorithm will work. One place where this simple algorithm can break down is when you have trips that loop (office to the bank ATM back to the office). In this scenario, the system cannot tell the difference between a run to the bank (business trip) and a trip to pick up McDonald’s for the kids (personal trip). Another area where the algorithm breaks down is with trips that have similar end points. For example, imagine you’re a contractor and take a business trip to Lowes to pick up materials on Friday (business). Then on Saturday, you take a trip to get your hair cut at the place next to Lowes. Since there isn’t a whole lot of difference in the end points, the system will incorrectly choose the most recent trip (haircut) as a match when you drive to Lowes on Monday.

The new algorithm we’ve developed solves both of these problems using a Genetic Algorithm technique. The system evaluates the “fitness” of previous trips based on the “environment” of the current trip. With the survival of the fittest, the most similar previous trip is considered a match. Using this algorithm, a trip to the bank will look different from a trip to McDonalds, and a trip to Lowes can be accurately matched over a trip to get a haircut based on where you park.

In the future, we’ll enhance this algorithm to include additional criteria into the fitness calculation like time-of-day, day of the week, etc.. so we can continually be bringing you the most pain-free mileage tracking experience.