I work for a state health program and am looking for the most efficient way to route inspectors from restaurant to restaurant. This is something like the travelling salesman problem, but with additional complexities. We have 75 inspectors, making less than 8 hour round trips from 17 different offices, inspecting ~18,000 businesses at 1.25 hours an inspection (not counting travel time). These businesses either need inspected annually, 3 times a year, or 5 times a year depending on their assigned risk level. Does anyone have any ideas/suggestions for this? I am talking to Telogis and Viamente as far as getting quotes for using their products but am interested in looking into all avenues. It's possible this is not on the right Stackexchange, if you know of a more appropriate venue I'd appreciate knowing that as well.
jsprit can solve your problem. It is a java based, open source toolkit for solving rich traveling salesman (TSP) and vehicle routing problems (VRP). Rich means here that you can model an arbitrary number of constraints that account for your business requirements such as skills, time-windows etc.. And in conjunction with jsprit, you can use GraphHopper.
Our FleetEngine software can also handle such tasks, although you would have to break the problem into smaller tasks, to handle it efficiently.
If you do not have a problem with Java code you could have a look into my Open Source GraphHopper project.
I have been using RouteSmart for some time, and recommend it highly. It's specifically designed to solve "high density" routing problems (~20K points is something I would refer to as dense), i.e., those involving a very large number of points that must be serviced regularly. It is not an open-source product but imho worth investing to.