Hi there all, i've just submitted this proposal for this year GSoC and although i know that I should have posted here BEFORE submitting it and not afterwards i would really appreciate some feedback. As I noticed proposals can be edited after the submission so I could refine some things. More importantly i would really like to know how this project sounds in general and if you think that i could benefit the ruby community. Obviously I do (after all I proposed it :D ), but you know, there may be something that I didn't think correctly (or at all)... Anyway, here comes the proposal as submitted in the GSoC app. Some parts are missing because of the character limit but they are included in a pdf version available for download. As said, any kind of feedback is appreciated... = GRuVeR: A General Ruby library for solving Routing Vehicle Problems = Complete version (in pdf format): http://www.uop.gr/~nikosd/gsoc08/gruver.pdf == Abstract == Routing Vehicle Problems are a generic class of NP-hard computation problems which all have in common the same target: how to find the best route in terms of speed, cost and/or efficiency among all possible ones, taking into account the amount of vehicles available, stops needed, available routes and other additional constraints. Although there are several variations of this problem with different levels of difficulty each, they all iterate around this basic principle. RVPs are really common in organizations that provide transportation and delivery services such as the post and courier services, food and diary distribution or even the kindergarten, which has to find a short route in order to take kids back home. Routing Vehicle Problems can also be found in various computer science and telecommunications topics like network routing. It is obvious that having a way to find the "best" possible route in an acceptable amount of time is more than necessary. What I propose is an implementation of an open source ruby library, which will be able to solve such problems efficiently given the necessary input (nodes, routes, costs, etc) and optional constraints. It will based on genetic and heuristic algorithms and it will use existing ruby libraries, such as charlie. So, as soon as this project is finished, it will be easy to integrate it in existing or new applications with vehicle routing needs. This will fill the gap that there is today, since no such open library exists. == Description == === Info on RVP and variations === [please see the pdf version] === Project targets === Setting a realistic target for what we want this project to deliver in the end of GSoC is more than crucial. So, instead of saying that everything will get implemented in 3 months it is way more useful to define a smaller set of features that we target for this available time. Before that, some general guidelines that I have in mind are: -Write the code in a way that it will be easily extensible afterwards. -Prioritize on one specific RVP variation implementation: Solve one first, then move to the other. When the next one is finished refactor and optimize the all the previous if possible. Based on these, I believe that setting, as primary goals, the following tasks is realistic: -Solve at least 2 variations of the RVP class of problems (for example Vehicle Routing Problem with Time Windows and Capacitated Vehicle Routing Problem) -Provide a way for multiple input and output data support (for example a matrix in ruby code, a yaml file, etc...). Additionally, a nice and possibly wanted feature might be defining (or implementing) a way for providing geospatial data as input and output. So it would be possible for example to only give the coordinates of the stops and get a result based on distance by default, without giving any more parameters. Then it would be easy to export the data and plot them on a mapping application. === Methodology that will be followed === As mentioned earlier, the main part of the implementation will use genetic algorithms and genetic programming in general. For this the charlie library will be used since it provides a nice set of features for implementing genetic algorithms in ruby. The focus will be on the official ruby 1.8.6 implementation but I will also try to make it compatible with most of the current alternatives if possible. This can help exposing differences between them in terms of speed. Behavior Driven Development is my preferred way of writing code. So it will be followed in most parts, since it makes easier to test the code base, eliminate bugs early and write documentation. During the development phase I plan to do small and targeted commits on the code repository thus making it easier for both the mentor and me to follow the evolution of the code and also allowing my mentor or any other person involved (community-wise) to provide feedback and suggestions. == Benefits == The benefits from this project will be multiple and diverge: Creation of a free and open RVP library in Ruby that could be used and extended from the community itself as an alternative to proprietary/ closed source implementations that already exist. Even better it could be the first choice among the other ones, at least for Ruby developers. Propagation of feedback "backwards" to libraries used (like charlie, RSpec, ZenTest and different ruby implementations like rubinius, jruby, Ruby 1.9). Last but definitely not least, this project (and projects like this in general) can really help bringing Ruby and Ruby-based projects (Rails, Merb and such) closer to enterprises by providing enterprise-scoped tools in a free as in speech manner. This will enable organizations to customize, build-upon and use this particular project (and ruby in general) while providing feedback, new solutions and possible patches back to the projects' code base. == Deliverables == -Source code with gem packaging -Documentation (including RDoc and usage examples) -Library specifications (RSpec) and/or tests -Website supporting all of the above -Weekly blog posts about updates and progress, in order to facilitate a community around the project == Timeline == Phase 1 (before official start): Gather all necessary research work and discuss the direction that should be followed during development with the mentor. Also set up the necessary environment including a bug-tracker (possibly Trac) and a blog. Phase 2a (official start - midterm evaluation): Spec & Implement the first RVP variant. Phase 2b (midterm evaluation - suggested pencils down date): Spec & Implement the second RVP variant and the various data input/ output helpers. Phase 3 (suggested pencils down date - firm pencils down date): Write documentation, usages examples and final evaluation. Also package library as a ruby gem in Rubyforge. === Possible variations in timeline === [please see the pdf version] == Related work == === Research work === There is a plethora of research work in this particular topic since this is a problem with both practical and scientific interest and the solutions proposed vary both in terms of implementation approach and results. What interest us more are approaches based mainly on genetic algorithms with optional usage of heuristics and / or other methods for optimization of result or computational speed. Mentioning these are out of the scope of this proposal but some are given in the references of the pdf version of this proposal. === Implementations === At the time being only closed source and commercial implementations do exist. Also all of them are either in binary format (executables) or in Java / J2EE. A commercial example is JOpt.SDK and a freeware one is OR-Objects. A more comprehensive list is available at http://www.lionhrtpub.com/orms/surveys/Vehicle_Routing/vrss.html. == Background == I am an undergraduate with a major on Telecommunications Science & Technology, currently on my last year of studies. Throughout my studies I have mostly given emphasis on programming, networking and signal processing and taken courses in subjects as OOP (Java and C/C+ +), network/distributed services and applications, pattern recognition and image/sound analysis and successfully implemented various programming tasks in these subjects. Over the last two years I have been constantly using Ruby and Rails for personal projects and while working part-time (mainly on my summer break) for a start-up company composed of young people which use and contribute on open source projects on a regular basis. Through this I had the opportunity to be engaged in the Ruby, Rails and other libraries' code base allowing me to understand their concepts even better as well as open source's ecosystem, ideas, principles and procedures. == Motivation == I'm really an advocate of Open Source tools, development and ideals and really passionate with problem-solving programming and thinking. It is my belief that bringing more quality and useful tools to the Open Source Community can push it even further to a wider audience, composed by enthusiasts, end-users and enterprises. I feel that I have the necessary background, motivation and will in order to successfully complete this project and this way I can give back to the community from which I have taken so much thus far while having the chance to gain invalueable experience in subjects that really interest me. == Contact Details == [partially removed] and I can be contacted via email at demisone a_t gmail d_o_t com. I also use the nickname demisone in Freenode. == References == [please see the pdf version]