[pgrouting-dev] Re: [OSGeo-Discuss] Advice on implementing VRP in FOSS4G

Hi David,

We have implemented something like this last year for pgRouting (extension of PostGIS/PostgreSQL). It’s very similar to what you describe.
Our goal was to have some genetic algorithm to solve the dial-a-ride problem for bus-on-demand as described here http://openvrp.com/blog/darp-algorithm-in-pgrouting/ or here http://georepublic.de/en/projects/openvrp/

It was a funded research project and we’re currently implementing a real bus-on-demand system using taxis and micro-buses.
There are plenty of similar problems related to VRP and a lot of possibilities to add new functionality as you describe. If you’re interested you can join the pgRouting community (http://www.pgrouitng.org) and we can discuss details there.

Best regards,

2011/2/15 cremat0rio <davidsantospinheiro@gmail.com>

Hi everyone!

I’m new on this list, so all the best for all of you and for OSGeo!

I’m writing to get some advice. For my master degree project, I’ll try to
create some code to solve Vehicle Routing Problem (VRP) through Evolutionary
Computation techniques (Genetic Algorithms and stuff like that). It would be
very good to put this code to work on some GIS desktop Software and make it
simple to use, suitable for any layperson.

VRP is a problem where you have some vehicles that need to serve some
places, and you want to distribute them through that area reducing their
overall cost (is terms of fuel consumption, time spent, eco impact, etc.).
For example, distributing waste collection trucks to different areas of a
city, or mailmen’s through some city, or some companies’ trucks that need to
serve mail packages to a country, etc… All this problems have in common that
we want the vehicles (or humans) to be routed on the network to serve some
In terms of implementation we need a LINESTRING layer representing the road
network (of some city, for example) and a POINT (or POLYGON) layer
representing the places that need to be visited (served). Then given some
vehicle’s positions and capacities, and some charging/discharging places the
code would calculate good routes that minimize the mentioned costs.

As I’ve said, it would be good for this package/software to be suitable for
use for any person, so a Desktop GIS implementation would be good.
The problem is that there seems to be two main computing language paradigms
in the FOOS4G Desktop GIS software’s, Java vs C++. Which one to choose?
Which DesktopGis software? Or should I implement something (some function)
in Postgres/Postgis? Or on the command line (on top of OGR)?
In the beginning I thought that a plugin for QuantumGis would be the best
option because the plugins are relatively independent of the core
developer’s work/supervision, and anyone can choose to install it or not.
But this way people that use Java based DesktopGIS (like gvSig) couldn’t
benefit from this work…
So, I’m asking for your kind advice.

Any help/advice will be much appreciated!

All the best,
David Pinheiro

View this message in context: http://osgeo-org.1803224.n2.nabble.com/Advice-on-implementing-VRP-in-FOSS4G-tp6023900p6023900.html
Sent from the OSGeo Discuss mailing list archive at Nabble.com.

Discuss mailing list

Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de