Visit each drifting tracker

Question

Your job is to replace the battery packs on many floating fish tracking devices in the shortest time. You must leave your base in the base helicopter and visit each tracker once, then return to the base.

Finding the optimum route is known to be hard, but there is an additional difficulty! Each tracker has a drift velocity (which will be assumed to be a constant for the day).

This is the standard travelling salesman problem with the added challenge of moving nodes. It should be easy to find a valid tour. The primary challenge is in developing an algorithm to find a near-optimal tour. I predict that it will not be possible to find a perfect tour with the current N=300 (but I would love to be proved wrong).

Rules

Your program will be supplied with a string of tracker data on STDIN or via a command line argument. You should find a route that visits each tracker exactly once and returns to base. The output should be a white space separated list of tracker ID:time pairs.

• Position is given in Centimetres (cm).
• Time is measured in seconds starting with t=0.
• Velocity is given in cm/sec.
• Each tracker ID is 1 to 8 upper case letters.
• The base with ID "BASE" is located at (0,0).
• All number values for input and output use signed integers.
• The input is one or more white space or slash separated trackers.
• Each tracker will have ID:x,y,vx,vy format (eg: A:566,-344,-5,11)
• At time t, a tracker will be at (x+vx*t, y+vy*t).
• The helicopter must never exceed 5000 cm/sec speed (180 km/hr).
• The output should be white space separated visits in time order.
• Each visit should be in ID:time format (eg: A:5723)
• The last visit in your output must be the base (eg: BASE:6120)
• If more than one tracker is at the same position, it takes zero time to move between them.
• The standard loopholes are forbidden.

Example dataset

A:77000,88000,-120,80 B:52000,-12000,0,-230 C:-140000,-23000,-270,110

Example non-optimal solution:

A:30 B:60 C:120 BASE:160

Note that A:30 B:60 C:120 BASE:130 would be invalid because the helicopter would have to fly at 17268 cm/sec to get back to base in 10 seconds.

Test dataset

