Search code examples
c#graphdijkstralogistics

Form ideal to Real . Dijkstra in logistic

I have a program for transportation company where optimal route computed by Dijkstra . Cities as vertexes and routes as edges . To find weight of edge . I connected cities in map with line and measure it . Then I accept it as weight of edge . But in real life routes aren't straight . So How can I fix it ? enter image description here

In my project I must solve logistic problem with creating Software . Can anyone give me idea what to solve ?

Solution

  • As you already found out, problem is not so simple as it might seem. First of all, connecting only major cities is a bad idea, as they're probably not connected directly with a highways (if it's not U.S. or something).

    That's your current idea: enter image description here

    What I would propose is to try to get every minor city on every way that makes sense and add it as a vertex to your Dijkstra:

    enter image description here

    Now, we come to the point where we can see which way actually exists in real world. From just looking on our graph, we might presume that going with bottom path should be more efficient. But what if we found out this:

    enter image description here

    We can easily come to conclusion now that upper path is actually much better, because you can achieve twice the speed of the bottom one. Is that very precise classification? No, it's not. We might want to think of what traffic is on each way and change weights of edges dynamically. But that's probably too much for your basic implementation.

    What I would do in the end is think of what data can I gather almost alone or with little help. So I can definitely:

    • somehow scrap some data about actual ways of reaching point B from point A; good references are either Google Maps API or Bing Maps API;
    • gather minor cities along the way with finding real world ways from point A to B;
    • try finding out what speed limit is where (if there is any database for it)

    Actually, you might want to go for full into either Google Maps or Bing Maps and just let them provide you with best road possible. They both have quite actual data of any road you need. There is no way you can gather as much data as they do. You have everything on a plate, if you feel that's the way you can do.

    If not, I would go hybrid way - get some vital data from any maps API, then use it for my Dijkstra algorithm, then use this data to write a simple algorithm for measuring actual weight of each edge based on possible modifiers (speed limit, traffic if API provides it and so on).