Route planning algorithm

[blanm]

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.
Thanks!

[helios]

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.

[jonnin]

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.

[blanm]

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.

[jonnin]

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.

[helios]

Just out of curiosity, do you have the input dataset? I'd like to try my hand at cracking this one.

[Duthomhas]

Yeah, give us the assignment too.

[blanm]

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).

EDIT: the main buildings are listed here: https://my.engineering.queensu.ca/International-Students/QEEI/images/campus-03.jpg It's missing some of the smaller residences but should be good enough for a rough trial if any of you want to give it a try.

[Duthomhas]

Additional useful information:
https://www.google.com/maps/dir/''/Queen's+University,+99+University+Ave,+Kingston,+ON+K7L+3N6,+Canada/@44.2257194,-76.4959693,865m/data=!3m1!1e3!4m8!4m7!1m0!1m5!1m1!1s0x4cd2ab0fccd925e9:0x268a8a4f5c257211!2m2!1d-76.4951412!2d44.2252795

Questions

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?

Umm, that's all for now.

[helios]

It would also be useful to know where the main entrances to each building are, if the tunnels will exit to the outside.

[helios]

I've preprocessed OP's data for easy consumption. I've also taken the liberty to invent some entrances by looking at the map.
You can get the data here:
https://drive.google.com/open?id=1FCYdmtxq-le3J1-GjAnE0yQ7U_oiBPMQ

[blanm]

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).

[jonnin]

well, dorms & the food building won't have any classes but probably have significant traffic :) Might be nice to have an entry near major parking lots also.

Roads/walk paths are not random but they also route around things. Could be a lot of the tunnels are totally different from the surface.

This is possibly the coolest school problem I have seen in years. Have fun, and do please share after its all done.

[blanm]

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).

[jonnin]

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.

[blanm]

I see, I'll look into that, but it might turn into a personal project at that point because of time constraints.

[blanm]

it's been a couple days, been a bit busy with other work but just finished it:

/*
 *  Tunnel route planning algorithm
 *  Done as part of the MEA2 assignment for APSC 100 Module 2 of Queen's University Engineering Program
 *  (c) Mitchell Bland 2017
 */

// included Libraries
#include <string> // for string object -> only used in file I/O
#include <iostream> // cout
#include <vector> // vector object
#include <cmath> // sqrt(), etc
#include <fstream> // ifstream -> used for file I/O

// number of points
#define N 26
using namespace std;

struct point
{
    double x, y;

    // used to shorten print statements
    void print()
    {
        cout << "(" << x << ", " << y << ")";
    }
};

// less of a vector class than a line class, as it has two points (a line is a vector/slope and a point)
struct vect
{
    point start_pt;
    point end_pt;
    double x,y;

    // Yes, I know that I should put my functions at the bottom of the code.
    // I did this because they're all pretty short

    // would use class ctor, but needs to be called repeatedly to reduce # of variables
    void construct(point a, point b)
    {
        start_pt = a;
        end_pt = b;
        calc();
    }

    // calculate points of vector
    void calc()
    {
        x = end_pt.x - start_pt.x;
        y = end_pt.y - start_pt.y;
    }

    // calculate magnitude of vector
    double mag()
    {
        return sqrt(x * x + y * y);
    }

    // calculate midpoint of vector
    point midpoint()
    {
        // could also use x = start_pt.x + 0.5 * x;
        point val;
        val.x = (start_pt.x + end_pt.x) / 2;
        val.y = (start_pt.y + end_pt.y) / 2;
        return val;
    }
};