AA:-164247,-378265,182,113
AB:-1494514,-385520,-25,80
AC:-744551,832058,-13,-123
AD:-930133,1598806,97,177
AE:-280777,-904936,-48,305
AF:-855362,-10456,-21,-89
AG:880990,154342,175,-100
AH:-319708,-623098,172,-17
AI:620018,-626908,-19,-164
AJ:-990505,164998,18,-120
AK:379998,310955,191,59
AL:-977441,-130531,107,-234
AM:-766893,14659,162,-198
AN:-502564,-95651,261,306
AO:661306,-98839,231,263
AP:-788211,254598,24,-249
AQ:851834,-1004246,-45,75
AR:698289,-965536,-8,-134
AS:-128295,701701,180,-241
AT:1423336,1359408,-6,173
AU:445274,-527619,231,319
AV:358132,-781522,26,-132
AW:736129,807327,0,-137
AX:-174581,-337407,133,180
AY:-1533760,-215500,144,-111
AZ:-383050,82658,221,-14
BA:-1650492,548674,89,-63
BB:54477,-906358,440,181
BC:891003,623700,326,102
BD:-393270,1732108,155,-97
BE:411090,-859170,93,163
BF:554962,-298575,480,-100
BG:-695530,475438,244,283
BH:93622,-958266,153,-127
BI:-403222,389691,323,329
BJ:1585132,98244,-156,71
BK:713912,484912,158,97
BL:-1612876,317391,-5,-131
BM:-725126,-320766,30,-105
BN:-76091,-381451,-172,95
BO:-483752,970905,16,-170
BP:1585890,91873,-173,-19
BQ:-815696,-342359,-64,-121
BR:-129530,-606673,-66,-94
BS:-339974,-561442,-35,271
BT:1277427,1258031,13,-5
BU:1246036,-743826,144,-200
BV:494745,-522944,211,309
BW:776786,586255,6,-146
BX:-847071,-792238,-142,-199
BY:748038,863976,6,-109
BZ:-667112,634959,221,-174
CA:888093,900097,-107,-56
CB:113938,-1031815,-167,134
CC:-626804,504649,2,-151
CD:866724,941177,311,221
CE:-1632084,-1957347,38,116
CF:774874,804277,-4,-152
CG:468675,-239063,437,-141
CH:-1352217,-388519,-86,70
CI:-1006,921538,-6,-179
CJ:-1866469,68979,-1,133
CK:-1036883,1962287,124,-62
CL:760226,858123,478,56
CM:764838,493113,-27,-155
CN:-642231,-387271,48,198
CO:430643,646456,8,-138
CP:268900,-82440,294,-114
CQ:-1518402,-1782748,123,62
CR:5487,980492,-30,-151
CS:-749712,494682,-1,-113
CT:-1144956,124994,84,120
CU:-1855045,-612779,30,-35
CV:416593,-57062,-67,-140
CW:-1970914,-1984034,-27,153
CX:-606767,629298,-49,-144
CY:-792900,-696850,0,-123
CZ:1561820,-450390,37,21
DA:579688,355017,-186,-153
DB:1178674,1247470,-86,-54
DC:483389,-837780,321,27
DD:468021,-992185,20,253
DE:-38126,-386917,270,250
DF:707678,189200,-59,-179
DG:-1428781,1326135,-29,-148
DH:-1943667,1645387,22,140
DI:-399820,626361,29,-132
DJ:-2657,170549,94,-169
DK:-331601,917405,104,157
DL:1965031,350999,158,-114
DM:902640,986090,-66,-140
DN:540679,-544126,15,-121
DO:-524120,411839,-48,-120
DP:-134995,-876166,191,-128
DQ:359872,-991469,-164,-186
DR:-186713,-309507,14,-86
DS:1846879,-585704,133,64
DT:169904,945363,298,70
DU:-218003,-1001110,-70,109
DV:316261,266341,-63,-89
DW:551059,55754,-4,-94
DX:-514965,305796,304,-100
DY:162176,485230,-90,83
DZ:675592,-1508331,119,-20
EA:656886,38516,257,-111
EB:-201090,678936,5,-161
EC:-920170,-503904,-8,158
ED:-728819,-401134,-83,154
EE:-611398,-320235,-5,-102
EF:-612522,-259240,14,-154
EG:662225,-808256,478,165
EH:-468284,-720421,234,316
EI:-958544,-161691,-12,-97
EJ:839898,-631917,-25,-159
EK:745130,598504,-72,132
EL:412250,-456628,13,-104
EM:-737096,374111,172,35
EN:726052,-385153,-45,31
EO:-888906,-495174,24,-170
EP:-518672,-685753,-14,-102
EQ:440153,-211801,-46,-180
ER:464493,-1637507,-3,154
ES:701248,-512422,-33,-83
ET:-795959,426838,-29,-117
EU:307451,978526,445,124
EV:800833,66796,15,-176
EW:-623452,299065,-30,-117
EX:15142,-363812,445,245
EY:-701669,-556515,-8,-136
EZ:-1772225,890097,-140,-104
FA:-948887,-882723,-11,-157
FB:387256,-128751,151,7
FC:1066595,-641933,31,-23
FD:-823274,-812209,-67,-172
FE:923612,536985,21,-123
FF:-886616,-808114,-26,-153
FG:411924,-518931,-7,-138
FH:945677,-1038311,174,-59
FI:913968,81871,-5,-139
FJ:625167,708120,-44,-90
FK:-405348,893926,-10,-93
FL:-58670,415334,170,-155
FM:326285,671439,426,-237
FN:-775332,-81583,4,-164
FO:280520,360899,2,-150
FP:-406095,133747,26,170
FQ:-990214,-342198,30,-112
FR:938869,801354,397,198
FS:-7527,36870,-23,-111
FT:999332,-956212,143,16
FU:-86215,792355,-49,-87
FV:144427,378536,-4,-136
FW:-786438,638084,28,-77
FX:903809,903424,-102,-132
FY:-36812,-126503,16,-159
FZ:-1083903,1001142,-29,-110
GA:857943,-120746,135,-3
GB:545227,-151166,239,127
GC:-356823,674293,106,90
GD:977846,1003667,-53,106
GE:-866551,180253,-1,-170
GF:-688577,289359,-24,-161
GG:-256928,-481626,169,109
GH:590910,829914,25,-170
GI:568114,735446,-34,-172
GJ:1756516,-655660,140,138
GK:-1683894,-1417741,-163,-84
GL:-201976,-703352,201,217
GM:-271187,-836075,-24,-141
GN:809929,793308,70,324
GO:-403617,58364,432,-191
GP:-94316,227063,148,28
GQ:-930345,1587220,-129,-142
GR:-433897,58058,-75,255
GS:-780984,114024,-12,-160
GT:-403102,-1425166,158,-84
GU:-449829,-414404,-27,-125
GV:556480,72387,-34,306
GW:-959629,326929,327,-91
GX:250741,-992373,94,-121
GY:702250,1612852,-41,38
GZ:853191,857773,-62,-105
HA:674500,-225890,7,-152
HB:-1890026,-179534,-23,49
HC:398363,681200,31,-26
HD:-1896372,113239,-51,25
HE:599213,137473,10,-31
HF:-34537,750768,-18,-179
HG:-959544,-430584,-33,-117
HH:1283773,1606578,-8,-80
HI:-866804,108513,180,-74
HJ:765654,115993,23,-22
HK:554000,130015,18,-32
HL:-470089,-407430,38,191
HM:366977,556677,18,-134
HN:175829,545309,29,-146
HO:-263163,-235953,3,-169
HP:727495,567716,6,-135
HQ:121304,-9150,81,-157
HR:-1789095,-471348,-73,-9
HS:-799974,819873,51,-64
HT:-985175,1774422,70,-10
HU:516368,-227142,-33,-117
HV:655503,350605,-6,-92
HW:733506,-1967066,197,-62
HX:1339705,-1227657,-195,44
HY:-384466,-1932882,7,-93
HZ:-394466,-459287,132,95
IA:120512,-1673367,28,-167
IB:1294647,-1112204,35,133
IC:883230,734086,144,54
ID:-95269,435577,30,148
IE:-378105,-1147004,-6,190
IF:366040,-132989,339,-61
IG:-397775,-410802,-1,-84
IH:849353,-181194,-98,45
II:774834,-56456,-177,21
IJ:-441667,576716,-51,-82
IK:-309799,-673582,-34,-99
IL:605784,-903045,-179,103
IM:-379218,-958590,-6,262
IN:982984,947942,212,-28
IO:-477749,-472771,474,44
IP:-1381284,-1273520,131,139
IQ:672901,1298275,-116,150
IR:-816582,-693425,121,-265
IS:809060,-66216,-45,-165
IT:655913,723612,6,-102
IU:70578,-546308,496,219
IV:558122,41452,-20,-103
IW:237612,-1605017,154,170
IX:-1120980,-471873,-181,-134
IY:-1385384,36137,-14,15
IZ:1401932,-1692315,103,115
JA:1339559,1534224,123,46
JB:-963572,-554932,-13,-153
JC:1422496,-213462,-97,-63
JD:-74743,-909157,277,273
JE:-1364398,911720,185,-19
JF:831273,-645419,-61,-147
JG:-308025,-297948,-59,-107
JH:-737466,-424236,419,219
JI:234767,971704,375,89
JJ:-715682,-871436,395,-54
JK:-296198,-466457,11,227
JL:277311,-661418,27,-124
JM:113477,-763303,-61,-142
JN:198929,881316,358,67
JO:864028,-1735917,-168,-162
JP:193352,-46636,12,-171
JQ:-374301,967915,-27,-98
JR:-900576,1585161,-14,-154
JS:-855414,-201048,24,-150
JT:473630,412948,-80,68
JU:-358039,-730839,-18,47
JV:677652,-670825,-63,-146
JW:536063,-734897,-86,57
JX:344532,-594945,143,230
JY:218390,42085,406,-154
JZ:222495,-933383,440,-29
KA:993576,490730,448,13
KB:1383947,-1637102,-146,-175
KC:181730,-314093,-20,47
KD:1400934,502742,-77,-126
KE:1239862,1152873,144,102
KF:-156867,290487,5,-92
KG:947301,958346,-12,-124
KH:-1873578,815339,194,167
KI:1181091,882850,89,-122
KJ:-825910,-452543,369,9
KK:548963,-358292,390,117
KL:-940596,-200000,125,296
KM:463530,905548,-70,-95
KN:-7507,263613,-7,-145
KO:172069,-457358,-40,-113
KP:-206484,-214043,172,-4
KQ:620049,1844897,-158,192
KR:-988657,612294,452,-125
KS:-802234,611144,-34,-178
KT:231136,-858200,123,129
KU:1557166,943150,105,114
KV:-229389,-440910,-71,123
KW:-135216,1346978,15,136
KX:-43852,521638,-38,279
KY:112655,441642,-8,-105
KZ:525746,-216262,8,-124
LA:-985825,-345745,33,187
LB:-839408,-319328,-6,-136
LC:-12208,1899312,-168,149
LD:156476,-902318,69,325
LE:976731,-427696,310,165
LF:-809002,-255961,312,235
LG:-899084,484167,5,57
LH:-748701,426117,256,-21
LI:-711992,148901,-49,24
LJ:-519051,-440262,22,-105
LK:-310550,283589,88,151
LL:244046,-1751273,5,29
LM:1350149,-1524193,-96,-158
LN:-706211,-585853,-63,-122

