[pgrouting-users] Using pgrouting for senior capstone design project?

[Stephen Woodbridge]

On 2/23/2012 10:20 PM, Andy Carnevale wrote:
> I'm a senior industrial engineering student at Ohio State working at a
> local healthcare company to help them improve their routing
> efficiency. I've been tasked with designing a software solution that
> will help them generate daily routes. They serve almost 600 active
> clients across four centers around Columbus with a fleet of 26 vans. I
> need to figure out some way to take their client roster and generate
> routes that will minimize costs within the system restraints (limited
> number of wheelchair spots on each van, different client pickup
> windows, etc.). I have a background in operations research, but I have
> never dealt with such a large problem before. I've never worked with
> Postgres before either. The deadline for this project is the first
> week of June.
>
> Before I begin using pgrouting to develop this solution, I wanted to
> ask for your thoughts on the feasibility of this approach, any advice
> you have, or issues you foresee.

Hi Andy,

Yes this is a big project! It might be easier to think about this 
problem by breaking it into discrete modules. pgrouting is only one 
small piece of this puzzle and to a large extent you can solve most of 
this without pgrouting. For example start by solving the problem using 
straight line distance between the locations. This is a rough 
approximation of the problem but it eliminates pgrouting from the 
problem initially. If you can solve the problem this way, then adding 
pgrouting back into the problem you can use it to compute the drive time 
distances between locations and then to compute the final routes.

Doing this will allow you to focus on the OR problem of allocating 
clients to vans based on the appropriate criteria. Since your client 
locations are relatively static you can pre-compute the distance matrix 
and store that in a table for access. You can easily add and remove 
clients from the table as needed. Then your OR code can use the distance 
matrix as required. In fact you could cache all the routes when you 
compute the drive times between the various locations so all you would 
need to do is extract the cached route when you arrived at your final 
solution.

One thing you need to consider is what street data are you going to use 
to feed into pgrouting for computing the routes. Tiger data is not use 
in this regard. You might be able to use OSM data depending on coverage 
area. You might also want to look at Navteq data if the area is small 
enough and you have some funding for the data.

-Steve