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@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
