Geocoding is the process of converting human written address into GPS coordinates understandable by machines.
Understanding human text is hard enough but it gets much harder for countries like India where a universal format for writing address doesn’t exist and most addresses are descriptive in nature.
Developing a context-dependent understanding of the address, while simultaneously growing our database of coordinates liked to those places is the major goal we have undertaken at Locus. We use a variety of techniques such as NLP and machine learning to achieve that goal. The NLP we use required heavy customization given the unique nature of address text, primarily its short length and non-obvious flow of tokens within a “sentence”.
Getting geocoding as accurate as possible is critical because it feeds directly into the Vehicle Routing Problem (VRP). VRPs have been extensively analyzed to reduce transportation costs. More particularly, in the real world, time of customer availability is also a usual constraint. Thus, the VRP is extended to VRP with time windows.
Here we will describe using simulated annealing to perform optimization over the objective function for this problem which can take on various additional constraints as well while minimizing a combination of distance traveled, number of vehicles used, time on road or other desired characteristics.