Good morning,
As the title says, how do I create a routing with multiple stops? Currently I have uploaded on Postgis the nodes and edges of the road graph but I want the stops to match the housenumbers. The ideal work would be to implement the time windows of each stop and the capacity of the vehicle (once reached the max capacity, the vehicle must return to a point 0, resume the route and then complete it). Which is the best algorithm to solve this problem?
Here is a small area of housenumbers and nodes (orange points) on QGIS
In general, you need to figure out the pgRouting working graph.
Based on your small explanation:
For example, suppose that you have one street segment as a graph (from one intersection to another) and the houses around it:
One “segment” graph
1 3 5 7 9 11
A-------------------------------------B
2 4 6 8 10 12
So now you have a 13 segment graph.
A-1-2-4-3-5-6-7-8-9-10-11-12-B
PostGIS/pgRouting do not have a function that does this. you would need to create your transformation function (if needed).
About what algorithm to use
You might as well see and do the examples of the proposed functions “with Points”
But if you are talking about pgr_pickDeliver then you might as well use it with the pgr_withPointsCost function to get the matrix values needed as input
With some funding it might be possible to implement such a function.
There are other things that can make such a use case more complicated, for example stop points need to be accessed from a certain side of the road, ie. because loading can be done only on the left or right side.
One remark regarding your data: it seems that you have a lot of stop points along each road segment.
It might simplify your problem, if you can allocate all points to a street segment and handle all stop points of that segment or none of them.
Hello Daniel,
thank you for your reply and thank you again Vicky for your help (I thought
I sent the message here but I think I sent a private message by mistake)
Anyway yes, I really have many points and yes, it is waste collection (I am
Italian and the English translation of the type of collection should be
Kerbside collection)
I have read about the Chinese Postman Problem but I guess it is something
terribly complex (I tried the QGIS Chinese Postman Solver plugin but with
very few results).
As I replied to Vicky in private (and I apologize again because I would have
preferred to put my answer here so that everyone could read it), I was
thinking to use the withPointsCost function to get the matrix values as
input for the pgr_pickDeliver but I still have to understand if it can
consider the vehicles capacity and time windows.
Anyway, I will certainly try to better inform myself about this CPP.
I'm just a beginner who wants to learn a lot from pgRouting.
My main goal is to give to the waste management manager optimized routes for
each vehicle.
Obviously the ideal would be to create a routes with all these multiple
stops but I was thinking, could it be an easier alternative to get from him
all the already established city stops and find the best routes for each
vehicle with pgRouting only passing through specific nodes and edges? So I
could bypass the part related to house numbers and give the manager only the
optimized routes.