Verifier

A program similar to the following verifier will be used to check the answers. You can use this program to check your answers before posting.

# PPCG: Visiting each drifting tracker
# Answer verifier for Python 2.7
# Usage: python verify.py infile outfile [-v]
# Infile has the given input string. Outfile has the solution string.
# v1.0 First release.

import sys, re
VERBOSE = ('-v' in sys.argv)
fi, fo = sys.argv[1:3]

def error(*msg):
    print ' '.join(str(m) for m in ('ERROR at:',) + msg)
    sys.exit()

indata = open(fi).read().strip()
trackdata = [re.split('[:,]', node) for node in re.split('[ /]', indata)]
trackers = dict((node.pop(0), map(int, node)) for node in trackdata)
shouldvisit = set(trackers.keys() + ['BASE'])

visittexts = open(fo).read().split()
visitpairs = [node.split(':') for node in visittexts]
visits = [(label, int(time)) for label,time in visitpairs]

fmt = '%10s '*5
if VERBOSE:
    print fmt % tuple('ID Time Dist Tdiff Speed'.split())
prevpos = (0, 0)
prevtime = 0
visited = set()
for ID, time in visits:
    if ID in visited:
        error(ID, 'Already visited!')
    tdiff = time - prevtime
    if tdiff < 0:
        error(ID, 'Time should move forward!')
    if ID == 'BASE':
        newpos = (0, 0)
    else:
        if ID not in trackers:
            error(ID, 'No such tracker')
        x, y, vx, vy = trackers[ID]
        newpos = (x+vx*time, y+vy*time)
    if newpos == prevpos:
        dist = speed = 0
    else:
        dist = ((newpos[0]-prevpos[0])**2 + (newpos[1]-prevpos[1])**2) ** 0.5
        if tdiff == 0:
            error(ID, 'Helicopters shouldn\'t teleport')
        speed = dist / tdiff
        if speed > 5000:
            error(ID, 'Helicopter can\'t fly at', speed)
    if VERBOSE:
        print fmt % (ID, time, int(dist), tdiff, int(speed))
    visited.add(ID)
    prevpos = newpos
    prevtime = time

