[pgrouting-dev] Shortest Path with conditional cost

[Daniel Kastl]

On Tue, Mar 11, 2014 at 9:53 AM, Julien-Samuel Lacroix <
jlacroix at mapgears.com> wrote:

> Hello,
>
> I'm trying to get my head around a networking building problem and wonder
> if it would be possible to have conditional cost depending on the type of
> segment (or nodes) we crossed to get there?
>
> An example would be:
> Each line segment have a cost and a type (A, B or C). You need to
> calculate the shortest path from one node 1 to node 35, but can only use
> one segment of type C.
>
> Would this be possible?
> What kind of modification would this need?
>
> My current solution would be to calculate the total cost using every
> single type C segment in my area, but in the long run, I fear this won't
> scale.
>
> I'm currently building a carpooling portal and I get the carpool offers as
> segments and nodes in my DB. I should not allow users to plan a trip
> combining 2 different offers as this quickly becomes a logistical nightmare.
>
> Best regards,
> Julien
>
>
Hi Julien,

It's an interesting problem and the first thing that came to my mind was
"Time Dependant Shortest Path" (TDSP) as it also has one constraint which
changes during moving through the network.

Jay developed it during Google Summer of Code, but before last year's new
release, so the code still lives in a separate branch and won't follow the
formal rules we use since version 2.0

   -
   https://github.com/pgRouting/pgrouting/wiki/Time-dependent---Dynamic-Shortest-Path

Well, in your case I think it needed a new algorithm, but maybe TDSP gives
some ideas. Soon GSoC is going to start, so this is another project idea?
;-)

Best reagrds,
Daniel



-- 
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.info
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20140311/eb9b7819/attachment.html>