I need some guidance on an optimisation problem. I have a case similar to sewer piping in a housing estate. I have many origin points (houses - ‘A’ points) and (in my case) a central reservoir . I need to connect all houses to the central reservoir. For the same of simplification, I will consider the reservoir as a selection of destination (‘B’ points).
However, there are some rules flow must be considered:
Small pipes need steep incline angles, large pipes do not
Small pipes are cheap, large pipes cost more
Joints, Elbows, Tees etc all have costs that need to be considered.
The solution needs to take ALL ‘A’ Points, and join them with ANY (but not all) ‘B’ points. The algorithm should reward the use of shared nodes (elbows, tees etc) to avoid running many parallel lines.
I thought I might be able to break this up into 2 parts - one is the path mapping, the second is the pipe sizing. But I now feel these need to be solved simultaneously.
do you have a “hands-on” example that you could share here?
I’m asking because, even if your explanation is pretty clear and well detailed, there are many factors that would influence the approach to this problem
for instance, it’s not very clear to me if there is a particular set of paths the trajectories must follow, how complex that paths are, and “at which point / how” you determine if a given pipe is large or small based on the slope
also, the possibility of many starting-points converging to the very same destination-point can for sure be scripted in terms of weights that represent the “convenience” of a given solution
but if you are able to evaluate the cost of a certain solution only after it’s fully executed, then you are probably steering toward a brute force, or semi-brute force situation, that might not be very appealing in terms of calculation times if you are working with large data sets
I’ve added multiple start points and it runs Dijkstra’s algorithm on each start point, with a shared end point. But the paths have no interaction between one another.
Visually, we can see some easy improvements on the result (yellow mark ups).
(NOTE: the GH file includes some consideration for maximum allowable slope. I’ve set this very high to ignore it)
The set of paths would be nominated with a mesh (or some other convenient method) similar to the image above. This gives freedom to alter the resolution of the mesh, and include/omit regions that might cause other issues.
The pipe size / incline angle would need to be defined with a function or lookup table/list.
Each pipe size will have a different cost. Each junction (elbow, Tee etc) will have a cost depending on the pipe sizes - we could simplify this by adding a fixed price.
I think there would be some benefit to figuring out a optimal or semi-optimal path even if we neglected the pipe sizing problem initially.