if ID != 'BASE':
    error(ID, 'Must finish at the BASE')
if visited != shouldvisit:
    error((shouldvisit - visited), 'Not visited')

print 'Successful tour in %u seconds.' % time

Scoring

Your score will be your final time in seconds. Lower is better. The winner will be the answer with the fastest time on the test dataset after the return to base. In the result of a tie, the earliest entry will win.

Please post solutions with a "Language, Score: NNN" title, the code, and the output solution string (with several visits per line prefered).

Answer 1

Python, Score: 20617 17461

I do not have much experience with these types of problems and don't really know what the best known methods are, but I used a method which I've had moderate success with in the past and I'm interested to see how it compares to other answers.

from __future__ import division
from math import *
import itertools

class Visitor:
    def __init__(self,data):
        self.trackers = self.parse(data)
        self.weights = {}
        avg = 0
        for key in self.trackers:
            x,y,vx,vy = self.trackers[key]
            w = hypot(vx,vy)**2
            self.weights[key] = w
            avg += w
        avg /= len(self.trackers)
        for key in self.weights:
            self.weights[key] += avg
        
    def parse(self,data):
        result = {}
        for line in data.split('\n'):
            id,vars = line.split(':')
            x_str,y_str,vx_str,vy_str = vars.split(',')
            result[id] = (int(x_str),int(y_str),int(vx_str),int(vy_str))
        return result
    
    def convert(self,path,final):
        result = ""
        total_time = 0
        for (id,time) in path:
            total_time+=time
            result += "%s:%s "%(id,total_time)
        return result + "BASE:"+str(final)
    
    def time_to(self,target,begin,offset=0):
        bx,by,dx,dy = begin
        tx,ty,vx,vy = target
        bx+=dx*offset
        by+=dy*offset
        tx+=vx*offset
        ty+=vy*offset
        
        t = 0
        for inter in [1000,100,20,10,4,1]:
            speed = 5001
            while speed > 5000:
                t += inter
                cx,cy = tx+vx*t,ty+vy*t
                speed = hypot(bx-cx,by-cy)/t
            if speed == 5000:
                return time
            t -= inter
        return t+1

    def path_initial(self):
        print 'Creating Initial Path'
        path = []
        tracks = self.trackers.copy()
        remaining = self.trackers.keys()
        px,py = 0,0
        distance = 0
        
        def score(id):
            if len(remaining) == 1:
                return 1
            t = self.time_to(tracks[id],(px,py,0,0))
            all_times = [self.time_to(tracks[id],tracks[k],t) for k in remaining if k != id]
            return t*len(all_times)/sum(all_times)/self.weights[id]
        
        while remaining:
            print "\t{0:.2f}% ".format(100-100*len(remaining)/len(tracks))
            next = min(remaining,key=score)
            t = self.time_to(tracks[next],(px,py,0,0))
            path.append((next,t))
            for k in tracks:
                ix,iy,ivx,ivy = tracks[k]
                tracks[k] = (ix+ivx*t,iy+ivy*t,ivx,ivy)
            px,py = tracks[next][:2]
            remaining.remove(next)
    
        return path
        
    def path_time(self,ids):
        path = []
        total_time = 0
        tracks = self.trackers.copy()
        px,py = 0,0
        distance = 0        
        for i in ids:
            t = self.time_to(tracks[i],(px,py,0,0))
            path.append((i,t))
            total_time += t
            for k in tracks:
                ix,iy,ivx,ivy = tracks[k]
                tracks[k] = (ix+ivx*t,iy+ivy*t,ivx,ivy)
            px,py = tracks[i][:2]
        return path,total_time+int(hypot(px,py)/5000+1)
    
    def find_path(self,b=4):
        initial = self.path_initial()
        current_path,current_time = self.path_time([c[0] for c in initial])
        pos = None
        last_path = None
        last_time = None
        
        count = 1
        while last_path != current_path:
            print 'Pass',count
            best_path,best_time = [c[0] for c in current_path],current_time
            for i in range(len(current_path)-b):
                print "\t{0:.2f}% ".format(100*i/(len(current_path)-b))
                sub = best_path[i:i+b]
                for s in itertools.permutations(sub):
                    new = best_path[:]
                    new[i:i+b]=s
                    npath,ntime = self.path_time(new)
                    if ntime < best_time:
                        best_path = new
                        best_time = ntime
            
            last_path,last_time = current_path,current_time
            current_path,current_time = self.path_time(best_path)
            count += 1
        return self.convert(current_path,current_time)

