[pgrouting-dev] algorithm allowing negative edge costs

[Haumann Simon]

Hi Vicky,

thank you for dealing with that problem. Those two options seem to be the feasible way. Adding the algorithm as a contribution myself sounds quite compelling - I appreciate your offer to guide me through the process.

We are already heading towards the end of the project, so we decided to choose the first option and implemented the algorithm in an external program using rust.

Off-topic: As a contribution I could offer a simple script/tool which implements the "osm2pgrouting"-conversion-tool in Model Builder of ArcGIS using subprocess in python (e.g. if a user wants to calculate the cost value by himself). It's actually anything but a big deal, however it might be quite helpful.

Nevertheless, it would be great if Bellman-Ford is going to be part of an updated version of pgrouting.

Best regards,
Simon
________________________________
Von: pgrouting-dev [pgrouting-dev-bounces at lists.osgeo.org]" im Auftrag von "Vicky Vergara [vicky at georepublic.de]
Gesendet: Donnerstag, 1. Dezember 2016 17:34
An: pgRouting developers mailing list
Betreff: Re: [pgrouting-dev] algorithm allowing negative edge costs

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<mailto: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<mailto: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<http://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/20161213/5c780537/attachment.html>