Google Summer of Code proposal: GRuVeR: A General Ruby library forsolving Routing Vehicle Problems

Discussion in 'Ruby' started by Nikos D., Mar 29, 2008.

  1. Nikos D.

    Nikos D. Guest

    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]
    Nikos D., Mar 29, 2008
    #1
    1. Advertising

  2. Nikos D.

    James Gray Guest

    Re: Google Summer of Code proposal: GRuVeR: A General Ruby library for solving Routing Vehicle Problems

    On Mar 28, 2008, at 9:25 PM, Nikos D. wrote:

    > 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 a person who served as a mentor for the last two years all I can
    say is that I wish most of the proposals I saw were half this good. ;)

    It's clear you've put in a lot of thought about your project and you
    have a solid plan for making it happen. The mentors that review this
    will see that and I believe it will reflect very well on you.

    Good luck with the project!

    > As I noticed proposals can be edited after the submission so I could
    > refine some things.


    Please understand this is not a complaint, but as I was reading
    through the proposal, I found myself wondering about using constraint
    processing in addition to genetic algorithms. I'm just mentioning
    that here so you can factor it into your thinking. I'm not saying you
    should toss your genetic algorithm idea, but it might be a bonus if
    the system you develop could easily have the planned Charlie-based
    integration swapped out for a Gecode/R backend (assuming someone was
    willing to write it, of course):

    http://gecoder.rubyforge.org/

    Disclaimer: I mentored the Gecode/R project last year and thus am
    obviously biased in this matter.

    Anyway, this is just an idea I wanted to share.

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


    The project is pretty specialized, so it may not touch those of us in
    the community not working directly in that area. However, I feel that
    expanding Ruby into new frontiers like this definitely benefits us all.

    James Edward Gray II
    James Gray, Mar 29, 2008
    #2
    1. Advertising

  3. Re: Google Summer of Code proposal: GRuVeR: A General Ruby

    James Gray wrote:
    > As a person who served as a mentor for the last two years all I can
    > say is that I wish most of the proposals I saw were half this good. ;)
    >
    > It's clear you've put in a lot of thought about your project and you
    > have a solid plan for making it happen. The mentors that review this
    > will see that and I believe it will reflect very well on you.
    >
    > Good luck with the project!
    >


    First of all, really thanks for the wishes and the good comments! Now to
    the suggestions... :)

    >
    > Please understand this is not a complaint, but as I was reading
    > through the proposal, I found myself wondering about using constraint
    > processing in addition to genetic algorithms. I'm just mentioning
    > that here so you can factor it into your thinking. I'm not saying you
    > should toss your genetic algorithm idea, but it might be a bonus if
    > the system you develop could easily have the planned Charlie-based
    > integration swapped out for a Gecode/R backend (assuming someone was
    > willing to write it, of course):
    >
    > http://gecoder.rubyforge.org/


    The truth is that even though I have heard of constraint programming, I
    had never really see what exactly it is. After reading some examples on
    the geocode/r site I must confess I found it at least interesting (if
    not exciting :) ). It has a same, basic idea in common with GA: describe
    your problem (somehow) or a way to find a solution and let the computer
    do the hard work for you :) It's really amazing actually!

    So, after some really quick thinking, I believe that it could be used
    *in conjunction* with the genetic algorithms at least in the first
    place.
    For example, most of the RVP problems have some constraints that have to
    be taken into account. So, what a better way to enforce these
    constraints than using constraint programming (this could even rhyme) :D
    You could for example use it to find some initial valid population that
    would evolve afterwards. Of course this doesn't means that the next
    generation would be valid but it is important anyway to have *some* good
    starting population to base upon the evolution that will take place.

    I don't know if this is feasible (and in what extent) but I believe that
    there must be some research work that we could use. If not, then we'll
    have to "brainstorm" a little more... :D I don't have the time today (or
    this week) to do it, but it's on the to-do list definitely.

    As for a complete swapping it is probably already in my thoughts. When I
    say "extensible" in the proposal I mean exactly this! That it would be
    nice to build the system (specifically mainly the public methods) in a
    way that is really unrelated to the backend (aka the inner
    parts/implementations of the library).
    This way when i want to solve the X problem i should call
    XProblem.new(some_data).solve and the XProblem should know which is the
    most efficient way to be solved if no further details are given by the
    user. The decision for this could be based on the kind of the problem
    and some characteristics of the data given (for example the number of
    the stops for a simple Traveling Salesman Problem).

    In the case where a user wants to explicitly define some parameters an
    imaginary example (for the sake of explaining my thoughts) could be:

    XProblem.new :data => some_data,
    :method => super_experimental_genetic_algorithm,
    :method_params => ..


    Something similar could be used regarding the data input/output.

    [note: mentor's support/experience will be really helpful regarding this
    certain aspect of the project]

    >
    > Disclaimer: I mentored the Gecode/R project last year and thus am
    > obviously biased in this matter.
    >
    > Anyway, this is just an idea I wanted to share.


    As I said the project looks really interesting and taken care of :)
    Kudos!
    I will probably play with it this week :)

    >
    > The project is pretty specialized, so it may not touch those of us in
    > the community not working directly in that area. However, I feel that
    > expanding Ruby into new frontiers like this definitely benefits us all.
    >


    I want to believe the same but only time can tell ;)

    Thanks a lot again for the feedback and the ideas.
    Cheers!

    -Nikos

    P.S.: /me is really tired - going to get some sleep before I update the
    proposal... :D
    --
    Posted via http://www.ruby-forum.com/.
    Nikos Dimitrakopoulos, Mar 31, 2008
    #3
  4. Nikos D.

    James Gray Guest

    Re: Google Summer of Code proposal: GRuVeR: A General Ruby

    On Mar 30, 2008, at 8:37 PM, Nikos Dimitrakopoulos wrote:

    >> Please understand this is not a complaint, but as I was reading
    >> through the proposal, I found myself wondering about using constraint
    >> processing in addition to genetic algorithms. I'm just mentioning
    >> that here so you can factor it into your thinking. I'm not saying
    >> you
    >> should toss your genetic algorithm idea, but it might be a bonus if
    >> the system you develop could easily have the planned Charlie-based
    >> integration swapped out for a Gecode/R backend (assuming someone was
    >> willing to write it, of course):
    >>
    >> http://gecoder.rubyforge.org/

    >
    > The truth is that even though I have heard of constraint
    > programming, I
    > had never really see what exactly it is. After reading some examples
    > on
    > the geocode/r site I must confess I found it at least interesting (if
    > not exciting :) ).


    Yes, I learned so much just watching that project come together. One
    big plus of using it is that you can often get great performance out
    of it, if you model the problem well and choose the write strategy to
    solve it with.

    > So, after some really quick thinking, I believe that it could be used
    > *in conjunction* with the genetic algorithms at least in the first
    > place.


    This is a neat idea that didn't occur to me. I have no idea how
    feasible or successful an approach like this would be.

    It might be fun to start a discussion about this on the Gecode/R list
    though and see what those folks think:

    http://rubyforge.org/mailman/listinfo/gecoder-users

    Good luck!

    James Edward Gray II
    James Gray, Mar 31, 2008
    #4
  5. Re: Google Summer of Code proposal: GRuVeR: A General Ruby library for solving Routing Vehicle Problems

    Nikos D. wrote:
    > 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
    > =


    Sounds cool...if you need any help making things work in JRuby, or if
    you find any performance bottlenecks, please file bugs or join us on
    FreeNode IRC in #jruby.

    http://jira.codehaus.org/browse/JRUBY

    - Charlie
    Charles Oliver Nutter, Apr 3, 2008
    #5
  6. Re: Google Summer of Code proposal: GRuVeR: A General Ruby

    Charles Oliver Nutter wrote:
    > Nikos D. wrote:
    >> 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
    >> =

    >
    > Sounds cool...if you need any help making things work in JRuby, or if
    > you find any performance bottlenecks, please file bugs or join us on
    > FreeNode IRC in #jruby.
    >
    > http://jira.codehaus.org/browse/JRUBY
    >
    > - Charlie


    Hi Charlie. I guess some help would be more than welcome so I will reach
    you when I start with the project (whether this is when the project gets
    accepted or when/if I start it alone). Thanks a lot again :)

    -Nikos
    --
    Posted via http://www.ruby-forum.com/.
    Nikos Dimitrakopoulos, Apr 3, 2008
    #6
  7. Nikos Dimitrakopoulos, Apr 8, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. james

    Vehicle Routing problem

    james, Jan 10, 2004, in forum: Java
    Replies:
    1
    Views:
    1,003
    Chris Gokey
    Jan 11, 2004
  2. Michael
    Replies:
    0
    Views:
    492
    Michael
    May 6, 2006
  3. David A. Black
    Replies:
    8
    Views:
    99
    Bill Guindon
    Jun 2, 2005
  4. pat eyler
    Replies:
    21
    Views:
    259
    Peter Szinek
    Mar 22, 2007
  5. Michael Neumann
    Replies:
    1
    Views:
    438
    Mark Volkmann
    Mar 14, 2007
Loading...

Share This Page