neděle 2. května 2010

Vehicle Routing Problem

One of my school assignments this semester was to implement some of the algorithms which solve the Vehicle Routing Problem.

UPDATE: I have moved the source code to GitHub. Get it or fork the project.

In VRP you have a depot and a set of customers. You have a fleet of vehicles which can serve this customers. Each customer can have an exact demand on quantity of goods and each vehicle can have capacity which is able to serve. This is easily modeled as Graph Theory Problem. The problem is NP hard. However there are several algorithms described for this problem (heuristics,genetics). To know more about variants and different solutions check this source.

I decided to implement Clarks & Wrights and Sweep algorithm. I build my solution in JAVA but later I decided that it would be cool to have some way to visualize the results. Then I decided to use GWT-MAPS API to visualize real world problems. Soon I wanted also to visualize the random generated graph problems so I included the GWT-INCUBATOR API to show some small graphs.

Check the program here

Basic functions

  • Compute the routes using Clark & Wright or Sweep algorithm
  • Generate random VRP - including distance matrix, node positions and demands of each node
  • Compute distance matrix from real world data using Google MAPS API

Basic usage
The input for this utility to compute the vehicle rows has to be specified as follows:

[route count]
[distance matrix]
[customer demand;address;x coordinate;y coordinate]


After loading the site you can see example problem of 3 customers. You can run Clark & Wright or Sweep algorithm and you will obtained the routes of the VRP in the OUTPUT window. Before running the algorithm you should set the capacity of the vehicles - in this situation all the vehicles have the same capacity. The output has the following format:

[number of routes]
[depo city1 city2 ... cityN depo]
...
[depo->city1->city2 ... cityN->depo]
...


You can visualize the output either on Graph or on MAP - if you working with real world cities and addresses than you visualize on map. If you are working just with sample data the you can visualize on the graph.


Generating distance matrix for real world cities
To generate the distance for several cities for which you know only the addresses u will enter in the INPUT box on each line one city and then click on "Generate distance matrix". Also you can see that on the MAP tab all the routes network connecting all the cities has been visualized:

image



Now you need to modify the input - more specifically modify the amounts of goods requested by each city. The DEPOT is always in the first city, so there the demand would be zero. Let's say your customer in Milano wants 15 units, in Paris 20 units and in Prague 13 units.



Now again you can just run the desired algorithm and view the results. For example after running the Clark & Wright algorithm you should get the following output:



Now you can visualize these routes in the MAP.


Generating and visualizing random problem
To generate random GRAPH VPR Problem you have to specify:

- Number of nodes.
- Constant by which the random value(0-1) would be multiplied to obtain desired amount for each city.
- Constant by which the random value(0-1) would be multiplied to obtain random coordinates of the city.

After you will obtain the desired INPUT.



Now you can run one of the algorithms(eg. SWEEP) and you will obtain the OUTPUT - the routes of the vehicle.



Now because this is randomly generated problem it is good to visualize it in the GRAPH:


THE ISSUES
The clear method of the canvas to visualize the points is not working fine - generating new VRP problem will not erase the points of the old VRP problem. The main issue is that this application uses the GWT Canvas, which was a part of GWT incubator. It also uses the Google Maps binding for GWT.

Since I have wrote the application there have been several changes in the situation about GWT and plugins:

  • Canvas is now part of the GWT 3. So theoretically the application could be rewritten using GWT 3.
  • Google Maps are now in version 2. However the GWT binding for Maps v3 has not yet been released – there are however some open-source initiatives.

So  what to do now? I have kept the code as it is: using maps v2 and the ancient Canvas project. If anyone feels motivated for moving the application to GWT 3 (changing Canvas and Maps binding) just fork it away on GitHub.

About the source code

On GitHub you can currently download two packages:

  • Java-only package. That is a basic library and executable program which can solve the VRP without the visualization.
  • GWT packages. Contains the classes which perform the VRP solving and the visualization using GWT.

The classes from the Java-only package are copied to the GWT project. That is because they have to be presented at compile time – the classes cannot be included as a JAR file. If anyone knows how to reuse a code in GWT projects without doubling it – let me know.

The  code is of a very poor quality. At time when I have wrote it I simply did not care about the readability and also I did not know Java that well.

