[pgrouting-dev] Shortest Path with conditional cost

[Stephen Woodbridge]

Julien,

This is called the Dial-A-Ride problem. It is a common VRP (Vehicle 
Routing Problem).  You could also use a PDP (pickup and delivery 
problem) to solve this where your packages are you people and the 
delivery point is the destination and the start point it the driver's 
location. Both of these are well defined problems and can be solved 
using a TABU search.

We have a basic VRP solver that was developed last year in GSoC but it 
is for a single depot multiple package delivery with time windows 
problem. It uses a TABU search.

https://github.com/pgRouting/pgrouting/tree/gsoc-vrp/src/vrp_basic

-Steve

On 3/10/2014 8:53 PM, Julien-Samuel Lacroix 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
>
>