BD × AI LAB · TSP

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

8zTSP grows from more than 60 of BD’s ideas; one of them, an addition to his own view of the map, was made by Claude. AI sessions (Claude and GPT) at BD × AI Lab implemented and measured them.8zTSP raste iz več kot 60 BD-jevih zamisli; eno od njih, dodatek k njegovemu pogledu na zemljevid, je naredil Claude. Izvedle in izmerile so jih seje AI (Claude in GPT) v BD × AI Lab.

Six leading language models know of no program like this; three wrote one and in 18 runs not one tour reached the optimum, while 8zTSP reaches it on the same two maps in every run.Šest vodilnih jezikovnih modelov takega programa ne pozna; trije so ga napisali in v 18 tekih nobena pot ni dosegla optimuma, 8zTSP ga na istih dveh zemljevidih doseže v vsakem teku.

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.

programprogramoptimum reachedoptimum doseženNicaragua (nu3496)Nikaragva (nu3496)SwitzerlandŠvica
A0 of 60 od 65.4 · 6.4 · 7.9 %5,4 · 6,4 · 7,9 %6.6 · 7.0 · 7.6 %6,6 · 7,0 · 7,6 %
B0 of 60 od 60.6 · 0.8 · 2.1 %0,6 · 0,8 · 2,1 %0.3 · 0.5 · 0.5 %0,3 · 0,5 · 0,5 %
C0 of 60 od 69.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 20optimum in every runoptimum v vsakem tekuoptimum 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.

Our tour through Slovenia’s 6,035 towns and villages, north up · Naša pot skozi 6.035 mest in vasi Slovenije, sever zgoraj
Slovenia, all 6,035 towns and villages: our tour, 8,728,190 m in straight lines, the best known tour, at most 0.006% above the optimum by Concorde’s lower bound (8zTSP, 18 Nov 2026).Slovenija, vseh 6.035 mest in vasi: naša pot, 8.728.190 m po zračnih črtah, najboljša znana pot, največ 0,006 % nad optimumom po Concordovi spodnji meji (8zTSP, 18. nov. 2026).
Our tour through Italy’s 16,862 places, north up · Naša pot skozi 16.862 krajev Italije, sever zgoraj
Italy, 16,862 places (it16862): our tour, 557,346, 0.006% above the optimum 557,315 proved with Concorde (8zTSP development build, not yet in the published program; one thread, 30 min, 18 Nov 2026).Italija, 16.862 krajev (it16862): naša pot, 557.346, 0,006 % nad optimumom 557.315, dokazanim s Concordom (razvojna gradnja 8zTSP, še ni v objavljenem programu; ena nit, 30 min, 18. nov. 2026).
Our tour through Switzerland’s 2,850 places, north up · Naša pot skozi 2.850 krajev Švice, sever zgoraj
Switzerland, 2,850 places: our tour, 7,844,951 m in straight lines, the optimum proved with Concorde and CPLEX on NEOS (8zTSP development build 326026c, not yet in the published program; one thread, seed 1, found after 75.1 s while Concorde’s proof for Slovenia ran on the other thread of the same core, 17 Nov 2026).Švica, 2.850 krajev: naša pot, 7.844.951 m po zračnih črtah, optimum, dokazan s Concordom in CPLEX na strežniku NEOS (razvojna gradnja 8zTSP 326026c, še ni v objavljenem programu; ena nit, seme 1, najdena po 75,1 s, ko je na drugi niti istega jedra tekel Concordov dokaz za Slovenijo, 17. nov. 2026).

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.

MapZemljevid8zTSPBest other program, same laptopNajboljši drug program, isti prenosnikConditionsPogoji
nu3496 · 3,496 cities: time to the optimumnu3496 · 3.496 mest: čas do optimumaabout 5 s, all 14 threadsokoli 5 s, vseh 14 nitiNagata’s GA-EAX: about 28 s as 7 copies, its best settingNagatov GA-EAX: okoli 28 s kot 7 kopij, njegova najboljša nastavitevEach 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: pomnilnikabout 48 MB, 7 threadsokoli 48 MB, 7 nitiNagata’s GA-EAX: about 1.0 GB as 7 copiesNagatov GA-EAX: okoli 1,0 GB kot 7 kopijPeak 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 mestwithin 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 nitiLKH 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 GBRace 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 brskalnikuabout 10 s, 7 workersokoli 10 s, 7 delavcevno other solver tested in a browserdrugih reševalnikov v brskalniku nismo preizkusiliMedian 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 nitthe 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 minOne 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.

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.

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

NextNaprej

Real run · 15 Nov 2026Pravi tek · 15. nov. 2026

The engine at workMotor v živo

This is a screen capture of the real 8zTSP demo running in a browser, nothing drawn by hand: nu3496 has just reached its known optimum, 96,132. More pictures and short clips, also of Slovenia and of a million cities, are on the demo page.To je zaslonski zajem pravega dema 8zTSP, ki teče v brskalniku, nič ni narisano na roko: nu3496 je pravkar dosegel svoj znani optimum 96.132. Več slik in kratkih posnetkov, tudi Slovenije in milijona mest, je na strani dema.

nu3496 (3,496 cities in Nicaragua) in the map view of the browser demo: the known optimum 96,132 is reached, and the page stops by itself. 4 workers, 15 Nov 2026.nu3496 (3.496 mest v Nikaragvi) v pogledu zemljevida dema v brskalniku: znani optimum 96.132 je dosežen in stran se sama ustavi. 4 delavci, 15. nov. 2026.

To run the demo yourself you need the password; access on request.Za lasten zagon dema je potrebno geslo; dostop na prošnjo.

Real run of the live demo page, 15 Nov 2026: Chromium 155 on an Intel Core i7-10875H laptop, 4 workers at low priority while the laptop was busy with other jobs; one run, not a measurement.Pravi tek žive strani dema, 15. novembra 2026: Chromium 155 na prenosniku Intel Core i7-10875H, 4 delavci z nizko prioriteto, medtem ko je bil prenosnik zaseden z drugimi opravili; en tek, ne meritev.

Credits: nu3496 — National TSP collection, University of Waterloo.Zasluga: nu3496 — zbirka National TSP, Univerza Waterloo.

All our TSP pagesVse naše strani o TSP

NowZdaj

Earlier workPrejšnje delo

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

  1. 195449 cities · Dantzig, Fulkerson, Johnson49 mest · Dantzig, Fulkerson, Johnson
  2. 19872,392 cities · Padberg, Rinaldi2.392 mest · Padberg, Rinaldi
  3. 19947,397 cities · Applegate, Bixby, Chvátal, Cook7.397 mest · Applegate, Bixby, Chvátal, Cook
  4. 199813,509 cities in the USA · the same team13.509 mest v ZDA · ista ekipa
  5. 200424,978 cities in Sweden · with Helsgaun24.978 mest na Švedskem · s Helsgaunom
  6. 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

How to read our numbersKako brati naše številke

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.