Traveling Sales Drone

Computer Science Level 4

Amazon is testing out their new Prime Air service, and they want to plot a path for the drone to make its deliveries.

Dispatch center: $(0,0)$

Packages: $(7,9), (-9,7), (1,22), (-6, 19), (-8, 1), ( 0, 1 )$

Assuming that the coordinates given are in km, what is the minimum distance the drone must travel to deliver all the packages and return to dispatch (rounded to the nearest km)?

The answer is 60.

5 solutions

Discussions for this problem are now closed

Ramchand Rajasekaran
Jan 16, 2014

Nicely Named as Travelling Sales Drone!! Yes the problem sounds akin to the "Travelling Sales Man" problem..

We can name the points as A,B,C,D,E,F in the order they appear ! Just plotting the points on a graph roughly gives you a picture like this

From that we can deduce that there can be 2 possible routes (that look shorter). They are ,
Origin -> F -> E -> B -> D -> C -> A -> Origin

Origin -> E -> B -> D -> C -> A -> F -> Origin

The first one sums upto 69.6 which can be rounded to 69 !

The second one sums upto 60.05 which can be rounded to 60 !

You can use Euclidean distance to calculate the distance between two points in a Graph!

Ramchand Rajasekaran - 7 years, 4 months ago

Can you formally prove the "they look shorter" part?

minimario minimario - 7 years, 4 months ago

You can use triangle inequality in geometry to prove that the diagonals are longer than the sides.

Samuraiwarm Tsunayoshi - 7 years, 4 months ago

It looks like your first path sums up to about 60.75, but I could easily be mistaken.
The second path is indeed the shortest.

Steven Perkins - 7 years, 3 months ago

Eric Zhang
Feb 23, 2014

The simplest way to do this problem is to simply bash through all the possibilities and calculate the distance for each.

Python solution:

import itertools

p = [(7,9),(-9,7),(1,22),(-6,19),(-8,1),(0,1)]

ans = float('inf')
for i in itertools.permutations(p):
    l = (0,0)
    d = 0
    for x in i:
        d += ((x[0] - l[0]) ** 2 + (x[1] - l[1]) ** 2) ** 0.5
        l = x
    d += (i[-1][0] ** 2 + i[-1][1] ** 2) ** 0.5
    if d < ans:
        ans = d

But isn't the complexity exponential then...

Cse Targate - 7 years, 3 months ago

No; it's O(n!), which is worse (O(c^n) is with dynamic programming), but it works finely for small cases like the one described in the problem.

Eric Zhang - 7 years, 1 month ago

Bill Bell
Dec 6, 2014

Using Python itertools module, as others have done, but used the sympy geometry abilities too, which saves the need to write Euclidean distance code.

Lokesh Sharma
Feb 2, 2014

Python Solution:

import itertools

class coordinate(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.conquered = False
    def getX(self):
        return self.x
    def getY(self):
        return self.y
    def __str__(self):
        return '(' + str(self.x) + ', ' + str(self.y) + ')'

def buildCoordinates():
    return [coordinate(7,9), coordinate(-9,7), coordinate(1,22), coordinate(-6, 19), coordinate(-8, 1), coordinate(0, 1)]

def dis(co1, co2):
    '''
    Returs distance between 2 coordinates
    '''
    return ((co1.getX() - co2.getX())**2 + (co1.getY() - co2.getY())**2)**0.5

def totDis(allCoordinates):
    totalDistance = 0
    for i in range(len(allCoordinates) - 1):
        totalDistance += dis(allCoordinates[i], allCoordinates[i + 1])
    totalDistance += dis(allCoordinates[0], coordinate(0, 0))
    totalDistance += dis(allCoordinates[-1], coordinate(0, 0))
    return totalDistance

bestDistance = 1000
allRoutes = list(itertools.permutations(buildCoordinates()))
for i in allRoutes:
    if totDis(i) < bestDistance:
        bestDistance = totDis(i)
print bestDistance

Maedhros 777
Jan 19, 2014

Python code:

import math
cities=[(7,9),(-9,7),(1,22),(-6,19),(-8,1),(0,1)]
min_dist = 100000000000000

    def explore(visited, total_distance):
        global cities, min_dist
        if len(visited) == 7:
            min_dist = min(min_dist, total_distance + math.sqrt(visited[-1][0]**2 + visited[-1][1]**2))
            return
        for city in cities:
            if city not in visited:
                explore(visited + [city], total_distance + math.sqrt((city[0] - visited[-1][0])**2 + (city[1] - visited[-1][1])**2))

explore([(0, 0)], 0)
print min_dist

i am getting 58 and have no idea y

int min=999;

void fx1(int set[10],int arr[10][10],int pat[10],int co,int c,int n,int j,int fin[10]){

int i;

if (c==n) {


    printf("\n%d\n",co+arr[j][0]);
    for (i=0; i<=n; i++) {

        printf(" %2d ",pat[i]);


    }
    printf("\n");
    for (i=0; i<=n; i++) {

        printf(" %2d ",arr[pat[i]][pat[i-1]]);


    }

    printf("\n");

//-----

    if (co+arr[j][0]<min) {
        min=co+arr[j][0];
        for (i=0; i<=n; i++) {
            fin[i]=pat[i];
        }
    }
}
for (i=0; i<n; i++) {
    if (set[i]==0) {
        set[i]=1;

        pat[c]=i;
        c++;
        fx1(set, arr, pat, co+arr[j][i], c, n, i,fin);
        set[i]=0;
        c--;
    }
}


// printf(")");

return;

}

int main(){

int set[10]={0},arr[10][10]={0},pat[10]={0},fin[10]={0},c,n,j,i;


printf("\n Enter the n\n");
scanf("%d",&n);
c=0;


for (i=1; i<n; i++) {
    for (j=0; j<i; j++) {
        printf("i=%d j=%d\n",i,j);
        scanf("%d",&arr[j][i]);
        arr[i][j]=arr[j][i];
    }
}


for (i=0; i<n; i++) {
    printf("\n");
    for (j=0; j<n; j++) {
        printf("%2d\t",arr[i][j]);
    }
}


c=1;
set[0]=1;

fx1(set, arr, pat, 0, c, n, 0,fin);



printf("the final min path is ->\n");

printf("\n%d\n",min);
for (i=0; i<=n; i++) {

    printf(" %d ",fin[i]);


}

}

Vishnu Swaroop - 7 years, 4 months ago

Are you going back to the dispatch point in the end?

Lokesh Sharma - 7 years, 4 months ago

It appears you are truncating each path length, instead of calculating the length as a double, adding them up and approximating the result.

Steven Perkins - 7 years, 3 months ago

Traveling Sales Drone

The answer is 60.

5 solutions

Discussions for this problem are now closed

0 pending reports