int main()
{
    point pts[N];
    vector <vect> tun_map;

    // FILE INPUT TO GET POINTS
    string line;
    ifstream myfile("points.txt"); // create file object
    if (myfile.is_open()) // checks if file works
    {
        int index = 0;
        while (getline(myfile, line)) // checks if still open while moving line of txt to line string
        {
            point temp;
            // convert ASCII text to numbers
            temp.x = (line[0] - 48) * 100 + (line[1] - 48) * 10 + (line[2] - 48);
            temp.y = (line[4] - 48) * 100 + (line[5] - 48) * 10 + (line[6] - 48);
            pts[index] = temp; // put point in array
            index++;
        }

        myfile.close();
    }
    else cout << "bad file" << endl;

    // transform map points into a vector to allow for looping
    vector <point> curr_pts;
    for (int i = 0; i < N; i++)
    {
        curr_pts.push_back(pts[i]);
    }

    vect test;
    bool cont = true;
    while(cont)
    {

        int num = curr_pts.size(); // number of points - set to variable due to # of usages
        vector <point> new_pts;
        vector <int> used_i;

        // if num is odd -> extra point. Move it to end, and decrement num to avoid errors
        if (num % 2 == 1)
        {
            new_pts.push_back(curr_pts.at(num-1));
            num--; // insure even
        }

        // increment thru first point
        for (int i = 0; i < num; i++)
        {
            // variables
            double min_dist = INT_MAX;
            int min_dist_i = i;
            vect temp;

            // check if already used
            bool used = false;
            for (int k = 0; k < used_i.size(); k++)
            {
                if (i == used_i.at(k)) used = true;
            }
            if(used) continue;

            // if not make sure it cant be again
            used_i.push_back(i);

            // increment thru second point
            for (int j = 0; j < num; j++)
            {
                // check if already used
                used = false;
                for (int k = 0; k < used_i.size(); k++)
                {
                    if (j == used_i.at(k)) used = true;
                }
                if(used) continue;

                // check if its the closest one
                temp.construct(curr_pts.at(i), curr_pts.at(j));

                int temp_dist = temp.mag();
                // if closest set it as such
                if (temp_dist < min_dist)
                {
                    min_dist = temp_dist;
                    min_dist_i = j;
                }
            }
            // reconstruct temp based on minimum dist
            temp.construct(curr_pts.at(i), curr_pts.at(min_dist_i));

            // add vector to map and eliminate j value from list
            tun_map.push_back(temp);
            used_i.push_back(min_dist_i);

            // push back midpoint of tunnel for next round
            new_pts.push_back(temp.midpoint());
        }

        // loop thru vectors and assign values to include new lines. This is done to allow easy looping
        curr_pts.clear();   // erase current points so as to not have an infinite loop
                            // *definately* didn't add this after several minutes of debugging
        for (int i = 0; i < new_pts.size(); i++)
        {
            curr_pts.push_back(new_pts.at(i));
        }
        cont =  !(curr_pts.size() == 1);    // if only 1 point remaining, its the midpoint of the last vector drawn
                                            // otherwise continue
    }

    double tot_dist = 0;
    // prints the connected points, the vector they make, and the magnitude
    for (int i = 0; i < tun_map.size(); i++)
    {
        tun_map.at(i).start_pt.print();
        cout << " + "; // yes I know it's not correct to "add" points but this makes sense to me
        tun_map.at(i).end_pt.print();
        cout << " = ";
        cout << "[" << tun_map.at(i).x << ", " << tun_map.at(i).y << "] -> ";
        cout << tun_map.at(i).mag() << endl;
        tot_dist += tun_map.at(i).mag();
    }

    cout << tot_dist << endl; // units = pixels
    cout << (tot_dist / sqrt(13*13 + 265*265)) * 300 << " meters" << endl; // units = meters
    return 0;
}

Sorry if the code is a bit rough, a lot of my console debugging lines are still in because I literally just finished 5 minutes ago. I'd be happy to take feedback on the code if anyone has any comments, just keep in mind that this isn't a programing class, they won't mark the actual program for efficiency, etc.
On one of the last lines, I use this: (tot_dist / sqrt(13*13 + 265*265)) * 300 . That's just unit conversion. I used google maps to calculate the distance from Barrie/Stuart to Barrie/Union, (300m), then used GIMP (a Photoshop software) to select all my points in terms of pixels on this map: https://drive.google.com/file/d/1HbdITe_2XW3Cg3wLZfyRWOwPsUvF1R7y/view?usp=sharing, as well as points for the two intersections, then did basic math to determine a "conversion factor". I know my method is inaccurate as google maps is +/- 50m (if i remember correctly), but its the best I have so far.
The file I used was this: https://drive.google.com/file/d/1O4eoFKcRUjOX4dkn2LiE5LTz21GITkuq/view?usp=sharing

EDIT:
replaced the code with slightly nicer-looking code without all the console debugging. I need to actually test the program by drawing out each of the vectors on a graph, but the total distance seems about right (I predicted about 4km, and got 4.3) so hopefully it's OK.

[jonnin]

you have to watch google maps, they are not adjusted correctly. There is a 3+ point process called georectification where you can take a tool (the one I had is not available to the public), click on 3 (or more, more is better) known points and enter their gps coordinates, and run the program and it will twist and stretch the image to be correct gps coordinates which can be back fed directly to distances. I don't know if you just did a crude form of this technique and if it got you close enough, but that is one way to deal with the problem. If this is your actual school or a site near you, you can take a phone or something with gps and pick off some points like a mailbox or flag pole or the like. Its tedious. (this is for the satellite maps, of course, where you can see little objects to use for references).

[helios]

What would be the point of that? At these distances the curvature of the Earth causes such a tiny error that it's not even worth considering.

r = 6371000 m
d = 500 m
y = sin(d/r)*r
x = (1-cos(d/r))*r
d' = sqrt(x^2+y^2)

d-d' ~= 10^-7 m

Do you have a GPS capable of giving you a fix down to a tenth of a micrometer?

[jonnin]

its not just the earth curve, it also fixes some issues with the images. The free sat maps can be off by several meters, caused by various issues.