import sys
in_fname,out_fname = sys.argv[1:3]
with open(in_fname) as infile:
    visitor = Visitor(infile.read())
s = visitor.find_path()
print s
with open(out_fname,"w") as file:
    file.write(s)

Firstly note that this always tries to maximize the speed between nodes, getting as close to 5000 cm/s as an integral value allows. I don't know if this is necessarily optimal, but removing a degree of freedom obviously makes things much simpler.

The initial step is to create an path by simply choosing one target after another. In this decision each target is weighted negatively by how far the target is from the current position and weighted positively by the average distance from the target to all the remaining possible nodes. This way it tries to go for targets that are closer to it relative to other nodes.

Once it has created an initial path, it loops through it, taking every consecutive b nodes and testing the new path time for every permutation of these nodes.* It repeats this process until doing so makes no change to the path.

*The default value of b is 4, however the value given as my score is my result for running it with b=6. I may run it with higher values and update my score accordingly later.

Edit:

I made a small modification to the deciding process of the initial path which now weights faster targets as higher priority. This seems to be a very significant improvement.

---

To run it simply use

visit.py infile.txt outfile.txt

(I would also suggest using pypy or something as it does take some time to run)

Example output:

FS:8 JY:58 CP:86 FB:110 IF:113 CG:149 BF:173 KK:179 BV:209 AU:218 IU:276 KC:314 EX:319 DE:340 IO:414 EH:445 BS:475 HZ:482 HL:514 JH:528 KJ:563 EE:577 EF:584 CN:601 LF:634 AM:645 GS:680 KL:693 GE:705 AP:725 HI:734 GW:775 CX:828 KR:836 EM:858 LH:871 BZ:890 IJ:896 BG:945 BO:959 FK:970 JQ:984 KX:1049 CR:1061 BI:1078 CI:1089 ID:1117 HF:1128 AN:1191 DX:1211 KF:1213 AZ:1238 KN:1257 GO:1324 HQ:1338 JP:1351 LD:1387 JD:1407 EQ:1424 BB:1500 JZ:1580 DC:1621 EG:1733 LE:1813 BJ:1901 KD:1911 FM:1934 AO:1977 CL:2152 KU:2195 FR:2206 CD:2270 KE:2282 EU:2333 JI:2380 JN:2412 DB:2436 DT:2450 GN:2553 AT:2646 JA:2708 BC:2860 KA:2988 DL:3098 GJ:3165 DS:3201 EA:3353 AG:3385 GA:3418 GB:3504 KI:3543 IN:3638 IC:3708 BK:3737 AK:3811 KG:3854 BY:3882 JX:3920 GL:3988 AA:4007 DD:4018 CO:4040 GI:4053 HM:4059 IH:4063 GG:4072 HN:4100 KP:4156 EN:4164 CM:4195 FL:4212 AS:4229 DW:4250 IV:4267 DJ:4302 DF:4314 AH:4338 HU:4352 EL:4393 ER:4403 HX:4419 FG:4447 JL:4464 JV:4487 AV:4506 AI:4518 JF:4531 EJ:4567 DP:4589 GX:4610 AR:4619 BH:4649 JJ:4760 IW:4839 EV:4861 FI:4900 JC:4919 KT:4984 BW:5001 HP:5014 HV:5041 HK:5058 HE:5061 GH:5075 BP:5082 CF:5094 AW:5110 IT:5132 DM:5160 GZ:5172 FJ:5204 FX:5211 AX:5298 HC:5315 GP:5358 BE:5441 HJ:5450 FE:5490 IB:5592 CZ:5649 FT:5756 IZ:5804 FH:5877 BU:5992 HW:6080 DZ:6256 GT:6431 LM:6552 KB:6630 IA:6652 IR:6739 JO:6832 HY:6887 DQ:6994 FA:7071 FF:7093 FD:7148 BX:7271 GK:7480 IX:7617 EZ:7938 HD:8064 HB:8115 CH:8125 GQ:8176 AB:8241 DG:8277 BN:8347 IY:8397 FZ:8437 CB:8446 JR:8512 II:8576 BA:8613 IL:8625 DU:8650 AC:8687 CS:8743 CC:8817 AJ:8864 EW:8898 DO:8919 ET:8942 AF:8981 KS:9021 DA:9028 EI:9035 GF:9077 JG:9101 FQ:9133 BR:9154 LB:9193 FN:9225 GU:9235 JS:9249 IK:9251 EP:9261 EY:9308 CY:9314 EO:9370 GM:9407 JM:9422 AL:9536 HO:9650 FY:9731 IS:9782 DN:9847 HA:9859 KZ:9922 LL:9985 ES:10014 FO:10056 FV:10106 KY:10182 DI:10215 DV:10263 EB:10340 CQ:10376 DR:10419 AY:10454 IG:10532 BM:10559 CV:10591 LJ:10594 KO:10616 JB:10820 LN:10903 HG:10947 BQ:10988 BL:11100 CU:11140 CE:11235 FU:11380 JU:11397 FW:11419 KM:11448 JW:11479 CA:11549 HS:11594 AQ:11709 IP:11813 JE:11964 HH:12033 BD:12095 BT:12223 GC:12376 LK:12459 DK:12611 KH:12690 AD:12887 GV:12938 KQ:13265 LC:13452 DH:13597 GR:13635 IQ:13748 AE:13763 KW:13967 JK:14080 IM:14145 LA:14232 EK:14290 FP:14344 GD:14395 GY:14472 CT:14532 IE:14650 EC:14771 DY:14807 CJ:14966 ED:15002 CW:15323 HR:15546 LI:15913 KV:16117 JT:16227 LG:16249 HT:16450 CK:16671 FC:17080 BASE:17461

