I have a design project for an engineering design course, the goal is to design a tunnel system beneath the Queen's University campus (in Kingston, Ontario). Its a several person assignment, and my role is to plan out the route of the tunnels (to just the major buildings).
My question is, which algorithm should I use? I've done some reading but the best I could find is Prim's algorithm or Kruskal's algorithm, which don't really help when considering foot traffic, as some buildings will be ridiculously far apart. If anyone knows of related algorithms that I could implement relatively easy (been programming mostly as a hobby for 4 years now), any suggestions would be appreciated.
I've done some reading but the best I could find is Prim's algorithm or Kruskal's algorithm, which don't really help when considering foot traffic, as some buildings will be ridiculously far apart.
You can either optimize the amount of tunnel that will need to be dug or the average distance that a user will need to traverse inside the tunnel. These are competing priorities, so you probably won't find a solution that's optimal by both metrics.
Which do you think is more important? You have to decide.
how realistic is it? Do you have obstacles like underground floors of the buildings, water pipes, etc?
Does it have to be done with an algorithm at all?
Without knowing an algorithm for this, I would be tempted to do this:
1) put a point in the exact center of all the points to be connected.
2) connect the center to every point
3) connect the perimeter
4) combine and tweak any tunnels that are approximately side by side / redundant (will take some thought and logic)
4) evaluate this result and see if it even remotely makes sense.
Thanks for the responses. I don't think jonnin's response will work, just because of the very large amount of tunneling necessary for it, as the cost-effectiveness will plummet.
I recently had an idea, where I would do this:
1. group all the points in pairs, such that the least amount of tunnel is dug between them (with some modification of kruskal's algorithm?)
2. find the midpoint of each of the pairs, and connect the midpoints in a similar manner to step 1.
3. find the midpoint of each of the lines determined in step 2, and repeat until all points are connected.
4. remove any overlapping tunnels (probably incorporate this into the previous steps).
5. manually go through and tweak the map
I just came up with this idea a few hours ago, but it should provide a balance between connecting all the buildings with short amount of tunnels, and not making the walking distance unreasonable.
let me know if anyone has an idea for a modification to this.
For the questions asked:
It should be realistic enough, such that it doesn't use an unreasonable amount of money, but the overall project will be far too expensive to actually construct, so I don't need to use the "most efficient" algorithm.
It doesn't have to be done with an algorithm, but bonus marks are awarded for writing a program as a model and I think that I should be able to write the above program without too much effort.
it should not be cost inefficient if you combine 'near' tunnels. For example if 2 buildings are within N feet of each other, use 1 tunnel from center to one and they can take the perimeter connector to the other. If the perimeter is too expensive, you can judiciously remove long pieces of it and leave only short connectors on the edges, playing with that too. This is part of playing with step 4 ... you have choices here to max/min your cost vs utility etc.
You will notice that what you propose and what I propose are very, very similar. They both key off midpoints vs edges. It gets you a starting point where you can either make the algorithm complex and configurable to generate several answers or you can generate and hand-tune. I highly recommend making the program able to generate several answers to consider, though.
multiple midpoints should be better for very large projects spanning a complex geography. That is a good idea; I had visualized a smallish project of just a few buildings where 1 hub seemed ideal. Another thought... run the thing N times and remove each point from the list. That is, run it with points abcd, bcde, acde, etc as well as abcde. See if throwing out just 1 building makes a huge difference, and if so, manually solve the odd building somehow around the solution it gives.
So the assignment was pretty open ended - the topic was of my group's design. My plan was to use a map along the lines of this: http://www.queensu.ca/campusmap/sites/default/files/assets/main-campus_0.png and assign coordinates to the buildings with high foot traffic (I haven't compiled the list of included buildings). I could then use google maps to generate a "scale" based off of the lengths of University Ave, Barrie St., etc (as they're pretty straight and can be measured easily). Sorry if this is a bit poorly defined, but I've been busy with midterms.
And in reply to Jonnin:
I see what you mean, I'll take a look at your method, maybe modify mine a bit. If time (and the page limit) permits, I'd like to do a "comparison" of a couple algorithms to find an efficient route, similar to what you suggested, just on a smaller scale. A similar method I thought of was to use Prim's algorithm and connect a few of the very far apart buildings together. Only issue (with my idea and yours) is as you pointed out, the sheer number of buildings (I'm going to need to include at least 25, just counting the main residences and lecture halls).
How are the tunnels to be connected? Main building basement access? Above ground access? Either? What other access points are expected?
What is the primary purpose of the tunnels?
Do you care about costs?
What about existing infrastructure (as mentioned by helios)? Should I assume that tunnels are not to intersect building foundations except as an underground access point?
Do you have any statistical data about traffic and/or building use? How much is the university accessed from surrounding suburbia? What buildings are best benefited from alternate access points? This question (and the question about costs) are really the most important here. Oh, and the purpose(s) of the tunnels.
Presumably tunnels need not follow existing routes. For example, I presume there would be no point in making a tunnel that follows Stewart Street. Is this correct?
So just so you all know - I can't use any work that you guys do, so I'll be doing all this on my own, and probably post my conclusion when I'm done (after I submit so as to not trigger the plagiarism software they use).
Tunnels would be connected using buildings as intersecting points. There isn't any reason why buildings can't be intersected by multiple tunnels, the intersection would probably be moved over a few meters so as to not interfere with foundations like you said, but that would be (pretty much) negligible to the length of tunnels, and would be a separate cost that I am not responsible for calculating (there's three other people working on this project).
Costs should be reduced as mush as possible, but as the purpose is to provide an efficient and safe (we may be hyperbolizing the effect of black ice a little) method of transportation, a significantly shorter route justifies a larger cost.
Tunnels don't need to follow existing paths/roads, but I'm assuming that they will likely follow a similar pattern as the roads weren't placed randomly.
let me know if this answers your questions or not, and thanks again for the replies.
I can probably plot the main entrances of the buildings on a map, but I don't believe its necessary? The idea is for the tunnel system to enable a student to go to most of his/her classes without going outside. Thus, if the result simply connects all the points, that should be fine, as a staircase can lead the student into the building of their class.
I haven't found any statistical data about traffic or building use, but plan on getting a rough estimate based on the number of classes/labs/tutorials/etc hosted in each building per week (if such information is readily available).
Haha, yeah, I was planning on adding the residences and cafeterias.
What I mean't about them not being random is that they were likely plotted with the same idea as me - to make an efficient route balancing walking distance and road costs, meaning that, if my method is correct, the tunnels and roads will likely follow a similar pattern.
This isn't an assigned school project - the project was to just make up a project that can be modeled by four group members, I just came up with this idea because I wanted an excuse to try more complex programming problems (the programming class here is a joke).
Its an excellent project.
One last thought... if you did a 3-d voxel map (volume pixel) you could use that to mark areas to avoid (foundations, underground pipes, whatever obstacles, even that old tree in the middle of it all that every campus has... cutting out its roots might not go over well). These are expensive to do but you have the liberty of making each voxel quite large (reducing the computational costs) even something like 10 foot cubed. This can also be done for this project on a 2-d mapping with the same idea... the point is just to somehow have a 'no go here' marker.