For a while I have been thinking about Vehicle Routing (you can see a previous blog here). Most of the problems I come across (though I am happy to be corrected) assume that distances are symmetric. That is, the distance between location i and location j is the same as the distance between location j and location i. I know that there has been some work done on the asymmetric Traveling Salesman Problem, but I am not aware that the asymmetric VRP has received a similar amount of research attention.
It is not always the case, particularly in real world problems, that the distances are symmetric. For example, the driving distance between two locations might be different depending on the direction you are traveling.
I guess there are many reasons why symmetric distances are used. For example:
- If we are storing the coordinates of each location we can calculate the distances algorithmically, as part of the pre-processing to the main optimisation algorithm.
- We could ask if it really matters if we work with symmetric distances? Does it really affect the results that much, or make any difference to the conclusions we can draw about the algorithm we are using?
But I have been wondering if there is any mileage (sic) in looking at asymmetric distances, in the context of real world VRPs?
With these questions in mind I have recently (a couple of months back) been looking at Google Maps as a way of being able to collect data. Google actually provide a very nice API (Application Programming Interface) which is quite easy to use and there (as you would imagine) is a lot of information available.
I got to the point where I have a Google Maps application up and running, really just to prove to myself that what I wanted to do was possible. Then I had to abandon it for a while as I had other, more urgent things to do. However, it is still on my mind about the research that is possible and I plan to address some of them in the near future.