[pgrouting-dev] Shortest Path with conditional cost

[Stephen Woodbridge]

On 3/11/2014 8:16 PM, Julien-Samuel Lacroix wrote:
> Hi Steve,
>
> I took a look at the code, but I must admit I'm a bit lost in the code
> of this branch. There's only one sql function called pgr_vrpOneDepot
> that takes order, vehicule, cost and depot sql statement. Can you give
> me an example of this in action?

http://osrm.georepublic.net:1337/#

This is a demo Daniel put together that uses this code. Click the 
[Sample Data] buttons for Vehicles, Depot, and Orders, then click [Start 
Scheduler]

This particular problem solves the case where you have a warehouse and a 
fleet of vehicles and some orders. It allocates the orders to the trucks 
  and mimizes the overall cost. to deliver the orders.

This is not the problem you are trying to solve. Look at the Pickup and 
Delivery link below. For a car pool, you have a driver with there 
location at they home and N people st home are the pickup location and 
the destination can be defined for each person or they can all have a 
common destination.

You can have lots of variations on this. Like multiple drivers and each 
vehicle can have a capacity. Each person can have a delivery time 
windows and/or pick up window, etc.

All VRP problems can be constructed and solved using a TABU search. The 
probably is to construct a model of constraints and inputs and then 
optimize a solution using TABU search or some other search engine to 
find a solution.

> Is there any documentation from the GSoC project?

Not much or any as the case may be. The basic VRP will get integrated 
into 2.1 when I have enough free time to merge it, write the docs and 
test cases.

> I feel like my problem is the reverse of this. I have a bunch of
> vehicule and only one order to deliver at one or more depot. I want to
> be able to use one vehicule in my network, but not two. The reason
> behind this reasoning, that there may be more than one type of vehicule
> (carpool, bike, city bus, etc) and you can use more than one of them in
> a single ride, but not twice the same type in a single ride (Note that I
> oversimplified my explanation here). Anyway, I'll take a look at the VRP
> code to get ideas.

https://github.com/pgRouting/pgrouting/wiki/VRP%20Pickup%20Delivery%20Problem

I think you might be looking at multi-modal routing, like drive to a 
train station, get the train, maybe change trains or get a bus, walk to 
your destination or get a cab to your destination. This gets a little 
complicated because you have to have support for time schedules, 
parking, and it means you have to plan for a start time or an arrival 
time and deal with wait times to make connections and do transfers 
between modes.

We have a multi-modal GSoC project:

https://github.com/pgRouting/pgrouting/tree/gsoc-multimodal

but it was complicated and there was no documentation. If this is what 
you are looking for Daniel or I can find that code and point you to it. 
Maybe you can get the developer to answer some questions.

Its not yet clear to me what problem you are trying to solve.

-Steve

> Julien
>
> On 14-03-10 09:12 PM, Stephen Woodbridge wrote:
>> 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
>>>
>>>
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>