Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   Google Summer of Code proposal: GRuVeR: A General Ruby library forsolving Routing Vehicle Problems (http://www.velocityreviews.com/forums/t849265-google-summer-of-code-proposal-gruver-a-general-ruby-library-forsolving-routing-vehicle-problems.html)

Nikos D. 03-29-2008 02:20 AM

Google Summer of Code proposal: GRuVeR: A General Ruby library forsolving Routing Vehicle Problems
 
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/surve...ting/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]

James Gray 03-29-2008 09:54 PM

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



Nikos Dimitrakopoulos 03-31-2008 01:37 AM

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


James Gray 03-31-2008 02:43 AM

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


Charles Oliver Nutter 04-03-2008 10:49 AM

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


Nikos Dimitrakopoulos 04-03-2008 06:07 PM

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 04-08-2008 10:22 PM

Re: Google Summer of Code proposal: GRuVeR: A General Ruby
 
In case anyone is interested here's the discussion on the Gecode/R
mailing list:
http://rubyforge.org/pipermail/gecod...thread.html#32

-Nikos
--
Posted via http://www.ruby-forum.com/.



All times are GMT. The time now is 05:36 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.