[pgrouting-dev] algorithm allowing negative edge costs

Haumann_Simon · December 1, 2016, 1:56pm

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!

cvvergara · December 1, 2016, 4:34pm

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.

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@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@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@[georepublic.de](http://georepublic.de)
Web: [https://georepublic.info](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

Haumann_Simon · December 13, 2016, 3:23pm

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

···

On Thu, Dec 1, 2016 at 7:56 AM, Haumann Simon <haumanns@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@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@[georepublic.de](http://georepublic.de)
Web: [https://georepublic.info](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

dkastl · December 14, 2016, 12:30am

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

... which gives a 3rd option: to fund the development
If someone is interested to do so, just contact one of the pgRouting
developers.

Simon, thanks for sharing your solution!
Regarding the conversion-script, with Github (and similar platforms) it's
very easy to share source code as Open Source, giving the credits to the
original author.
So I suggest, that you just go ahead, if you would like to do so. We
happily add a link from some pgRouting site to the repository, that users
can find it.
For contributions to pgRouting it's also important, that someone maintains
the source code and at least Vicky and I do not use ArcGIS, so we would not
be able to do so.

Best regards,
Daniel

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: https://georepublic.info

Haumann_Simon · December 23, 2016, 4:25pm

Dear Daniel,

I am positive that I will be able to share the solutions on Github very soon. I will get back to you for the invitation/link to the repo.

As soon as I recognise my graduation on my bank account I will reconsider your 3rd option

Thank you&Merry Christmas to all of you!
Simon

···

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

… which gives a 3rd option: to fund the development
If someone is interested to do so, just contact one of the pgRouting developers.

Simon, thanks for sharing your solution!
Regarding the conversion-script, with Github (and similar platforms) it’s very easy to share source code as Open Source, giving the credits to the original author.
So I suggest, that you just go ahead, if you would like to do so. We happily add a link from some pgRouting site to the repository, that users can find it.
For contributions to pgRouting it’s also important, that someone maintains the source code and at least Vicky and I do not use ArcGIS, so we would not be able to do so.

Best regards,
Daniel

–

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