[pgrouting-dev] Shortest Path with conditional cost

[Stephen Woodbridge]

On 3/10/2014 9:13 PM, Daniel Kastl wrote:
>
>
> On Tue, Mar 11, 2014 at 9:53 AM, Julien-Samuel Lacroix
> <jlacroix at mapgears.com <mailto: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? ;-)

This can be solved by Dial-a-Ride or Pickup and Delivery VRP solvers. 
Both of these are on out GSoC Ideas page.

-Steve