3

I have stolen diamonds in a lot of different places. The places are on a coordinate system (x,y) where each place is named after a number and have an d-time for example:

Name  X  Y  dT
1   283 248 0
2   100 118 184
3   211 269 993
4   200 200 948
5   137 152 0
6   297 263 513
7   345 256 481
8   265 212 0
9   185 222 840 
10  214 180 1149
11  153 218 0
12  199 199 0
13  289 285 149
14  177 184 597
15  359 192 0
16  161 207 0
17  94  121 316
18  296 246 0
19  193 122 423
20  265 216 11

dT stand for due time and it's given for each place, which is the fixed time when we need to get the diamonds back before the thief move their hideout away.

Starting point is always 1.

I need to visit all places only once and get the diamonds back such that the total delay is minimized. Distance is calculated with Euclidean distance rounded to its closest integer. The arrival time for each places is calculated as in distance + previous distance. The delay for each place is arrival-due and the total delay is the sum of the delays between places.

If the police can get the diamonds before the due time of that place, then the delay is equal to 0; otherwise, the delay equals the difference between the time of arrival and due time of the place.

My mission is to find the right order in which the police can visit each place once that minimizes the delay for two larger instances.

I think I'm pretty much close to an answer myself but I would love to know how would you solve it and also to get a better understanding of the math behind it to be able to program it better.

Here are my codes that calculate everything, the only thing missing is the way to find the right order :

#------------------------------------------------------------------------

poss=[(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)] # the order

here=[]
for p in range(len(poss)):
    tempos=[]
    for o in range(len(index)):
        point=poss[p][o]
        valuez=order[point-1]
        tempos.append(valuez)
    here.append(tempos)

#//DUE//

due =[[item[b][3] for b in range(len(index))] for item in here]

#//DISTANCE//

x_ = [[item[b][1] for b in range(len(index))] for item in here]
y_ = [[item[b][2] for b in range(len(index))] for item in here]
z = [list(zip(x_[a],y_[a])) for a in range(len(x_))]

dis = []
for aa in range(len(poss)) :
    tempor=[]
    for i in range(len(index)-1):
        firstpoint = z[aa][i]
        secondpoint = z[aa][i+1]
        distance = round(np.linalg.norm(np.array(secondpoint)-np.array(firstpoint)))
        distance = int(distance)
        tempor.append(distance)
    dis.append(tempor)


#//ARRIVAL TIME//
#Arrival time is the sum of the pv distance.

arrival = []
for v in range(len(poss)):
    forone = [0,dis[v][0],]
    for r in range(len(index)-2):
        sumz = dis[v][r+1] + forone[r+1]
        sumz = int(sumz)
        forone.append(sumz)
    arrival.append(forone)

#//DELAY//

delay=[]
for d in range(len(poss)) :
    tempo=[]
    for q in range(len(index)):
        v=arrival[d][q]-due[d][q]
        if arrival[d][q] <= due[d][q]:
            tempo.append(0)
        else :
            tempo.append(v)
    delay.append(tempo)

#//ORDER//
#goal is to find the right order that minimizes the delay for two larger instances.

total = [sum(x) for x in delay]
small= min(total)
final=here[total.index(small)]

print(small)
teabubble
  • 37
  • 5
  • Could you clarify: 1. If you can't get to a location before the delay time, does visiting the location still mean you get the diamond from it, or has the thief taken it. 2. What location do the police start at – 0liveradam8 May 25 '19 at 00:06
  • @0liveradam8 starting point is always 1 , visiting each location means you get the diamonds. if you don't get to the location before the delay time then it's arrival - dT = delay time of the place ( you can also check it in my codes ) – teabubble May 25 '19 at 00:10

1 Answers1

0

You could solve this by implmenting the travelling salesman problem, but it needs a simple modification. In the TSP, the cost of moving to the next location is just its distance from your current location. In your algorithm, the cost is calculated:

if current_travelling_time < dT then
    cost = 0
else
    cost = dT - current_travelling_time

The total cost of each path is calculated by summing up their costs. The path with the minimum cost is the one you want.

Solving this can be programmed simply by calculating these costs across all permutations of locations, bar the first location.

Note that this is very computationally expensive, so you should consider dynamic programming.

For this brute-force approach, see https://codereview.stackexchange.com/questions/110221/tsp-brute-force-optimization-in-python. The cost would need to be calculated differently, as I've mentioned.

0liveradam8
  • 752
  • 4
  • 18
  • Unfortunately, trying all permutations is almost impossible as it's over billions. I have already tried to solve it using brute force and genetic algorithm but the total delay was still way too big :( – teabubble May 25 '19 at 01:26
  • As I've said, [dynamic programming](https://stackoverflow.com/questions/30114978/how-to-implement-a-dynamic-programming-algorithms-to-tsp-in-python) would reduce the complexity, which would be the simplest implementation for an exact algorithm. This should be sufficient for 20 locations. Past this, you can use a [branch-and-bound](https://stackoverflow.com/questions/2154171/tsp-branch-and-bound) algorithm. Past this, the [wikipedia page](https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution) for the problem has a variety of exact and estimated solutions to use. – 0liveradam8 May 25 '19 at 17:01