HomeApartment hunting routes
Many reasons motivate people to move apartments: being closer to their university or job, retiring and wanting a place in the countryside or by the beach, starting a new family or expanding their existing one, etc. Nonetheless, moving homes is very stressful and it starts with finding a new one.
The demand for services that ease this pain has inspired new technologies and businesses. There are numerous websites and apps capable of offering a vast collection of available homes; and the features they provide are essential to find your new heaven. They can show you places by price range, square footage, neighborhood, number of parking spaces, building structure, or whether it is pet-friendly. Once all possible places are listed there is one more thing all people should do: visit them. Sure, some will opt for online tours but there are important aspects that one can only check by physically being in the apartment to find out if it is too loud, cold, smelly, etc. Among the people who choose on-site visits, most try to visit as many apartments as possible in a single day. That is especially true for those who are moving to a new town or to a neighborhood further away from their current place.
The problem can get increasingly harder to solve if we consider that the transportation time between locations is non-symmetrical, which means that the time to move from A to B is different from B to A. Another very important aspect is that those transportation times also depend on traffic conditions. Route A to B takes on average 1h; however during rush hour it normally takes 1h30, while in lower congestion hours it could take 30 minutes. This means that not only the sequence of visits is important but also that the actual scheduling time has great impact on the number of places visited.
It is clear that the complexity of selecting the best route increases drastically once you have multiple places to go and several possible visiting hours. If the person only has a couple of places to visit, it is easy to check all possibilities and select the most suitable one. However, once the number of places reaches a certain number the only way to find the best route is by using optimization algorithms. The benefits of applying that approach have been discussed in the post The expert and the optimizer.
The apartment hunt route problem is very similar to the problem faced daily by most delivery services. In the Operations Research field, that context is known as the vehicle routing problems with time windows (VRPTW). Delivery companies want to reduce the time spent to complete their routes while respecting the deliverable windows set by their customers. There are two optimization approaches to use when trying to solve this complex problem: exact methods and heuristics. The first approach uses mathematical modeling with the aid of solvers to find the optimal solution; while the second approach uses algorithms to generate feasible solutions in a short span of time.
Large problems tend to be harder to prove optimality and, consequently, take a lot of processing time. That is why many companies opt to use heuristic algorithms that are capable of providing very good (but not optimal) solutions very fast.
So next time you have to face a new round of apartment hunting, bear in mind that the scientific community agrees with you: that is a hard problem!
Co-author: Fabio Silva - Senior Manager at Cassotis Consulting