24 komentářů:

  1. Hey Honza!
    I am a student at UCLouvain in Belgium in Business Ingenieur.
    For a school assignement, we have to build a web application that gives the routes for the distribution of newspapers.
    For that, we are using gwt and eclipse and we would like to implement the vrp algorithm, almost like you show on your wall.
    Would it be possible that you provide us your codes? We are using java...
    This would be very helpful, we are beginners and tend to get lost in the codes ;)
    Thank you very much for reading this :)
    Sara
    (smdf2000@hotmail.com)

    OdpovědětVymazat
  2. Hi Honza,
    Your app is so interesting. I am Leo, from NTU Singapore. I am also doing a related project. I have downloaded you codes but got some problems while running your code, do I have to do anything to set-up before running the code? I am using Eclipse, and trying to install GWT however I still got error message with the "import coom.google..."
    DO you have any suggestion?
    Thank you very much!

    Leo (lehoangdung at pmail dot ntu dot edu dot sg)

    OdpovědětVymazat
  3. Hi Honza,
    please if you can send me your application report,i really need it...thank you very much!

    abdellah7000@gmail.com

    OdpovědětVymazat
  4. Abdellah,

    the report is in Czech language, so it will not be of much help for you I think...

    OdpovědětVymazat
  5. Hi Honga,

    thanks for your reply,i asked you about your report only because i didn't understand the use of somme classes,so please if you don't mind sending me somme clarifications concerning the codes (pleaaaaaaaase)...you can contact me on this adress : abdellah7000@gmail.com......thank you so much

    OdpovědětVymazat
  6. am30568@gmail.com...I need some help in this...if u can send me the java code it will be very helpful

    OdpovědětVymazat
  7. Hello I am develop a research about code in internet, pls I need contact you for remaks some aspects. My email is father_bear@hotmail.com. This is not spam I am a student of University of Catalunya
    Thanks

    OdpovědětVymazat
  8. Hello Honza and everybody i have the same problem i did writhe all the code but i still have problems with some jars like the one where we can found widget,maps ....
    if it's possible can u send me the code in my mailbox??? it's touria1989@gmail.com

    OdpovědětVymazat
  9. Hello everyone,

    The code is little bit outdated. It uses GWT with Google Maps v2 plugin and also Google Canvas plugin. This stuf does not exists anymore. Because it interests a lot of viewers I think I might rewrite it in JavaScript...- this pure client side code - JavaScripts seems to me the only language. I will try to do this in next month...but I am quite busy with other projects at the moment...

    OdpovědětVymazat
  10. Hello.
    i have problem with compilation i download the GWT plugin for google chrome and it didn't work so i download an old version of firefox the 3.5.19 i didn't found the GWT plugin for it what can i do??
    What is ur advice!!!!!

    OdpovědětVymazat
  11. Hello everyone,

    I have took some time to take a look back at the project. The source has moved to GitHub: https://github.com/hoonzis/Vehical-Routing-Problem/.

    Regarding issues with compilation: you will have to install Eclipse GWT plugin and than import the projects to Eclipse. I have tested it using Eclipse 3.7 and Google Chrome plugin.

    Also Google Maps uses a "key" to access the API. Please generate your own key. This key has to be added to the script link pointing towards google maps which is in the index.html.

    OdpovědětVymazat
  12. Hi
    for me i'm using eclipse indigo and i did download the gwt plugin for firefox 3.5.19 but it didn't work.
    also i took the key you had in the website https://github.com/hoonzis/Vehical-Routing-Problem/ they said to me it's no longer working and if you are the owner of the project this a link u can use: https://developers.google.com/maps/documentation/javascript/v2/introduction?hl=fr#Obtaining_Key

    OdpovědětVymazat
  13. If it's possible and you can give me some of ur precious time i would be thankful this is my yahoo id : touriakarite@yahoo.com just tell me when you are free this week and i'll be waiting cause i will have my presentation in the end of this month.

    OdpovědětVymazat
    Odpovědi
    1. Sorry man, If you have concrete questions, you can post them here, I could try to respond. But as said before - I have verified that the solution can be compiled and works.

      Vymazat
  14. ok i will try it and thank you for your help.
    you don't have a code for the 2 opt method???

    OdpovědětVymazat
  15. hi!!!!!
    i used the old code u posted here i did some modification need and everything it works with 8 cities but when i tried with more cities 50 and 100 with their coordinates and their demands(requests) an error appear to me the message say " error 620 and 602" this errors i think it's because of the localisation!!! what's i have to do to resolve this problem??? and thank you.

    OdpovědětVymazat
    Odpovědi
    1. Hello,

      Yes. It's GeoLoc problem. In the version which I have put on GitHub this weekend, I have made a change in order to prinout out also the request which you causes the error.

      In the VRPGui class search for DirectionsCallback. There you can change the action which on the geoloc error in the "onFailure" handler.

      https://github.com/hoonzis/Vehical-Routing-Problem/blob/master/gwt/src/vrp/client/VRPGui.java

      If this arrives you can either skip the query - or tray to reformate it.

      Vymazat
    2. Hi.
      the code worked finaly for me.and the maps appear for just few seconds and disappear they tell me to change the API key i go to http://code.google.com/apis/maps/documentation/javascript/v2/itroduction.html#Obtaining_Key i do that i activate a new key as they say in the website but this message appear to:

      "Google has disabled use of the Maps API for this application. The provided key is not a valid Google API Key, or it is not authorized for the Google Maps Javascript API v2 on this site. If you are the owner of this application, you can learn about obtaining a valid key here: http://code.google.com/apis/maps/documentation/javascript/v2/introduction.html#Obtaining_Key"

      Vymazat
  16. No worries i had my api key but an error still appear to me it's "error 500"???

    OdpovědětVymazat
  17. Hi Jan Fajfr,
    so the application worked for me i have just one small problem with the graph it dosen't appear correctly as when i used the old code.
    i made some changes in vrp guid in the resolution but nothing new appear.
    thank you for your help i'm very thankful.



    Touria.

    OdpovědětVymazat
  18. Hi.
    where i can change in the VRPGui??in order that the graph appear to me in the center cause now it appear to me on the left and it's just a part of the graph not all of it.

    OdpovědětVymazat
  19. hi
    i have the same problem with graph, can u send me the old version of the code please
    beacause the old version it works for me pleaaaase
    thank you!!

    OdpovědětVymazat
  20. has anyone realised the ClarkAndWright method is wrong? Outputs are not optimal.. did you fix it?

    OdpovědětVymazat
    Odpovědi
    1. Hi Guillem,
      As said in the mail, just for it on GitHub and provide the correct version. I will update the arctile or add a link to your blog/post with correct version.

      Vymazat