Answer 2

Python 3, score = 21553

The program uses a naive greedy approach. It always calculates where should it go to catch a tracker (any of them) in the shortest time possible. Runs in a couple seconds.

import re

class tracker:
    def __repr__(s):
        return str([s.id,s.x,s.y,s.vx,s.vy])

def dist2(e,t):
    return (e.x+t*e.vx-x)**2+(e.y+t*e.vy-y)**2

def closest(x,y,t,tr):
    tp=0
    while 1:
        min_dist2,min_ind=min((dist2(e,t+tp),ind) for ind,e in enumerate(tr))
        if min_dist2<(tp*5000)**2:
            be=tr[min_ind]
            return be.x+(t+tp)*be.vx,be.y+(t+tp)*be.vy,min_ind,t+tp
        tp+=1

tr=[] #x,y,vx,vy,id
with open('tracklist') as f:    
    for l in f.read().split():
        a=tracker()
        a.id,data=l.split(':')
        a.x,a.y,a.vx,a.vy=[int(s) for s in data.split(',')]
        tr+=[a]
x,y,gx,gy=0,0,0,0
t=0
r=[] #id,time
while tr:
    x,y,ti,t=closest(x,y,t,tr)
    r+=[(tr[ti].id,t)]
    #print(len(tr),t,tr[ti].id)
    del tr[ti]
    if not tr and r[-1][0]!='BASE':
            a=tracker()
            a.id,a.x,a.y,a.vx,a.vy='BASE',0,0,0,0
            tr+=[a]
