TSP · the travelling salesman problem · BD × AI Lab · 19 Nov 2026TSP · problem potujočega trgovca · BD × AI Lab · 19. nov. 2026
A new kind of travelling-salesman (TSP) solver that breaks records.Trgovski potnik (TSP) nove vrste, ki podira rekorde.
We break records against the leading programs on the same computer. Watch the animations of the shortest route being solved, and the live demo. It is fast, lean, portable, powerful, and more.Rekorde podiramo v primerjavi z vodilnimi programi na istem računalniku. Poglejte si animacije reševanja najkrajše poti in živ demo. Je hiter, varčen, prenosljiv, zmogljiv in še več.
More about the testVeč o preizkusu
We described the measured properties of 8zTSP to six leading language models, each in a new conversation, without BD’s ideas and without code, and asked whether they know such a program and whether they can write it. All six answered that they know of no such program. Three wrote a program: after five minutes on one core their tours were 0.3 % to 19 % above the optimum, and in 18 runs none reached the optimum; 8zTSP reaches it on the same two maps in every run. Three wrote that they cannot make a program with such properties. Each model had one attempt.Šestim vodilnim jezikovnim modelom smo v novem pogovoru, brez BD-jevih zamisli in brez kode, opisali izmerjene lastnosti 8zTSP in jih vprašali, ali tak program poznajo in ali ga znajo napisati. Vseh šest je odgovorilo, da takega programa ne poznajo. Trije so program napisali: po petih minutah na enem jedru so bile njihove poti od 0,3 % do 19 % nad optimumom in v 18 tekih nobena ni dosegla optimuma; 8zTSP ga na istih dveh zemljevidih doseže v vsakem teku. Trije so zapisali, da programa s takimi lastnostmi ne morejo narediti. Vsak model je imel en poskus.
| programprogram | optimum reachedoptimum dosežen | Nicaragua (nu3496)Nikaragva (nu3496) | SwitzerlandŠvica |
|---|---|---|---|
| A | 0 of 60 od 6 | 5.4 · 6.4 · 7.9 %5,4 · 6,4 · 7,9 % | 6.6 · 7.0 · 7.6 %6,6 · 7,0 · 7,6 % |
| B | 0 of 60 od 6 | 0.6 · 0.8 · 2.1 %0,6 · 0,8 · 2,1 % | 0.3 · 0.5 · 0.5 %0,3 · 0,5 · 0,5 % |
| C | 0 of 60 od 6 | 9.1 · 9.2 · 18.7 %9,1 · 9,2 · 18,7 % | 8.1 · 9.4 · 11.3 %8,1 · 9,4 · 11,3 % |
| 8zTSP development build, not yet in the published program (10 seeds per map, one thread)razvojna gradnja 8zTSP, še ni v objavljenem programu (10 semen na zemljevid, ena nit) | 20 of 2020 od 20 | optimum in every runoptimum v vsakem teku | optimum in every runoptimum v vsakem teku |
One thread, 300 s, 3 seeds per map and program, the same laptop; every tour recomputed by us. Distance above the proved optimum (nu3496: 96,132; Switzerland: 7,844,951). The three programs are not named. More about 8zTSP on these two maps in our lab log: Switzerland, nu3496.Ena nit, 300 s, 3 semena na zemljevid in program, isti prenosnik; vsako pot smo preračunali sami. Odmik od dokazanega optimuma (nu3496: 96.132; Švica: 7.844.951). Treh programov ne imenujemo. Več o 8zTSP na teh dveh zemljevidih v našem laboratorijskem dnevniku: Švica, nu3496.
For one of the six models the conversation was opened in an account with stored settings; it did not read the project’s content. The programs were tested on one core; with more cores the results could differ.Pri enem od šestih modelov je bil pogovor odprt v računu z naloženimi nastavitvami; vsebine projekta ni bral. Programi so bili preizkušeni na enem jedru; z več jedri bi bili izidi lahko drugačni.
The demo is password-protected; access on request.Demo je zaščiten z geslom; dostop na prošnjo.
New in the demo, 19 Nov 2026. The demo now runs a new build of 8zTSP with the same kernel as our race candidate. The maps sit in a menu with two levels that opens with »Selected 10«, Croatia and Croatia HARD-25K are new maps, and every map is drawn with north up, in the demo and in the pictures. Open the demo (password; access on request).Novo v demu, 19. nov. 2026. Demo zdaj poganja novo gradnjo 8zTSP z istim jedrom, kot ga ima naš kandidat za dirko. Zemljevidi so v meniju na dveh ravneh, ki se odpre z »Izbranih 10«, Hrvaška in Hrvaška HARD-25K sta nova zemljevida, vsak zemljevid pa je narisan s severom zgoraj, v demu in na slikah. Odpri demo (z geslom; dostop na prošnjo).
Tell us (form on the demo page)Povejte nam (obrazec na strani demo)
Finland on an iPad, 22 Nov 2026. With 1,437,195 locations and 8 workers, web 8zTSP on BD’s iPad Air M2 showed 108,901.5 km at 3,600.3 s, while still searching. BD reports one pass without separate preparation. The iPad tour export and independent validation are pending. Screenshot, published references and independently recomputed single-thread controls; the 16-copy LKH repeat has started, the matched result is pending.Finska na iPadu, 22. nov. 2026. Spletni 8zTSP je na BD-jevem iPadu Air M2 pri 1.437.195 lokacijah in 8 delavcih pokazal 108.901,5 km pri 3.600,3 s, ko je iskanje še teklo. BD navaja en prehod brez ločene predpriprave. Izvoz ture z iPada in neodvisna preverba še čakata. Posnetek, objavljene reference in neodvisno preračunani enonitni kontroli; ponovitev LKH s 16 kopijami se je začela, izid primerjave še čaka.
Records in our comparisonsRekordi v naših primerjavah
Each row: our number and the best other program’s on the same laptop, with the conditions. The whole laptop for each program first; the one-thread row last.V vsaki vrstici: naša številka in številka najboljšega drugega programa na istem prenosniku, s pogoji. Najprej ves prenosnik za vsak program; vrstica z eno nitjo zadnja.
Swipe the table sideways for every column.Za vse stolpce podrsajte tabelo vstran.
| MapZemljevid | 8zTSP | Best other program, same laptopNajboljši drug program, isti prenosnik | ConditionsPogoji |
|---|---|---|---|
| nu3496 · 3,496 cities: time to the optimumnu3496 · 3.496 mest: čas do optimuma | about 5 s, all 14 threadsokoli 5 s, vseh 14 niti | Nagata’s GA-EAX: about 28 s as 7 copies, its best settingNagatov GA-EAX: okoli 28 s kot 7 kopij, njegova najboljša nastavitev | Each at its best on this laptop; median of 10 runs, both at the optimum in every run, 17 Nov 2026.Vsak v svoji najboljši nastavitvi na tem prenosniku; mediana 10 tekov, oba v vsakem teku do optimuma, 17. nov. 2026. From the labIz laboratorija |
| nu3496: memorynu3496: pomnilnik | about 48 MB, 7 threadsokoli 48 MB, 7 niti | Nagata’s GA-EAX: about 1.0 GB as 7 copiesNagatov GA-EAX: okoli 1,0 GB kot 7 kopij | Peak of all processes, in decimal units; 17 Nov 2026.Največja poraba vseh procesov, v desetiških enotah; 17. nov. 2026. From the labIz laboratorija |
| 10 million cities10 milijonov mest | within 1% of the estimated bound in about 15 minutes; about 1.6 GB of memory, 7 threadsnajveč 1 % nad ocenjeno mejo v približno 15 minutah; okoli 1,6 GB pomnilnika, 7 niti | LKH 3.0.7 as 2 copies: no route in 2 hours; about 14.2 GBLKH 3.0.7 kot 2 kopiji: v 2 urah nobene poti; okoli 14,2 GB | Race of 12 Nov 2026 on the same 7 cores; the bound is an estimate, not a certified lower bound.Dirka 12. nov. 2026 na istih 7 jedrih; meja je ocena, ne dokazana spodnja meja. From the labIz laboratorija |
| nu3496 in a browsernu3496 v brskalniku | about 10 s, 7 workersokoli 10 s, 7 delavcev | no other solver tested in a browserdrugih reševalnikov v brskalniku nismo preizkusili | Median of 10 runs, Chromium on the same laptop, 15 Nov 2026.Mediana 10 tekov, Chromium na istem prenosniku, 15. nov. 2026. The demo (password)Demo (z geslom) |
| Hougardy–Zhong · 52 to 199 cities, one thread eachHougardy–Zhong · 52 do 199 mest, po ena nit | the optimum in 50 of 50 runs, each under 0.15 s (one thread)optimum v 50 od 50 tekov, vsakič manj kot 0,15 s (ena nit) | LKH 3.0.7, one thread: not the optimum of Tnm199 in 3 of 3 runs; Concorde, one thread: proved the three smallest in 30 s, 290 s and 20 minLKH 3.0.7, ena nit: optimuma za Tnm199 ni dosegel v 3 od 3 tekov; Concorde, ena nit: tri najmanjše je dokazal v 30 s, 290 s in 20 min | One program at a time on one core of a fully loaded laptop, 16 Nov 2026. The maps: Hougardy and Zhong (2021), CC BY 4.0.En program naenkrat na enem jedru polno obremenjenega prenosnika, 16. nov. 2026. Zemljevidi: Hougardy in Zhong (2021), CC BY 4.0. In the demo: Hard instances (password)V demu: Težki primeri (z geslom) |
One engine for the whole computer: in a browser, even on a phone; on one laptop up to 10 million cities.En motor za ves računalnik: v brskalniku, tudi na telefonu; na enem prenosniku do 10 milijonov mest.
The travelling salesman problem (TSP) asks for the shortest round trip that visits every city on a map exactly once. It is easy to state and gets very hard as the number of cities grows.Problem potujočega trgovca (TSP) išče najkrajšo krožno pot, ki vsako mesto na zemljevidu obišče natanko enkrat. Postaviti ga je lahko, z rastočim številom mest pa postane zelo težak.
With its own view of the map, 8zTSP puts 7 of the laptop’s 8 cores to work on one map at once. The standard programs, LKH and Concorde’s linkern, use one core per run: on the same laptop, with the settings used, neither got there in two hours.Z lastnim pogledom na zemljevid 8zTSP na enem zemljevidu hkrati zaposli 7 od 8 jeder prenosnika. Standardna programa, LKH in Concordov linkern, uporabljata eno jedro na tek: na istem prenosniku in z uporabljenimi nastavitvami v dveh urah do tja ni prišel nobeden od njiju.
Measured on one laptopIzmerjeno na enem prenosniku
Every card names its conditions and links to its source. The headlines use the whole computer; numbers for a single core are in the small print.Vsaka kartica navede pogoje in poveže na vir. Naslovi uporabijo ves računalnik; številke za eno jedro so v drobnem tisku.
nu3496 · 3,496 cities in Nicaraguanu3496 · 3.496 mest v Nikaragvi
The optimum, 96,132, in about 6 secondsOptimum, 96.132, v približno 6 sekundah
With 7 of the laptop’s 8 cores: median 6.13 s, 10 of 10 runs. In a browser, about 10 s.S 7 od 8 jeder prenosnika: mediana 6,13 s, 10 od 10 tekov. V brskalniku okoli 10 s.
Build 563f8fa of 15 Nov 2026 (kernel 1f072ad); the optimum was proved by Concorde. One run of LKH 3.0.7 on one core had not reached it after 16.8 hours (best 96,152; run of 15–17 Nov). nu3496 has 3,496 cities but only 2,373 distinct locations; 1,840 cities share their location with one or more others.Gradnja 563f8fa s 15. nov. 2026 (jedro 1f072ad); optimum je dokazal Concorde. En tek LKH 3.0.7 na enem jedru ga po 16,8 ure ni dosegel (najboljše 96.152; tek 15.–17. nov.). nu3496 ima 3.496 mest, a le 2.373 različnih lokacij; 1.840 mest si lokacijo deli z vsaj enim drugim.
From the labIz laboratorija →Hougardy–Zhong · hard for exact proofs · 52 to 199 citiesHougardy–Zhong · težki za natančen dokaz · 52 do 199 mest
The optimum in 50 of 50 runs, each in a fraction of a secondOptimum v 50 od 50 tekov, vsakič v delu sekunde
On the same laptop Concorde needed 30 s, 290 s and 20 min to prove the three smallest; LKH, given up to a minute, did not find the 199-city optimum in 3 of 3 runs.Na istem prenosniku je Concorde za dokaz treh najmanjših potreboval 30 s, 290 s in 20 min; LKH v največ minuti optimuma za 199 mest ni našel v 3 od 3 tekov.
Each run took under 0.15 s, measured with one thread per program on a fully loaded laptop, 16 Nov 2026. The maps: Hougardy and Zhong (2021), CC BY 4.0.Vsak tek je trajal manj kot 0,15 s, izmerjeno z eno nitjo na program na polno obremenjenem prenosniku, 16. nov. 2026. Zemljevidi: Hougardy in Zhong (2021), CC BY 4.0.
In the demo: Hard instances (password)V demu: Težki primeri (z geslom) →Slovenia · all 6,035 settlementsSlovenija · vseh 6.035 naselij
8,728.2 km, at most 0.006% above the shortest possible route8.728,2 km, največ 0,006 % nad najkrajšo možno potjo
Our tour of 8,728,190 m, measured against Concorde’s lower bound; the proof is still running. It is the best known tour: 8zTSP reached it on 18 Nov at 05:35 by fusing five of its own earlier tours, and LKH 3.0.14 reached the same tour from scratch the same morning.Naša pot 8.728.190 m, primerjana s Concordovo spodnjo mejo; dokaz še teče. To je najboljša znana pot: 8zTSP jo je dosegel 18. novembra ob 05:35 z zlitjem petih svojih prejšnjih poti, LKH 3.0.14 pa je isto pot našel od začetka isto jutro.
Tour: 8zTSP, 18 Nov 2026, 05:35, five of its own earlier tours fused after a 24-hour run of its development build (a continuation of earlier runs, not a run from scratch). Bound: Concorde, 8,727,732 m, 18 Nov 2026, 08:55. Straight-line distances between settlement centres, not roads.Pot: 8zTSP, 18. nov. 2026, 05:35, pet svojih prejšnjih poti, zlitih po 24-urnem teku razvojne gradnje (nadaljevanje prejšnjih tekov, ne tek od začetka). Meja: Concorde, 8.727.732 m, 18. nov. 2026, 08:55. Zračne razdalje med središči naselij, ne ceste.
From the labIz laboratorija →10 million cities · one laptop10 milijonov mest · en prenosnik
Within 1% of the bound in about 15 minutes, with 7 of the laptop’s 8 coresNajveč 1 % nad ocenjeno mejo v približno 15 minutah, s 7 od 8 jeder prenosnika
On the same laptop LKH 3.0.7, run as it can use the machine (2 copies on the 7 cores; more do not fit in memory), gave no route at all in 2 hours (race of 12 Nov). That is more than five times the 1,904,711 cities of the World TSP (only the number of cities is compared).Na istem prenosniku LKH 3.0.7, v toliko kopijah, kolikor jih stroj zmore (2 kopiji na 7 jedrih; več jih ne gre v pomnilnik), v 2 urah ni dal nobene poti (dirka 12. nov.). To je več kot petkrat toliko mest, kot jih ima World TSP (1.904.711; primerjamo le število mest).
The bound for 10 million cities is an estimate (0.7080·√(N·A)), not a certified lower bound. A one-core test of 13–14 Nov: 8zTSP 56 min, LKH 1 h 49 min, linkern not within 2 h.Meja za 10 milijonov mest je ocena (0,7080·√(N·A)), ne dokazana meja. Preizkus na enem jedru 13.–14. nov.: 8zTSP 56 min, LKH 1 h 49 min, linkern ne v 2 h.
From the labIz laboratorija →The whole computerVes računalnik
1 → 7 cores: about 28 s → about 6 s on nu34961 → 7 jeder: okoli 28 s → okoli 6 s na nu3496
8zTSP puts every core to work on one map. The other solvers in our tests (LKH 3.0.7, Concorde, Nagata’s GA-EAX) each run on one core.8zTSP zaposli vsa jedra na enem zemljevidu. Drugi reševalniki v naših preizkusih (LKH 3.0.7, Concorde, Nagatov GA-EAX) tečejo vsak na enem jedru.
Median 27.8 s on one core and 6.13 s on 7, the same build 563f8fa, 15 Nov 2026.Mediana 27,8 s na enem jedru in 6,13 s na 7, ista gradnja 563f8fa, 15. nov. 2026.
From the labIz laboratorija →nu3496 · the whole laptop against Nagata’s GA-EAXnu3496 · ves prenosnik proti Nagatovemu GA-EAX
With 7 cores each: the optimum in about 6 s; GA-EAX as 7 copies, about 28 sS po 7 jedri: optimum v približno 6 s; GA-EAX kot 7 kopij v približno 28 s
Both found the optimum, 96,132, in all 10 runs; 8zTSP was first in 9 of 10 and needed about 4.5 times less time. Each at its best on this laptop: 8zTSP about 5 s with all 14 threads, GA-EAX about 28 s as 7 copies (as 14 copies about 39 s), about 5 times. Memory: about 48 MB against about 1.0 GB for the 7 copies.Oba sta optimum, 96.132, našla v vseh 10 tekih; 8zTSP je bil prvi v 9 od 10 in je potreboval okoli 4,5-krat manj časa. Vsak v svoji najboljši nastavitvi na tem prenosniku: 8zTSP okoli 5 s z vsemi 14 nitmi, GA-EAX okoli 28 s kot 7 kopij (kot 14 kopij okoli 39 s), okoli 5-krat. Pomnilnik: okoli 48 MB proti okoli 1,0 GB za 7 kopij.
Medians of 10 runs per setting, 17 Nov 2026, the order alternating. GA-EAX: Nagata’s public code, one copy per core, each restarting; the first copy at the optimum counts. 8zTSP build 3c36abdd. Memory: peak of all processes, decimal units.Mediane 10 tekov na nastavitev, 17. nov. 2026, vrstni red se je menjal. GA-EAX: Nagatova javna koda, ena kopija na jedro, vsaka se znova zažene; šteje prva kopija na optimumu. 8zTSP, gradnja 3c36abdd. Pomnilnik: največja poraba vseh procesov, desetiške enote.
From the labIz laboratorija →
More on nu3496Več o nu3496
Concorde, on one core of the same laptop, proved the optimum in a median of 70 min of processor time (three seeds: 55, 70 and 149 min). 8zTSP finds the optimal tour; Concorde proves it is optimal.Concorde je na enem jedru istega prenosnika optimum dokazal v mediani 70 min procesorskega časa (tri semena: 55, 70 in 149 min). 8zTSP optimalno pot najde, Concorde pa dokaže, da je optimalna.
Checking every possible tour is hopeless: 3,496 cities mean about 1010,868 tours, and already 27 cities would take longer than the age of the universe on this laptop.Preverjanje vseh možnih poti je brezupno: 3.496 mest pomeni okoli 1010.868 poti, že 27 mest pa bi na tem prenosniku trajalo dlje od starosti vesolja.
One engine, many fieldsEn motor, veliko področij
The same engine can work wherever many points must be put in a good order. Each field needs its own measurement first; the label says how far each one is. All ten fields in detail, on the lab page.Isti motor lahko dela povsod, kjer je treba veliko točk postaviti v dober vrstni red. Vsako področje najprej potrebuje svojo meritev; oznaka pove, kako daleč je. Vseh deset področij podrobno na laboratorijski strani.
- in test nowv preizkusu zdajChips and electronicsČipi in elektronika
Points on chips, test chains, drilling and laser paths are true travelling-salesman problems; public chip maps reach about 745,000 points. Two of Waterloo’s VLSI maps are in the demo, and the open Bonn VLSI maps are in test.Točke na čipih, testne verige ter poti vrtanja in laserja so pravi problemi trgovskega potnika; javni zemljevidi čipov segajo do okoli 745.000 točk. Dva zemljevida VLSI iz Waterlooja sta v demu, odprti zemljevidi VLSI iz Bonna pa so v preizkusu.
- in test nowv preizkusu zdajOrdering and compressing dataUrejanje in stiskanje podatkov
DNA reads, table rows and the documents used to train language models are easier to store and use when similar items sit next to each other: a relative of the TSP.Odčitke DNK, vrstice tabel in dokumente za učenje jezikovnih modelov je laže shraniti in uporabljati, če so podobni elementi drug ob drugem: sorodnik TSP.
- ideazamiselPoint clouds and star cataloguesOblaki točk in katalogi zvezd
Not a TSP: here our own view of the map is itself the product, as a way to index and compress millions of points.To ni TSP: tu je izdelek sam naš lastni pogled na zemljevid, kot način za indeksiranje in stiskanje milijonov točk.
- ideazamiselTours from star to starTure od zvezde do zvezde
A true TSP in three dimensions: public tours through 2 million, 10 million and 1.33 billion stars of the Gaia catalogue exist (Bill Cook and Keld Helsgaun, Waterloo).Pravi TSP v treh razsežnostih: obstajajo javne ture skozi 2 milijona, 10 milijonov in 1,33 milijarde zvezd kataloga Gaia (Bill Cook in Keld Helsgaun, Waterloo).
- ideazamiselGenetic mapsGenetski zemljevidi
Genetic and radiation-hybrid maps order markers as a TSP on distances, and Concorde has been better there than specialised tools.Genetski zemljevidi in zemljevidi radiacijskih hibridov urejajo označevalce kot TSP na razdaljah, Concorde pa je bil tam boljši od specializiranih orodij.
- ideazamiselLogisticsLogistika
A big tour cut into vehicle routes (capacities, time slots) is the TSP’s closest business relative.Velika tura, razrezana na poti vozil (zmogljivosti, časovni termini), je najbližji poslovni sorodnik TSP.
- ideazamiselMaterials and moleculesMateriali in molekule
Not shortest paths but the deepest energy valley, yet the search machine is a sibling of our kernel, part for part.Ne najkrajše poti, temveč najgloblja energijska dolina, a iskalni stroj je sorodnik našega jedra, del za delom.
- ideazamiselTelescopes and space missionsTeleskopi in vesoljske misije
Observatories order their targets this way: a 2023 study called it the travelling telescope problem and cut a Keck night’s slewing time several-fold.Observatoriji tako urejajo svoje cilje: študija iz leta 2023 ga je imenovala problem potujočega teleskopa in večkrat skrajšala čas obračanja teleskopa Keck v eni noči.
- ideazamiselScheduling and other combinatorial problemsRazporejanje in drugi kombinatorični problemi
Integer programming, satisfiability and scheduling already use cousins of our parts.Celoštevilsko programiranje, izpolnjivost in razporejanje že uporabljajo sorodnike naših delov.
- ideazamiselProteinsBeljakovine
Protein folding is not a TSP, and our engine does not fold proteins; a simple lattice model of folding is a fair testbed.Zvijanje beljakovin ni TSP in naš motor beljakovin ne zvija; preprost model zvijanja na rešetki je pošteno preizkusno polje.
From the same idea at BD × AI LabIz iste zamisli v BD × AI Lab
BD’s idea, MDL × DCC, also drives his work beyond the TSP. In those pages’ own words (in English):BD-jeva zamisel MDL × DCC poganja tudi njegovo delo zunaj TSP. Z besedami teh strani (v angleščini):
- DNADNA — Repeat Structure and Null Models
»The strongest annotated yeast regions are tandem repeats within FLO1 and FLO9.«
- 8Z image compressionStiskanje slik 8Z8Z Mathematical Compression — Benchmarks and Methods
»On this mixed 60-image set, 8Z uses 38.9% of the original TIFF bytes in total. JPEG XL is smaller at 31.4%, followed by WebP at 34.2%; PNG uses 46.3% and 7-Zip 49.2%.«
- 8Z sound compressionStiskanje zvoka 8Z8Z-Audio Benchmark v1.0
»Surpassed FLAC-12 (maximum) on 7 of 15 clips. Lossless verified.«
NextNaprej
- 100 million points on one laptop, then 1 billion: not claimed before they are measured.100 milijonov točk na enem prenosniku, nato 1 milijarda: ne trdimo, dokler ni izmerjeno.
- The World TSP, 1,904,711 cities.World TSP, 1.904.711 mest.
- The open VLSI maps.Odprti zemljevidi VLSI.
- 8zTSP-Q (planned): we assess that the 8zTSP architecture also suits quantum computers, as co-processors for parts of a problem.8zTSP-Q (v načrtu): ocenjujemo, da je arhitektura 8zTSP primerna tudi za kvantne računalnike, kot sopomočnike za dele problema.
All our TSP pagesVse naše strani o TSP
NowZdaj
- 8zTSP: results and the lab log8zTSP: izidi in laboratorijski dnevnikfirst published 11 Nov 2026prvič objavljeno 11. nov. 2026
The new Rust kernel, measured on one laptop next to LKH and Concorde; every result with its conditions. Updated 19 Nov 2026.Novo jedro v Rustu, merjeno na enem prenosniku ob LKH in Concordu; vsak izid s svojimi pogoji. Posodobljeno 19. nov. 2026.
- 8zTSP in your browser8zTSP v brskalnikufirst published 14 Nov 2026prvič objavljeno 14. nov. 2026
The same engine in its minimal build, on your own computer: all its cores, the map in full screen, a stop at the known optimum. Password-protected; access on request.Isti motor v minimalni gradnji, na vašem računalniku: vsa njegova jedra, zemljevid čez cel zaslon, ustavitev pri znanem optimumu. Zaščiteno z geslom; dostop na prošnjo.
- Edition 1 benchmarkMeritve 1. izdaje12-level comparison and verification notesPrimerjava 12 ravni in opombe o preverjanju
- Top 5 TSP approachesTop 5 TSP pristopovFrom exact solvers to 8zTSP and its research arenaOd eksaktnih reševalcev do 8zTSP in njegove raziskovalne arene
- 8zTSP: recorded runs8zTSP: posnetki tekovfirst published 16 Nov 2026prvič objavljeno 16. nov. 2026
Two recorded runs of the demo, played back step by step: Nicaragua to its known optimum and Slovenia’s 6,035 settlements. Open to everyone, no password.Dva posneta teka demo različice, predvajana korak za korakom: Nikaragva do znanega optimuma in 6.035 naselij Slovenije. Odprto za vse, brez gesla.
Earlier workPrejšnje delo
- 8Z-RP: TSP as compression8Z-RP: TSP kot stiskanjefirst published 14 Mar 2026prvič objavljeno 14. mar. 2026
From an exact qa194 result to a nu3496 route of 96,793, with a trip optimizer in the browser.Od natančnega izida za qa194 do poti 96.793 za nu3496, z optimizatorjem potovanj v brskalniku.
- 8Z-RP · nu3496 status8Z-RP · stanje nu3496first published 18 Mar 2026prvič objavljeno 18. mar. 2026
The verified nu3496 route of 96,928 from DEV2.3, with TSPES and TSPTS.Preverjena pot 96.928 za nu3496 iz DEV2.3, s TSPES in TSPTS.
- ssMDL-DCC challengeIzziv ssMDL-DCCfirst published 18 Mar 2026prvič objavljeno 18. mar. 2026
Find the best self-selecting governor for the TSP.Poiščite najboljši samoizbirni krmilnik za TSP.
- qa194 tour mapsZemljevida poti qa194first published 19 Mar 2026prvič objavljeno 19. mar. 2026
Qatar, 194 cities: the 8Z-RP tour on the map; a second view.Katar, 194 mest: pot 8Z-RP na zemljevidu; drugi pogled.
- 8Z-RP v1.18Z-RP v1.1first published 19 Mar 2026prvič objavljeno 19. mar. 2026
The earliest versions of TSP as compression; also v1.0.Najzgodnejši različici TSP kot stiskanja; tudi v1.0.
- Arena Lab v2.6Arena Lab v2.6first published 21 Mar 2026prvič objavljeno 21. mar. 2026
25 sensors and 685 laws for 8Z-RP; MDL decides.25 senzorjev in 685 zakonov za 8Z-RP; odloča MDL.
- nu3496: the route of 96,928nu3496: pot 96.928first published 19 Jul 2026prvič objavljeno 19. jul. 2026
The verified route on an interactive map; the routes before it: 97,110, 97,056, 97,050, 97,042 and 96,934 (12–16 Jul 2026).Preverjena pot na interaktivnem zemljevidu; poti pred njo: 97.110, 97.056, 97.050, 97.042 in 96.934 (12.–16. jul. 2026).
- Six TSP arenasŠest aren za TSPfirst published 11 Sep 2026prvič objavljeno 11. sep. 2026
Six arenas side by side, with the evidence receipts of 11 Sep and 12 Sep; the earlier page with five.Šest aren drugo ob drugi, s potrdili izidov z dne 11. sep. in 12. sep.; prejšnja stran s petimi.
- Trip OptimizerOptimizator potovanjfirst published 9 Jan 2026prvič objavljeno 9. jan. 2026
Plan a real trip: paste the places, get a clean route and map links. Also the LAB version and TripOpti.Načrtujte pravo potovanje: prilepite kraje in dobite urejeno pot in povezave na zemljevid. Tudi različica LAB in TripOpti.
Every page keeps its content; the old addresses lead to the new ones.Vsaka stran ohrani vsebino; stari naslovi vodijo na nove.
Seventy years of solving the TSPSedemdeset let reševanja TSP
The largest TSPs solved with a proof of optimality, by year (source: University of Waterloo, Milestones).Največji TSP-ji, rešeni z dokazom optimalnosti, po letih (vir: Univerza Waterloo, Milestones).
- 195449 cities · Dantzig, Fulkerson, Johnson49 mest · Dantzig, Fulkerson, Johnson
- 19872,392 cities · Padberg, Rinaldi2.392 mest · Padberg, Rinaldi
- 19947,397 cities · Applegate, Bixby, Chvátal, Cook7.397 mest · Applegate, Bixby, Chvátal, Cook
- 199813,509 cities in the USA · the same team13.509 mest v ZDA · ista ekipa
- 200424,978 cities in Sweden · with Helsgaun24.978 mest na Švedskem · s Helsgaunom
- 200685,900 points of a circuit layout · with Espinoza, Goycoolea, Helsgaun85.900 točk načrta vezja · z Espinozo, Goycooleo, Helsgaunom
The World TSP of 1,904,711 cities has a best known tour but no proof that it is optimal. For scale: nu3496 has 3,496 cities, Slovenia 6,035, and our largest test map 10,000,000.World TSP s 1.904.711 mesti ima najboljšo znano pot, dokaza, da je optimalna, pa še ne. Za primerjavo: nu3496 ima 3.496 mest, Slovenija 6.035, naš največji preizkusni zemljevid pa 10.000.000.
On the shoulders ofNa ramenih
- The TSP pages of the University of Waterloo (William Cook and colleagues): the national maps such as nu3496, the World TSP and the history of the problem.Strani o TSP Univerze Waterloo (William Cook s sodelavci): nacionalni zemljevidi, kot je nu3496, World TSP in zgodovina problema.
- Concorde (Applegate, Bixby, Chvátal, Cook): the exact solver that proves a tour optimal; on our laptop it proved the optimum of nu3496 in a median of 70 minutes of processor time (three seeds: 55 to 149 minutes).Concorde (Applegate, Bixby, Chvátal, Cook): natančni reševalnik, ki dokaže, da je pot optimalna; na našem prenosniku je optimum nu3496 dokazal v mediani 70 minut procesorskega časa (tri semena: od 55 do 149 minut).
- LKH (Keld Helsgaun): the Lin–Kernighan–Helsgaun heuristic, the yardstick for large maps.LKH (Keld Helsgaun): hevristika Lin–Kernighan–Helsgaun, merilo za velike zemljevide.
- TSPLIB (Gerhard Reinelt): the classic collection of test maps, and the file format our demo reads.TSPLIB (Gerhard Reinelt): klasična zbirka preizkusnih zemljevidov in oblika datotek, ki jo bere naš demo.
- The DIMACS TSP Challenge (David Johnson, Lyle McGeoch): the random maps E100k.0 to E10M.0 and their Held–Karp bounds.DIMACS TSP Challenge (David Johnson, Lyle McGeoch): naključni zemljevidi od E100k.0 do E10M.0 in njihove meje Held–Karp.
- EAX (Nagata and Kobayashi): the edge assembly crossover.EAX (Nagata in Kobayashi): križanje s sestavljanjem robov.
How to read our numbersKako brati naše številke
- Every number has its conditions next to it: one laptop (Intel i7-10875H, 8 cores), how many threads, which build and which day.Vsaka številka ima pogoje ob sebi: en prenosnik (Intel i7-10875H, 8 jeder), koliko niti, katera gradnja in kateri dan.
- »Median of 10 runs« means that half of the runs were faster and half slower; some seeds take much longer, and we show them.»Mediana 10 tekov« pomeni, da je bila polovica tekov hitrejša in polovica počasnejša; nekatera semena trajajo precej dlje, in jih pokažemo.
- »The optimal tour« only where the optimum is known (nu3496: 96,132, proved by Concorde). 8zTSP finds the optimal tour; Concorde proves that it is optimal.»Optimalna pot« le tam, kjer je optimum znan (nu3496: 96.132, dokazal ga je Concorde). 8zTSP optimalno pot najde, Concorde pa dokaže, da je optimalna.
- On big random maps no optimum is known: we give how far a tour is above the Held–Karp bound, a lower limit that no tour can go below (for 10,000,000 cities an estimate of it).Na velikih naključnih zemljevidih optimum ni znan: navedemo, za koliko je pot nad mejo Held–Karp, spodnjo mejo, pod katero ne more nobena pot (za 10.000.000 mest njeno oceno).
- LKH and Concorde ran on the same laptop, with the settings named next to each result; better settings are welcome and would be measured the same way.LKH in Concorde sta tekla na istem prenosniku, z nastavitvami, navedenimi ob vsakem izidu; boljše nastavitve so dobrodošle in bi jih izmerili na enak način.
- These are development results: they can change, and the lab log keeps every earlier figure with its date.To so razvojni izidi: lahko se spremenijo, laboratorijski dnevnik pa hrani vsako prejšnjo številko z datumom.
- You can check our tours: the downloads have our tours of nu3496, Slovenia and E1M.0, with SHA-256 sums and a short verifier in Python.Naše poti lahko preveriš: med prenosi so naše poti za nu3496, Slovenijo in E1M.0, s kontrolnimi vsotami SHA-256 in kratkim preverjevalnikom v Pythonu.
Who made itKdo je to naredil
BD × AI Lab. Our own view of the map is BD’s idea, first built by Claude in March 2026, then implemented by GPT. An addition to it was made by Claude C1 from BD’s idea, in a session BD prepared free of old TSP knowledge; BD calls it the first Claude invention. Known methods such as the edge assembly crossover (EAX) of Nagata and Kobayashi run inside. Behind it is BD’s way of working with LLMs: the Mental Arena Lab, the RHP protocol and AI8, the team of AI sessions that built and measured 8zTSP.BD × AI Lab. Naš lastni pogled na zemljevid je BD‑jeva zamisel, ki jo je marca 2026 prvi izvedel Claude, nato pa GPT. Dodatek k njemu je iz BD‑jeve zamisli naredil Claude C1 v seji, ki jo je BD odtujil od okov starega znanja o TSP; BD ga imenuje prvi Claudov izum. V jedru tečejo tudi znane metode, na primer križanje s sestavljanjem robov (EAX) Nagate in Kobayashija. Za tem je BD‑jev način dela z velikimi jezikovnimi modeli: Mental Arena Lab, protokol RHP in AI8, ekipa sej umetne inteligence, ki je 8zTSP zgradila in izmerila.

