## 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

### About the source code

• 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)

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)

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

abdellah7000@gmail.com

4. Abdellah,

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

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

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

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

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

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...

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!!!!!

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.

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

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.

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.

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

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.

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.

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"

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

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.

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.

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!!

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

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.