print(*[re[0]+':'+str(re[1]) for re in r])

Route:

FS:8 DJ:34 KN:53 GP:70 KF:89 LK:119 BI:149 IJ:181 DI:195 GC:218 EB:247 AS:272 KX:281 HF:301 FU:320 CI:348 CR:362 DK:420 JQ:443 FK:459 BO:475 BG:531 BZ:549 CX:567 KR:586 FW:600 KS:622 LG:638 CS:674 ET:694 GW:719 GF:738 LI:747 AP:769 HI:778 GS:797 KL:812 GE:818 AJ:841 AF:878 LA:903 EI:919 EC:942 AL:953 JS:962 ED:982 FN:990 AM:1026 CN:1028 HL:1061 BS:1078 KV:1094 BN:1105 JK:1119 JH:1127 HZ:1162 EH:1172 DR:1186 HO:1205 KJ:1228 JG:1231 IG:1249 AE:1261 IM:1284 JU:1294 IK:1322 DU:1336 IE:1353 GM:1386 JJ:1421 CB:1444 BR:1472 AH:1511 KO:1546 IL:1594 FG:1611 KT:1631 EL:1636 JW:1645 DD:1671 BE:1685 ES:1706 DN:1732 AI:1765 JV:1770 JF:1802 AQ:1815 EJ:1827 JZ:1880 HX:1916 AR:1976 IW:2005 ER:2027 GX:2045 BH:2054 AV:2087 JL:2118 DP:2166 JM:2229 DQ:2297 GT:2338 LL:2398 IA:2481 JO:2533 KB:2646 LM:2682 HW:2735 DZ:2861 FH:2975 BU:3027 IZ:3034 FT:3137 DC:3170 IB:3193 FC:3242 GO:3285 JC:3319 IO:3339 CP:3382 IF:3442 EA:3444 BB:3459 AG:3484 GA:3518 KD:3574 FE:3601 JD:3616 BP:3629 HJ:3651 BW:3662 HP:3673 HE:3698 HV:3701 HK:3704 DX:3720 CM:3731 FL:3755 EN:3776 DW:3784 IV:3799 KP:3824 FO:3857 FV:3892 KC:3899 DV:3911 II:3933 KY:3934 HN:3978 GG:4004 IH:4016 HM:4021 GI:4027 CO:4039 AZ:4056 AA:4073 GL:4096 GH:4115 CF:4131 AW:4145 IT:4162 DM:4185 GZ:4193 FX:4221 FJ:4229 LH:4250 AX:4272 LD:4289 HC:4312 CA:4340 LF:4376 DB:4444 AN:4505 GD:4548 GV:4616 BD:4660 EK:4681 ID:4755 FP:4831 DY:4845 JE:4885 CT:4943 JR:4995 FZ:5087 BA:5131 IY:5189 AB:5227 CH:5265 HB:5312 HD:5358 EZ:5433 CJ:5598 GQ:5642 DG:5705 AC:5877 DO:5960 EW:5980 CC:6018 IP:6026 DA:6055 AY:6124 EE:6135 BM:6156 LJ:6197 EF:6236 GU:6256 EP:6283 CQ:6313 EY:6319 CY:6334 EO:6357 JB:6420 LN:6456 HG:6495 BQ:6512 CE:6546 CU:6636 BL:6694 CW:6822 HR:6908 IX:7087 GK:7239 BX:7438 FD:7558 FF:7615 FA:7640 LB:7784 FQ:7826 CV:7955 FY:8018 JP:8058 IS:8090 KZ:8136 HQ:8177 EV:8210 HA:8254 FI:8340 HU:8471 DF:8495 EQ:8587 HY:8799 IR:8932 KG:9512 BY:9523 EM:9703 HH:9763 BT:9850 JX:9973 BK:10091 IC:10129 AK:10203 GB:10350 GJ:10436 IN:10463 DS:10577 DL:10789 JY:11049 FM:11146 CG:11213 BF:11363 KA:11783 EG:11886 CL:11966 IU:12107 EU:12210 EX:12271 FR:12418 CD:12652 AO:12901 AU:12976 BV:13022 DE:13154 KE:13262 KU:13303 JA:13366 DT:13620 JN:13804 LE:13831 BC:13879 JI:13914 KK:14134 FB:14869 CZ:14975 KI:15161 CK:15670 HT:15870 GY:15992 JT:16216 BJ:16275 HS:16636 KM:16813 KW:17719 AD:17965 AT:18082 KH:18226 GN:18841 DH:19723 IQ:19760 GR:19948 KQ:20117 LC:20351 BASE:21553