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.
Thank you for your help.
Andy Carnevale
carnevalem@gmail.com
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
Steve,
Thank you for your response. The approach you described is similar to
what I was also considering, except I was planning on using Google's
Distance Matrix API
(http://code.google.com/apis/maps/documentation/distancematrix/) to
pull the time-distances between clients. Every morning, when that
day's roster is confirmed, I would generate a graph containing that
day's clients. Doing this would reduce it to an OR problem to
determine good routes.
However I was considering pgrouting because its seems like the DARP
branch (http://www.pgrouting.org/docs/1.x/darp.html) is already
capable of making calculations like this. Perhaps I misunderstanding
pgrouting's capabilities?
Andy
On 2/27/2012 6:49 PM, Andy Carnevale wrote:
Steve,
Thank you for your response. The approach you described is similar to
what I was also considering, except I was planning on using Google's
Distance Matrix API
(http://code.google.com/apis/maps/documentation/distancematrix/) to
pull the time-distances between clients. Every morning, when that
day's roster is confirmed, I would generate a graph containing that
day's clients. Doing this would reduce it to an OR problem to
determine good routes.
However I was considering pgrouting because its seems like the DARP
branch (http://www.pgrouting.org/docs/1.x/darp.html) is already
capable of making calculations like this. Perhaps I misunderstanding
pgrouting's capabilities?
Ok, DARP might be able to do this also. I just read through the docs on it at the link above and it does sound like it should be able to do a lot if not all of what you need.
I will say that I have not tried to use the DARP package, so I'm not aware of the details. I think this also needs to be passed the distance matrix. It would be great to see this getting used in a real world application.
Over the last couple of years we have had a lot of code developed in branches that needs to be pulled into the next release when ever that is.
-Steve