[pgrouting-dev] algorithm allowing negative edge costs

[Vicky Vergara]

Hello,
Currently we don't have Bellman-Ford.

We are trying to add as many graph functionality from boost::graph, that
function is certainly one of the goals.
It is not planned for the 2.4 version of pgRouting due to release on march
next year, and I guess that
waiting is not an option.

from my point of view, is see 2 possible approaches:
option 1)
Use the
http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/bellman_ford_shortest.html
on an independent program.
option 2)
Add the
http://www.boost.org/doc/libs/1_46_0/libs/graph/doc/bellman_ford_shortest.html
into pgRouting, and the use it from the database.

Of course, as pgRouting developer, I see that option 2 has its advantages:
we can guide you on how to add it to pgRouting,
part of your theses work would be open source,
let the world use your work!!!
you can have the contribution as part of your resume.

On any option, how long would it take it to do it?, might depend on your
C++ coding skills.

please, keep me posted on tour decision.

Vicky





On Thu, Dec 1, 2016 at 7:56 AM, Haumann Simon <haumanns at student.ethz.ch>
wrote:

> Hello,
>
> for a project in the course of my master thesis, I use pgRouting to find
> the route with least energy consumption for e-bikes. Accordingly, my model
> calculates the energy consumption (Wh) which is implemented as cost factor.
> Due to recuperation, I have several negative edge costs. Therefore, I
> need an algorithm which takes this circumstance into concideration.
> Unfortunetly, the appropriate single source shortest path (SSSP) algorithm
> (Bellman-Ford) is not yet part of pgRouting ( http://www.boost.org/doc/
> libs/master/libs/graph/doc/bellman_ford_shortest.html ). Previous
> enquiries ( http://lists.osgeo.org/pipermail/pgrouting-users/
> 2013-July/001589.html ) did not solve that problem.
>
> Do you have any recommendation how to deal with this kind of matter?
>
> Possible approaches:
>
> - Anyone who created a beta version / pgRouting-command of the above
> mentioned Bellman-Ford?
> - altering existing all pairs algorithms (johnson's, floyd warshall) which
> theoretically allow scattered negative edge costs (in pgRouting too?) to
> SSSP like dijkstra
> - idea for a workaround (e.g. adapting the cost calculating model so there
> are no negative edges no more)
> - another develompment tool / framework that runs Belman Ford?
>
> Thanks for your help!
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>



-- 

Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky at georepublic.de
Web: https://georepublic.info

Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20161201/45ba15f5/attachment.html>