80 large number of gps optimizer via haversine

<div id=”gps-route-optimizer” class=”gro”>
<style>
#gps-route-optimizer{–ink:#12263a;–muted:#5d7183;–line:#dce5ec;–brand:#0567b5;–good:#087a4b;font:15px/1.45 system-ui,-apple-system,Segoe UI,Roboto,sans-serif;color:var(–ink);max-width:1080px;margin:20px auto;background:#fff;border:1px solid var(–line);border-radius:16px;box-shadow:0 8px 28px #15324a12;padding:clamp(16px,3vw,32px);box-sizing:border-box}.gro *{box-sizing:border-box}.gro h2{margin:0 0 4px;font-size:25px}.gro .sub{margin:0 0 24px;color:var(–muted)}.gro label{display:block;font-weight:700;margin:17px 0 7px}.gro input,.gro textarea{width:100%;border:1px solid #b9c9d5;border-radius:9px;padding:11px 12px;font:inherit;color:var(–ink);background:#fff}.gro textarea{height:230px;resize:vertical}.gro input:focus,.gro textarea:focus{outline:3px solid #0567b530;border-color:var(–brand)}.gro .hint{font-size:12px;color:var(–muted);margin-top:5px}.gro .actions{display:flex;gap:10px;flex-wrap:wrap;margin:20px 0}.gro button{border:0;border-radius:9px;padding:11px 16px;font:700 14px/1 system-ui;cursor:pointer;background:var(–brand);color:#fff}.gro button:hover{filter:brightness(.94)}.gro button:disabled{opacity:.55;cursor:not-allowed}.gro button.secondary{background:#e8f1f8;color:#155177}.gro button.danger{background:#a92d32}.gro .panel{border:1px solid var(–line);border-radius:10px;padding:14px;margin-top:16px;background:#fbfdff}.gro .status{white-space:pre-wrap;min-height:24px;color:#29465b}.gro .error{border-color:#e7aaaa;background:#fff8f8;color:#8b1d24}.gro .ok{border-color:#add8c3;background:#f5fcf8;color:#17623e}.gro .hide{display:none}.gro .metrics{display:grid;grid-template-columns:repeat(4,minmax(140px,1fr));gap:10px;margin-top:14px}.gro .metric{border:1px solid var(–line);border-radius:9px;padding:10px;background:#fff}.gro .metric b{display:block;font-size:18px}.gro .metric span{font-size:12px;color:var(–muted)}.gro .table-wrap{overflow:auto;max-height:520px;margin-top:14px;border:1px solid var(–line);border-radius:9px}.gro table{border-collapse:collapse;width:100%;min-width:430px}.gro th,.gro td{text-align:left;padding:9px 12px;border-bottom:1px solid #edf1f4}.gro th{position:sticky;top:0;background:#f2f7fb}.gro .pager{display:flex;align-items:center;gap:10px;margin-top:12px}.gro .pager span{color:var(–muted);font-size:13px}@media(max-width:720px){.gro .metrics{grid-template-columns:repeat(2,minmax(0,1fr))}}@media(max-width:560px){.gro button{flex:1}.gro textarea{height:190px}}
</style>

<h2>GPS Route Optimizer</h2>
<p class=”sub”>
Browser-only fixed-start open-route optimization. This version uses an LKH-style variable-depth k-opt search with backtracking, 1-tree α-nearness candidates, randomized kicks, and multiple runs. No maps or routing APIs are used.
</p>

<label for=”gro-start”>Start Point</label>
<input id=”gro-start” value=”33.5871849, 73.1193211″ inputmode=”text” aria-describedby=”gro-start-hint”>
<div id=”gro-start-hint” class=”hint”>
Latitude, longitude — e.g. 33.5871849, 73.1193211
</div>

<label for=”gro-locations”>Delivery Locations</label>
<textarea id=”gro-locations” spellcheck=”false” placeholder=”33.600123,73.110456&#10;33.612345,73.125678&#10;33.590111,73.140222″></textarea>
<div id=”gro-count” class=”hint”>0 valid delivery locations detected.</div>

<div class=”actions”>
<button id=”gro-run” type=”button”>OPTIMIZE ROUTE</button>
<button id=”gro-cancel” class=”danger hide” type=”button”>Cancel Optimization</button>
</div>

<div id=”gro-message” class=”panel hide” role=”alert”></div>
<div id=”gro-progress” class=”panel status” aria-live=”polite”>Ready. Add one coordinate per line.</div>

<section id=”gro-results” class=”hide”>

<div class=”metrics” id=”gro-metrics”></div>

<h2 style=”margin-top:26px”>Optimized Route</h2>

<div class=”table-wrap”>
<table>
<thead>
<tr>
<th>#</th>
<th>Latitude</th>
<th>Longitude</th>
</tr>
</thead>
<tbody id=”gro-route-body”></tbody>
</table>
</div>

<div class=”pager”>
<button id=”gro-prev” class=”secondary” type=”button”>Previous</button>
<span id=”gro-page”></span>
<button id=”gro-next” class=”secondary” type=”button”>Next</button>
</div>

<div class=”actions”>
<button id=”gro-copy” class=”secondary” type=”button”>Copy Optimized GPS</button>
<button id=”gro-csv” class=”secondary” type=”button”>Download CSV</button>
</div>

</section>

<script>
(()=>{
‘use strict’;

const root=document.currentScript.parentElement,
$=s=>root.querySelector(s);

const
startEl=$(‘#gro-start’),
locations=$(‘#gro-locations’),
count=$(‘#gro-count’),
run=$(‘#gro-run’),
cancel=$(‘#gro-cancel’),
msg=$(‘#gro-message’),
progress=$(‘#gro-progress’),
results=$(‘#gro-results’),
tbody=$(‘#gro-route-body’),
metrics=$(‘#gro-metrics’);

let worker=null,
routeData=null,
page=0;

const PAGE=250;
const MAX_POINTS=10000;

function coord(s){
const m=String(s).trim().match(/^\s*([+-]?(?:\d+(?:\.\d*)?|\.\d+))\s*(?:,|\s+)\s*([+-]?(?:\d+(?:\.\d*)?|\.\d+))\s*$/);

if(!m)return null;

const a=+m[1];
const b=+m[2];

return Number.isFinite(a)&&
Number.isFinite(b)&&
a>=-90&&
a<=90&&
b>=-180&&
b<=180
?[a,b]:null;
}

function list(a){
return a.slice(0,25).join(‘, ‘)+
(a.length>25?’ … (‘+a.length+’ total)’:”);
}

function notice(text,kind){
msg.textContent=text;
msg.className=’panel ‘+kind;
}

function parse(show){

const lines=locations.value.replace(/\r/g,”).split(‘\n’);
const valid=[];
const validGps=[];
const invalid=[];
const duplicates=[];
const seen=new Set;

lines.forEach((line,i)=>{

if(!line.trim())return;

const p=coord(line);

if(!p){
invalid.push(i+1);
return;
}

const k=p[0].toFixed(8)+’,’+p[1].toFixed(8);

if(seen.has(k)){
duplicates.push(i+1);
}
else{
seen.add(k);
valid.push(p);
validGps.push(line.trim());
}

});

const extra=duplicates.length
?’ (‘+duplicates.length+’ duplicate’+(duplicates.length===1?”:’s’)+’ will be removed).’
:”;

count.textContent=
valid.length+
‘ valid delivery location’+
(valid.length===1?”:’s’)+
‘ detected’+
extra;

if(valid.length>MAX_POINTS)
count.textContent+=’ Maximum supported input is ‘+MAX_POINTS+’.’;

if(show&&(invalid.length||duplicates.length)){

const parts=[];

if(invalid.length)
parts.push(
‘Invalid coordinate line’+
(invalid.length===1?”:’s’)+
‘: ‘+list(invalid)+’.’
);

if(duplicates.length)
parts.push(
‘Duplicate line’+
(duplicates.length===1?”:’s’)+
‘ removed: ‘+list(duplicates)+’.’
);

notice(
parts.join(‘ ‘),
invalid.length?’error’:’ok’
);

}

return{
valid,
validGps,
invalid,
duplicates
};
}

locations.addEventListener(
‘input’,
()=>parse(false)
);

function setRunning(on){
run.disabled=on;
cancel.classList.toggle(‘hide’,!on);
}

function fmt(m){
return m<1000
?m.toFixed(0)+’ m’
:(m/1000).toFixed(2)+’ km’;
}

function render(){

if(!routeData)return;

const{
lat,
lon,
order,
start
}=routeData;

const from=page*PAGE;
const to=Math.min(
order.length,
from+PAGE
);

let html=
‘<tr>’+
‘<td>Start</td>’+
‘<td>’+start[0]+'</td>’+
‘<td>’+start[1]+'</td>’+
‘</tr>’;

for(let i=from;i<to;i++){

const n=order[i];

html+=
‘<tr>’+
‘<td>’+(i+1)+'</td>’+
‘<td>’+lat[n].toFixed(7)+'</td>’+
‘<td>’+lon[n].toFixed(7)+'</td>’+
‘</tr>’;
}

tbody.innerHTML=html;

$(‘#gro-page’).textContent=
‘Stops ‘+(from+1)+’–’+to+
‘ of ‘+order.length;

$(‘#gro-prev’).disabled=page===0;
$(‘#gro-next’).disabled=to>=order.length;
}

$(‘#gro-prev’).onclick=()=>{
if(page){
page–;
render();
}
};

$(‘#gro-next’).onclick=()=>{
if((page+1)*PAGE<routeData.order.length){
page++;
render();
}
};

run.onclick=()=>{

const start=coord(startEl.value);
const p=parse(true);

if(!start){
notice(
‘Start Point must be a valid latitude and longitude.’,
‘error’
);
return;
}

if(p.invalid.length){
notice(
‘Fix the invalid delivery line’+
(p.invalid.length===1?”:’s’)+
‘ before optimizing: ‘+
list(p.invalid)+’.’,
‘error’
);
return;
}

if(p.valid.length>MAX_POINTS){
notice(
‘The browser version is capped at ‘+
MAX_POINTS+
‘ delivery locations.’,
‘error’
);
return;
}

if(!p.valid.length){
notice(
‘Enter at least one valid delivery location.’,
‘error’
);
return;
}

notice(”,’hide’);
startJob(
start,
p.valid,
startEl.value.trim(),
p.validGps
);
};

function startJob(
start,
points,
startGps,
gps
){

setRunning(true);

results.classList.add(‘hide’);

progress.textContent=
‘Preparing ‘+points.length+
‘ delivery coordinates…’;

const lat=new Float64Array(points.length);
const lon=new Float64Array(points.length);

points.forEach((p,i)=>{
lat[i]=p[0];
lon[i]=p[1];
});

const source=
‘(‘+workerMain.toString()+’)()’;

const blob=new Blob(
[source],
{type:’text/javascript’}
);

worker=new Worker(
URL.createObjectURL(blob)
);

worker.onmessage=e=>{

const d=e.data;

if(d.type===’progress’){

progress.textContent=d.text;

}

else if(d.type===’error’){

notice(
d.message,
‘error’
);

finish();

}

else if(d.type===’done’){

routeData={
start,
startGps,
gps,
lat:new Float64Array(d.lat),
lon:new Float64Array(d.lon),
order:new Int32Array(d.order)
};

showDone(d);

autoCopyOptimizedGPS();

finish();

}

};

worker.onerror=()=>{

notice(
‘The optimizer worker stopped unexpectedly. Try a modern browser with sufficient memory.’,
‘error’
);

finish();

};

worker.postMessage(
{
start,
lat:lat.buffer,
lon:lon.buffer
},
[
lat.buffer,
lon.buffer
]
);
}

function finish(){

if(worker){
worker.terminate();
worker=null;
}

setRunning(false);
}

cancel.onclick=()=>{

if(worker){
worker.terminate();
worker=null;
}

progress.textContent=
‘Optimization cancelled. No route was exported.’;

setRunning(false);
};

function showDone(d){

metrics.innerHTML=[

[‘Locations’,d.count],

[‘Initial Distance’,fmt(d.initial)],

[‘Final Distance’,fmt(d.final)],

[‘Improvement’,d.improvement.toFixed(2)+’%’],

[‘Optimization Time’,
(d.ms/1000).toFixed(1)+’ s’
],

[‘LKH Runs’,d.runs],

[‘Accepted k-opt’,d.moves],

[‘2-opt Moves’,d.twoOptMoves||0],

[‘Max Move Depth’,d.maxDepth]

].map(x=>

‘<div class=”metric”>’+
‘<b>’+x[1]+'</b>’+
‘<span>’+x[0]+'</span>’+
‘</div>’
).join(”);

page=0;

render();

results.classList.remove(‘hide’);

progress.textContent=
‘Complete — ‘+
d.runs+
‘ LKH-style runs, ‘+
d.moves+
‘ accepted variable-depth moves.’;
}

function gpsText(){

const r=routeData;

const a=[
r.startGps
];

for(const n of r.order){

a.push(
r.gps[n]
);

}

return a.join(‘\n’)+’\n’;
}

async function autoCopyOptimizedGPS(){

try{

await navigator.clipboard.writeText(
gpsText()
);

progress.textContent=
‘Complete — optimized GPS copied to clipboard automatically.’;

}
catch(e){

progress.textContent=
‘Complete — route optimized. Click “Copy Optimized GPS” to copy the GPS.’;
}

}

$(‘#gro-copy’).onclick=async()=>{

try{

await navigator.clipboard.writeText(
gpsText()
);

progress.textContent=
‘Optimized GPS copied to your clipboard.’;

}
catch(e){

const t=document.createElement(‘textarea’);

t.value=gpsText();

document.body.append(t);

t.select();

document.execCommand(‘copy’);

t.remove();

progress.textContent=
‘Optimized GPS copied to your clipboard.’;

}

};

$(‘#gro-csv’).onclick=()=>{

const b=new Blob(
[gpsText()],
{type:’text/csv’}
);

const a=document.createElement(‘a’);

a.href=URL.createObjectURL(b);

a.download=’optimized-gps-route.csv’;

a.click();

setTimeout(
()=>URL.revokeObjectURL(a.href),
500
);

};

/*
Browser implementation of the core LKH ideas:

1. A fixed-start open path is transformed into a cycle by adding
a zero-cost duplicate of the start.

2. The candidate backbone is based on an exact minimum 1-tree
for the spherical/Haversine geometry. The MST edge ordering
is computed with unit-sphere chord distances, which preserve
the ordering of great-circle distances.

3. α-nearness is computed using:
alpha(i,j) = c(i,j) – maximum edge on the 1-tree path i..j

4. Search uses sequential alternating X/Y edge exchanges:
X1, Y1, X2, Y2, …, Xk, Yk

5. Search is recursive and backtracks through candidate choices.

6. Positive gain pruning is used before deeper continuation.

7. Randomized double-bridge style kicks provide new starting tours.

8. Multiple independent runs are used.

Important:
This is NOT a binary/line-for-line port of Helsgaun’s official
LKH-3 source code. It is a browser implementation of the main
Lin-Kernighan-Helsgaun search concepts and is intentionally not
labelled as the official LKH solver.
*/

function workerMain(){

‘use strict’;

const R=6371008.8;
const INF=1e100;

let lat;
let lon;

let N;
let M;

let root;
let dup;

let cands;

let moves=0;
let lastPost=0;

let rngState=1;

let deadline=0;
let maxDepth=5;

let searchAborts=0;

const rad=x=>
x*Math.PI/180;

function rng(){

rngState=
(
rngState*1664525+
1013904223
)>>>0;

return rngState/4294967296;
}

function hav(a,b){

if(
(a===root&&b===dup)||
(a===dup&&b===root)
)
return 0;

const p=rad(lat[a]);
const q=rad(lat[b]);

const u=rad(
lat[b]-lat[a]
);

const v=rad(
lon[b]-lon[a]
);

const h=
Math.sin(u/2)**2+
Math.cos(p)*
Math.cos(q)*
Math.sin(v/2)**2;

return 2*
R*
Math.atan2(
Math.sqrt(h),
Math.sqrt(
Math.max(
0,
1-h
)
)
);
}

function post(text,force){

const now=performance.now();

if(
force||
now-lastPost>300
){

lastPost=now;

self.postMessage({
type:’progress’,
text
});

}

}

function edgeKey(a,b){

return a<b
?a*M+b
:b*M+a;
}

function isFixed(a,b){

return(
(a===root&&b===dup)||
(a===dup&&b===root)
);

}

/*
Build a geographically local raw candidate graph.
This is intentionally only the candidate pool; α-values are
subsequently calculated against the exact 1-tree.
*/

function gridCandidates(K){

post(
‘Building geographic neighbor graph…’,
true
);

const count=M;

const meanLat=
lat.reduce(
(s,v)=>s+v,
0
)/count;

const scale=Math.max(
0.05,
Math.cos(rad(meanLat))
);

const xs=new Float64Array(count);
const ys=new Float64Array(count);

let xmin=INF;
let xmax=-INF;
let ymin=INF;
let ymax=-INF;

for(let i=0;i<count;i++){

xs[i]=lon[i]*scale;
ys[i]=lat[i];

if(xs[i]<xmin)xmin=xs[i];
if(xs[i]>xmax)xmax=xs[i];

if(ys[i]<ymin)ymin=ys[i];
if(ys[i]>ymax)ymax=ys[i];

}

const span=Math.max(
xmax-xmin,
ymax-ymin,
0.000001
);

const cell=Math.max(
span/Math.sqrt(count)*1.8,
0.00005
);

const grid=new Map();

const key=(x,y)=>
x+’,’+y;

const cx=new Int32Array(count);
const cy=new Int32Array(count);

for(let i=0;i<count;i++){

const x=Math.floor(
(xs[i]-xmin)/cell
);

const y=Math.floor(
(ys[i]-ymin)/cell
);

cx[i]=x;
cy[i]=y;

const k=key(x,y);

let a=grid.get(k);

if(!a){

a=[];

grid.set(k,a);

}

a.push(i);

}

const out=
Array.from(
{length:count},
()=>[]
);

const target=
Math.min(
Math.max(K*4,48),
96
);

for(let i=0;i<count;i++){

const pool=[];
const seen=new Set();

let radius=0;

while(
pool.length<target&&
radius<12
){

for(
let dx=-radius;
dx<=radius;
dx++
){

for(
let dy=-radius;
dy<=radius;
dy++
){

if(
Math.max(
Math.abs(dx),
Math.abs(dy)
)!==radius
)
continue;

const a=
grid.get(
key(
cx[i]+dx,
cy[i]+dy
)
);

if(!a)
continue;

for(const j of a){

if(
j!==i&&
!seen.has(j)
){

seen.add(j);

pool.push(j);

}

}

}

}

radius++;

}

if(pool.length<target){

const yy=lat[i];

const idx=[];

for(
let j=0;
j<count;
j++
)
if(j!==i)
idx.push(j);

idx.sort(
(a,b)=>
Math.abs(lat[a]-yy)-
Math.abs(lat[b]-yy)
);

for(
let z=0;
z<Math.min(
idx.length,
target*2
)&&
pool.length<target;
z++
){

if(
!seen.has(idx[z])
){

seen.add(idx[z]);

pool.push(idx[z]);

}

}

}

pool.sort(
(a,b)=>
hav(i,a)-
hav(i,b)
);

for(
let z=0;
z<Math.min(
K,
pool.length
);
z++
){

out[i].push([
pool[z],
hav(i,pool[z])
]);

}

if(
(i&255)===0
){

post(
‘Neighbor graph: ‘+
i+’/’+count
);

}

}

return out;

}

/*
Exact minimum spanning tree on the non-root nodes.

The edge ordering for Prim is calculated from squared chord
distance on the unit sphere. Since this is a strictly increasing
transform of angular/geographic distance, the resulting MST
edge ordering is the same as for Haversine distance.

The actual tree-edge costs stored for α-nearness are Haversine.
*/

/*
Build the exact minimum 1-tree and compute exact
unpenalized α-nearness values.

Node layout:

0 … N-1 = delivery nodes
N = real start/root
N+1 = duplicate start

The 1-tree is constructed as:

MST on every node except root
+
root -> duplicate-start, cost 0
+
root -> nearest delivery

For ordinary non-root edges:

alpha(i,j) =
c(i,j) – maximum-MST-edge-on-path(i,j)

For root edges:

alpha(root, nearest) = 0
alpha(root, j) =
c(root,j) – rootSecondCost

The α calculation is GLOBAL:
every possible non-fixed edge is examined.
There is no geographic RAW_K pre-filter.

This is an exact α-nearness calculation for the
unpenalized spherical/Haversine 1-tree.
*/

function buildOneTree(ALPHA_K,geoCands,GEO_K){

post(
‘Computing exact minimum 1-tree…’,
true
);

/*
The MST must contain EVERY node except the distinguished root.

That means:

deliveries 0 … N-1
duplicate start N+1

The real root N is excluded.
*/

const treeNodes=[];

for(
let v=0;
v<M;
v++
){

if(v!==root){

treeNodes.push(v);

}

}

const V=treeNodes.length;

if(V<1){

throw new Error(
‘1-tree requires at least one non-root node.’
);

}

/*
Unit-sphere coordinates.

Squared chord distance has the same ordering as
great-circle/Haversine distance, so Prim produces
the same MST for the spherical metric.
*/

const ux=
new Float64Array(M);

const uy=
new Float64Array(M);

const uz=
new Float64Array(M);

for(
const v of treeNodes
){

const p=rad(lat[v]);
const q=rad(lon[v]);

ux[v]=
Math.cos(p)*
Math.cos(q);

uy[v]=
Math.cos(p)*
Math.sin(q);

uz[v]=
Math.sin(p);

}

/*
Exact dense Prim MST on all non-root nodes.
*/

const parent=
new Int32Array(M);

const used=
new Uint8Array(M);

const best=
new Float64Array(M);

parent.fill(-1);
best.fill(INF);

const first=
treeNodes[0];

best[first]=0;

const adj=
Array.from(
{length:M},
()=>[]
);

const mstCost=
new Float64Array(M);

mstCost.fill(0);

for(
let it=0;
it<V;
it++
){

let v=-1;
let bestW=INF;

/*
Find the unused tree node with minimum
connection cost.
*/

for(
let q=0;
q<V;
q++
){

const j=
treeNodes[q];

if(
!used[j] &&
best[j]<bestW
){

bestW=best[j];
v=j;

}

}

if(v<0){

throw new Error(
‘Exact MST construction failed.’
);

}

used[v]=1;

/*
Add the selected MST edge.
*/

if(parent[v]!==-1){

const p=parent[v];

const w=
hav(v,p);

mstCost[v]=w;

adj[v].push([
p,
w
]);

adj[p].push([
v,
w
]);

}

/*
Relax every remaining vertex.

Squared chord distance is used ONLY for
MST ordering.
*/

const vx=ux[v];
const vy=uy[v];
const vz=uz[v];

for(
let q=0;
q<V;
q++
){

const j=
treeNodes[q];

if(used[j])
continue;

const dx=
vx-ux[j];

const dy=
vy-uy[j];

const dz=
vz-uz[j];

const w=
dx*dx+
dy*dy+
dz*dz;

if(w<best[j]){

best[j]=w;
parent[j]=v;

}

}

if(
(it&255)===0
){

post(
‘Exact 1-tree MST: ‘+
(it+1)+’/’+V
);

}

}

/*
Find the cheapest REAL root -> delivery edge.

IMPORTANT:
Do not include root itself.
Do not include duplicate start.
*/

let nearest=0;

let rootSecond=
hav(
root,
0
);

for(
let j=1;
j<N;
j++
){

const z=
hav(root,j);

if(z<rootSecond){

rootSecond=z;
nearest=j;

}

}

/*
We now have the exact 1-tree:

MST(treeNodes)
+
root -> duplicate
+
root -> nearest delivery

The root->duplicate edge is fixed and has cost 0.
*/

/*
—————————————————————-
Exact maximum-edge-on-MST-path calculator
—————————————————————-

For every source node, traverse the entire MST once.

For a given source i, when visiting j:

beta(i,j) =
maximum MST edge on path i -> j

Then:

alpha(i,j) =
c(i,j) – beta(i,j)

This is O(M^2), but it is genuinely global:
NO geographic candidate pool is used.
—————————————————————-
*/

/*
Reusable DFS stacks.
*/

const stackNode=
new Int32Array(V);

const stackParent=
new Int32Array(V);

const stackBeta=
new Float64Array(V);

/*
Small max-heap used to retain only the K
smallest alpha candidates for each source.

The heap root is the WORST candidate currently kept.
*/

function heapWorse(
aAlpha,
aCost,
bAlpha,
bCost
){

return(
aAlpha>bAlpha||
(
aAlpha===bAlpha &&
aCost>bCost
)
);

}

function heapPush(
nodes,
alphas,
costs,
size,
node,
alphaValue,
costValue,
capacity
){

if(size<capacity){

let i=size;

nodes[i]=node;
alphas[i]=alphaValue;
costs[i]=costValue;

size++;

while(i>0){

const p=
Math.floor((i-1)/2);

if(
!heapWorse(
alphas[p],
costs[p],
alphas[i],
costs[i]
)
)
break;

[
nodes[p],
nodes[i]
]=[
nodes[i],
nodes[p]
];

[
alphas[p],
alphas[i]
]=[
alphas[i],
alphas[p]
];

[
costs[p],
costs[i]
]=[
costs[i],
costs[p]
];

i=p;

}

return size;

}

/*
Heap is full.

Ignore the new edge if it is not
better than the current worst edge.
*/

if(
!heapWorse(
alphas[0],
costs[0],
alphaValue,
costValue
)
){

return size;

}

/*
Replace heap root.
*/

nodes[0]=node;
alphas[0]=alphaValue;
costs[0]=costValue;

let i=0;

while(true){

const l=i*2+1;
const r=i*2+2;

let w=i;

if(
l<size &&
heapWorse(
alphas[l],
costs[l],
alphas[w],
costs[w]
)
){

w=l;

}

if(
r<size &&
heapWorse(
alphas[r],
costs[r],
alphas[w],
costs[w]
)
){

w=r;

}

if(w===i)
break;

[
nodes[i],
nodes[w]
]=[
nodes[w],
nodes[i]
];

[
alphas[i],
alphas[w]
]=[
alphas[w],
alphas[i]
];

[
costs[i],
costs[w]
]=[
costs[w],
costs[i]
];

i=w;

}

return size;

}

/*
Sort the retained heap into increasing alpha order.
*/

function sortHeap(
nodes,
alphas,
costs,
size
){

const arr=[];

for(
let i=0;
i<size;
i++
){

arr.push([
nodes[i],
alphas[i],
costs[i]
]);

}

arr.sort(
(a,b)=>
a[1]-b[1]||
a[2]-b[2]
);

return arr;

}

/*
Capacity cannot exceed the number of possible
non-self, non-fixed candidates.
*/

const K=
Math.max(
1,
Math.min(
ALPHA_K,
M-2
)
);

/*
Merge α-nearness candidates with geographically
nearby candidates.

α candidates remain first.
Geographic candidates are then added if they
are not already present.

The duplicate-start node is never allowed as
an ordinary search candidate.
*/

function mergeHybrid(
source,
alphaList
){

const out=[];
const seen=new Set;

for(
const v of alphaList
){

if(
v===source||
v===dup
)
continue;

if(
!seen.has(v)
){

seen.add(v);
out.push(v);

}

}

const geoList=
geoCands[source]||[];

for(
const item of geoList
){

const v=
Array.isArray(item)
?item[0]
:item;

if(
v===source||
v===dup
)
continue;

if(
source===dup&&
v===root
)
continue;

if(
!seen.has(v)
){

seen.add(v);
out.push(v);

}

}

return out;

}

/*
Compute exact α candidates for every node.
*/

for(

let source=0;
source<M;
source++
){

/*
The root has special 1-tree α-values.
*/

if(source===root){

const heapNodes=
new Int32Array(K);

const heapAlpha=
new Float64Array(K);

const heapCosts=
new Float64Array(K);

let heapSize=0;

for(
const j of treeNodes
){

/*
The duplicate-start edge is fixed and is
not a candidate.
*/

if(j===dup)
continue;

const d=
hav(root,j);

const alphaValue=
j===nearest
?0
:Math.max(
0,
d-rootSecond
);

heapSize=
heapPush(
heapNodes,
heapAlpha,
heapCosts,
heapSize,
j,
alphaValue,
d,
K
);

}

const ordered=
sortHeap(
heapNodes,
heapAlpha,
heapCosts,
heapSize
);

cands[root]=
mergeHybrid(
root,
ordered.map(
x=>x[0]
)
);

continue;

}

/*
Non-root source.

Every other MST node is examined.
*/

const heapNodes=
new Int32Array(K);

const heapAlpha=
new Float64Array(K);

const heapCosts=
new Float64Array(K);

let heapSize=0;

/*
DFS from source through the COMPLETE MST.

Each visited node gets its exact
maximum edge cost along source -> node.
*/

let sp=0;

stackNode[sp]=source;
stackParent[sp]=-1;
stackBeta[sp]=0;
sp++;

while(sp>0){

sp–;

const v=
stackNode[sp];

const prev=
stackParent[sp];

const beta=
stackBeta[sp];

/*
Do not consider the source itself.
*/

if(v!==source){

const d=
hav(source,v);

const alphaValue=
Math.max(
0,
d-beta
);

heapSize=
heapPush(
heapNodes,
heapAlpha,
heapCosts,
heapSize,
v,
alphaValue,
d,
K
);

}

/*
Continue through MST neighbors.
*/

const neighbors=
adj[v];

for(
let ni=0;
ni<neighbors.length;
ni++
){

const u=
neighbors[ni][0];

const w=
neighbors[ni][1];

if(u===prev)
continue;

stackNode[sp]=u;
stackParent[sp]=v;

stackBeta[sp]=
Math.max(
beta,
w
);

sp++;

}

}

/*
Now handle the real root edge separately.

The fixed root->duplicate edge is excluded.
*/

if(source!==dup){

const dRoot=
hav(
source,
root
);

const rootAlpha=
Math.max(
0,
dRoot-rootSecond
);

/*
If root already appears in the K exact candidates,
heapPush will deduplicate naturally below.
*/

heapSize=
heapPush(
heapNodes,
heapAlpha,
heapCosts,
heapSize,
root,
rootAlpha,
dRoot,
K
);

}

/*
Convert exact top-K α values into the candidate set.
*/

const ordered=
sortHeap(
heapNodes,
heapAlpha,
heapCosts,
heapSize
);

cands[source]=
mergeHybrid(
source,
ordered.map(
x=>x[0]
)
);

if(
(source&255)===0
){

post(
‘Exact α-nearness: ‘+
source+’/’+M
);

}

}

/*
The fixed zero-cost root->duplicate edge is
not used as an ordinary search candidate.
It is structural only.
*/

cands[root]=
cands[root].filter(
v=>v!==dup
);

cands[dup]=
cands[dup].filter(
v=>v!==root
);

post(
‘Hybrid candidates ready: ‘+
ALPHA_K+
‘ α-nearness + up to ‘+
GEO_K+
‘ geographic-neighbor candidates/node.’,
true
);

}

function cycleLength(route){

let z=0;

for(
let i=0;
i<route.length-1;
i++
){

z+=hav(
route[i],
route[i+1]
);

}

z+=hav(
route[route.length-1],
route[0]
);

return z;
}

/*
Construct a randomized nearest-neighbor initial tour.
Node root is the real start.
Node dup is a second copy of start with zero closing cost.
*/

function initialTour(seed){

const used=
new Uint8Array(M);

const r=
new Int32Array(M);

r[0]=root;

used[root]=1;

let cur=root;

for(
let p=1;
p<M-1;
p++
){

let pool=
cands[cur].filter(
j=>
!used[j]&&
j!==dup
);

if(!pool.length){

pool=[];

for(
let j=1;
j<M-1;
j++
){

if(
!used[j]
){

pool.push(j);

}

}

}

pool.sort(
(a,b)=>
hav(cur,a)-
hav(cur,b)
);

const top=
Math.min(
pool.length,
seed
?Math.min(
6,
pool.length
)
:1
);

const pick=
pool[
Math.floor(
rng()*top
)
];

r[p]=pick;

used[pick]=1;

cur=pick;

}

r[M-1]=dup;

return r;

}

function posMap(route){

const p=
new Int32Array(M);

for(
let i=0;
i<M;
i++
){

p[route[i]]=i;

}

return p;

}

function tourNeighbors(
route,
v,
pos
){

const p=
pos[v];

const left=
route[
(p-1+M)%M
];

const right=
route[
(p+1)%M
];

return left===right
?[left]
:[left,right];

}

function edgeInTour(
route,
pos,
a,
b
){

return(
pos[b]===
((pos[a]+1)%M)
||
pos[a]===
((pos[b]+1)%M)
);

}

/*
Apply an alternating X/Y exchange and verify that it produces
one valid Hamiltonian cycle while retaining the fixed
root <-> duplicate-start edge.
*/

function validExchange(
route,
X,
Y
){

const adj=
Array.from(
{length:M},
()=>[]
);

/*
Remove X edges from the current tour.
*/

for(
let i=0;
i<M;
i++
){

const a=route[i];

const b=
route[
(i+1)%M
];

let removed=false;

for(
const e of X
){

if(
edgeKey(a,b)===
edgeKey(
e[0],
e[1]
)
){

removed=true;

break;

}

}

if(!removed){

adj[a].push(b);
adj[b].push(a);

}

}

/*
Add Y edges.
*/

const added=
new Set();

for(
const e of Y
){

const a=e[0];
const b=e[1];

if(
a===b||
isFixed(a,b)
)
return null;

const k=
edgeKey(a,b);

if(
added.has(k)
)
return null;

added.add(k);

adj[a].push(b);
adj[b].push(a);

}

/*
Every node must have degree two.
*/

for(
let i=0;
i<M;
i++
){

if(
adj[i].length!==2
)
return null;

}

/*
Traverse the resulting cycle.

The fixed root <-> duplicate-start edge must remain.
The returned representation is:

root -> deliveries -> duplicate
*/

const out=
new Int32Array(M);

const first=
adj[root].find(
v=>v!==dup
);

if(first==null)
return null;

out[0]=root;

let prev=root;
let cur=first;

for(
let i=1;
i<M;
i++
){

out[i]=cur;

const a=
adj[cur][0];

const b=
adj[cur][1];

const next=
a===prev
?b
:a;

prev=cur;
cur=next;

if(
i<M-1 &&
cur===root
)
return null;

}

if(
cur!==root ||
out[M-1]!==dup
)
return null;

return out;

}

/*
Return the position of the tour edge (a,b).

The result is the index i such that:

route[i] -> route[(i+1)%M]

is the edge.
*/

function tourEdgeIndex(
a,
b,
pos
){

const pa=pos[a];
const pb=pos[b];

if(
(pa+1)%M===pb
)
return pa;

if(
(pb+1)%M===pa
)
return pb;

return -1;

}

/*
Fast LK feasibility test.

X contains broken tour edges.
Y contains already-added non-tour edges.
close is the prospective closing edge:

(last,t1)

After removing X and adding Y + close,
the result must be ONE Hamiltonian cycle.

This avoids constructing an M-node adjacency graph for
every recursive test. Only the k affected tour segments
are examined.
*/

function feasibleSequentialClose(
route,
pos,
X,
Y,
close
){

if(
!close||
close[0]===close[1]||
isFixed(
close[0],
close[1]
)
)
return false;

const xSet=
new Set();

const breakIdx=[];

const delta=
new Map();

const bump=(
v,
d
)=>{

delta.set(
v,
(delta.get(v)||0)+d
);

};

/*
Remove X edges from the current tour.
Each removed edge creates one path component.
*/

for(
const e of X
){

const a=e[0];
const b=e[1];

const k=
edgeKey(a,b);

if(
xSet.has(k)||
isFixed(a,b)||
!edgeInTour(
route,
pos,
a,
b
)
)
return false;

const idx=
tourEdgeIndex(
a,
b,
pos
);

if(idx<0)
return false;

xSet.add(k);
breakIdx.push(idx);

bump(a,-1);
bump(b,-1);

}

if(!breakIdx.length)
return false;

/*
Add Y edges plus the final closing edge.

The intermediate Y edges must connect
different path components.

The FINAL closing edge is different:
by that point all path components should
already belong to one connected component,
and the final edge closes that component
into one Hamiltonian cycle.
*/

const added=
Y.concat([
close
]);

const addedSet=
new Set();

for(
const e of added
){

const a=e[0];
const b=e[1];

if(
a===b||
isFixed(a,b)
)
return false;

const k=
edgeKey(a,b);

if(
xSet.has(k)||
addedSet.has(k)
)
return false;

if(
edgeInTour(
route,
pos,
a,
b
)
)
return false;

addedSet.add(k);

bump(a,1);
bump(b,1);

}

/*
Every touched vertex must remain degree two.
*/

for(
const d of delta.values()
){

if(d!==0)
return false;

}

/*
Deleting k edges from a single Hamiltonian cycle
creates exactly k path components.
*/

breakIdx.sort(
(a,b)=>a-b
);

const k=
breakIdx.length;

const parent=
new Int32Array(k);

for(
let i=0;
i<k;
i++
)
parent[i]=i;

function find(x){

let r=x;

while(
parent[r]!==r
){

parent[r]=
parent[parent[r]];

r=parent[r];

}

return r;

}

function unite(a,b){

a=find(a);
b=find(b);

if(a!==b)
parent[b]=a;

}

/*
Return the component containing the tour
position p after the X edges are removed.

If the removed tour-edge positions are:

b1 < b2 < … < bk

then each remaining segment is one component.
*/

function componentAtPosition(p){

let lo=0;
let hi=k;

while(lo<hi){

const mid=
(lo+hi)>>1;

if(
breakIdx[mid]<p
){

lo=mid+1;

}
else{

hi=mid;

}

}

return(
lo-1+k
)%k;

}

/*
Process added edges in order.

Y1 … Y(k-1):
each must connect two DIFFERENT components.

Final close:
all components must already be connected,
so the final edge should connect the SAME
union-find component and close the cycle.
*/

for(
let i=0;
i<added.length;
i++
){

const e=added[i];

const ca=
componentAtPosition(
pos[e[0]]
);

const cb=
componentAtPosition(
pos[e[1]]
);

const ra=find(ca);
const rb=find(cb);

/*
Intermediate Y edge:
must merge two different components.
*/

if(
i<added.length-1
){

if(
ra===rb
)
return false;

unite(
ra,
rb
);

}

/*
Final closing edge:
all k path components should now have
been merged into one component.

The final edge closes that component.
*/

else{

if(
ra!==rb
)
return false;

}

}

/*
Final connectivity check:
there must be exactly one component.
*/

const base=find(0);

for(
let i=1;
i<k;
i++
){

if(
find(i)!==base
)
return false;

}

return true;

}

/*
Recursive variable-depth Lin-Kernighan search.

State:

X = broken tour edges
Y = added non-tour edges

At depth i:

X_i = (t_(2i-1), t_(2i))
Y_i = (t_(2i), t_(2i+1))

The search:

X1
Y1
X2
Y2
…
Xk
Yk

The algorithm:

1. keeps cumulative positive gain;
2. tries a legal close-up at every depth;
3. requires close-up feasibility when selecting X_i;
4. backtracks through candidate Y choices;
5. backtracks through alternate X choices;
6. records the best improvement instead of returning
at the first improvement.
*/

function extendLK(
route,
pos,
t1,
last,
depth,
gain,
X,
Y,
usedX,
usedY,
usedNodes,
depthLimit,
passDeadline,
bestState
){

if(
performance.now()>=passDeadline
)
return;

/*
Try the close-up:

Y_k = (t_(2k), t1)

This is what turns the current alternating chain
into an actual k-opt move.
*/

if(
depth>=2
){

const close=[
last,
t1
];

const closeKey=
edgeKey(
last,
t1
);

const closeCost=
hav(
last,
t1
);

if(
!usedX.has(closeKey) &&
!usedY.has(closeKey) &&
!isFixed(last,t1) &&
!edgeInTour(
route,
pos,
last,
t1
)
){

const finalGain=
gain-closeCost;

/*
Positive improvement and better than the best
exchange already found.
*/

if(
finalGain>1e-6 &&
finalGain>
bestState.gain+1e-6
){

const Yfinal=
Y.concat([
close
]);

/*
The close-up should already be feasible because
X_i was selected using the LK feasibility rule.
Validate again before accepting the move.
*/

if(
feasibleSequentialClose(
route,
pos,
X,
Y,
close
)
){

const candidate=
validExchange(
route,
X,
Yfinal
);

if(candidate){

bestState.gain=
finalGain;

bestState.route=
candidate;

}

}

}

}

}

/*
Variable depth ends here.

A depth limit is only a practical browser safeguard;
the move itself is still variable-depth.
*/

if(
depth>=depthLimit
)
return;

const options=
cands[last]||[];

/*
Try candidate Y edges in α-nearness order.
*/

for(
let ci=0;
ci<options.length;
ci++
){

if(
performance.now()>=passDeadline
)
return;

const t3=
options[ci];

const yKey=
edgeKey(
last,
t3
);

/*
Y edge requirements.

t3 must be a new node.
The edge must not already be in the tour.
X/Y must remain disjoint.
*/

if(
t3===t1||
usedNodes[t3]||
usedX.has(yKey)||
usedY.has(yKey)||
isFixed(last,t3)||
edgeInTour(
route,
pos,
last,
t3
)
)
continue;

const yCost=
hav(
last,
t3
);

const gainAfterY=
gain-yCost;

/*
Lin-Kernighan positive gain criterion.

Do not descend into a branch whose cumulative
gain has already become non-positive.
*/

if(
gainAfterY<=1e-6
)
continue;

/*
X_(i+1) must currently be a tour edge incident to t3.

There are at most two such edges in a tour.
*/

const neigh=
tourNeighbors(
route,
t3,
pos
);

for(
let ni=0;
ni<neigh.length;
ni++
){

if(
performance.now()>=passDeadline
)
return;

const t4=
neigh[ni];

if(
t4===t1||
t4===last||
usedNodes[t4]
)
continue;

const xKey=
edgeKey(
t3,
t4
);

if(
usedX.has(xKey)||
usedY.has(xKey)||
isFixed(t3,t4)
)
continue;

const xCost=
hav(
t3,
t4
);

const gainAfterX=
gainAfterY+xCost;

/*
Tentatively add Y_i and X_(i+1).
*/

Y.push([
last,
t3
]);

X.push([
t3,
t4
]);

usedY.add(yKey);
usedX.add(xKey);

usedNodes[t3]=1;
usedNodes[t4]=1;

/*
This is the important LK feasibility criterion:

when X_(i+1) is selected, joining t4 to t1 must
be capable of producing a tour.

Without this test the search is only a loose
variable-depth k-opt enumerator.
*/

/*
Do not require the partial exchange to already be
closable at this depth.

A deeper LK move may need additional Y/X exchanges
before a valid closing edge exists.

The complete move is still checked by
feasibleSequentialClose() and validExchange()
when we actually attempt the close.
*/

extendLK(
route,
pos,
t1,
t4,
depth+1,
gainAfterX,
X,
Y,
usedX,
usedY,
usedNodes,
depthLimit,
passDeadline,
bestState
);

/*

Backtrack.
*/

usedNodes[t4]=0;
usedNodes[t3]=0;

usedX.delete(xKey);
usedY.delete(yKey);

X.pop();
Y.pop();

}

}

}

/*
One complete LK improvement pass.

Unlike the previous version, this:

– examines every directed starting edge until the deadline;
– examines both choices for X1;
– fully backtracks;
– records the best improving move;
– applies only the best move found during the pass.

This is the core behavior expected from the LK search,
rather than a bounded collection of 2-opt-like trials.
*/

function improveByLK(
route,
passDeadline,
depthLimit
){

const pos=
posMap(route);

const baseLength=
cycleLength(route);

const bestState={
gain:0,
route:null
};

const X=[];
const Y=[];

const usedX=
new Set();

const usedY=
new Set();

const usedNodes=
new Uint8Array(M);

/*
Every directed tour edge is a possible X1 orientation.

This is important: checking only route[i] -> route[i+1]
misses the opposite t1/t2 orientation.
*/

for(
let t1=0;
t1<M;
t1++
){

if(
performance.now()>=passDeadline
){

searchAborts++;

break;

}

const neighbors=
tourNeighbors(
route,
t1,
pos
);

for(
let ni=0;
ni<neighbors.length;
ni++
){

if(
performance.now()>=passDeadline
){

searchAborts++;

break;

}

const t2=
neighbors[ni];

if(
isFixed(t1,t2)
)
continue;

/*
Reset recursive state for this starting orientation.
*/

X.length=0;
Y.length=0;

usedX.clear();
usedY.clear();

usedNodes.fill(0);

/*
X1 = (t1,t2)
*/

const x1Key=
edgeKey(
t1,
t2
);

X.push([
t1,
t2
]);

usedX.add(x1Key);

usedNodes[t1]=1;
usedNodes[t2]=1;

const x1Gain=
hav(
t1,
t2
);

/*
Recursive LK search.

It does NOT return at the first improvement.
It keeps searching and updates bestState.
*/

extendLK(
route,
pos,
t1,
t2,
1,
x1Gain,
X,
Y,
usedX,
usedY,
usedNodes,
depthLimit,
passDeadline,
bestState
);

}

if(
(t1&127)===0
){

post(
‘LK search: starting node ‘+
t1+’/’+M+
‘\nBest gain so far: ‘+
bestState.gain.toFixed(1)+’ m’
);

}

}

/*
Apply the best improving variable-depth move found.
*/

if(
bestState.route &&
bestState.gain>1e-6
){

route.set(
bestState.route
);

moves++;

return{
changed:true,
length:
baseLength-bestState.gain
};

}

return{
changed:false,
length:baseLength
};

}

/*
Exhaustive 2-opt polishing.

The route representation is:

root -> delivery -> delivery -> … -> delivery -> dup

The root and duplicate-start remain fixed at the two ends.

For every pair of non-adjacent tour edges:

A -> B
C -> D

2-opt replaces them with:

A -> C
B -> D

and reverses the route segment B … C.

The entire set of valid edge pairs is scanned.
The best improving move is applied.
The scan repeats until no improving 2-opt move remains
or the supplied deadline is reached.
*/

/*
Parallel Exhaustive 2-opt.

The coordinator remains in the existing optimizer worker.

For every complete 2-opt pass:

1. Divide all possible i values among child workers.
2. Each child evaluates its complete j range.
3. Each child returns its best improving move.
4. The coordinator selects the global best move.
5. The coordinator performs the route reversal.
6. A new parallel pass begins.

The route therefore remains synchronized while the expensive
O(N²) neighborhood search is distributed across CPU workers.
*/

async function exhaustiveTwoOptParallel(
route,
polishDeadline
){

const totalI=
Math.max(
0,
M-3
);

if(
totalI<=0
){

return{
moves:0,
passes:0,
timedOut:false,
workers:0
};

}

/*
hardwareConcurrency is the browser’s estimate of logical
CPU concurrency.

The existing workerMain() is itself already one Worker,
so use hardwareConcurrency – 1 child workers.

This keeps roughly the reported number of logical CPUs
available to the optimization rather than unnecessarily
oversubscribing the CPU.
*/

const reportedCPUs=
Number(
navigator.hardwareConcurrency
)||2;

const workerCount=
Math.max(
1,
Math.min(
reportedCPUs-1,
totalI
)
);

const source=
‘(‘+twoOptChildMain.toString()+’)()’;

const blob=
new Blob(
[source],
{
type:’text/javascript’
}
);

const workerURL=
URL.createObjectURL(blob);

const pool=[];

function createWorker(){

return new Worker(
workerURL
);

}

/*
Create all child workers.
*/

for(
let i=0;
i<workerCount;
i++
){

pool.push(
createWorker()
);

}

/*
Terminate the entire pool safely.
*/

function terminatePool(){

for(
const w of pool
){

try{
w.terminate();
}
catch(e){}

}

URL.revokeObjectURL(
workerURL
);

}

/*
Initialize one child worker.
*/

function initWorker(w){

return new Promise(
(resolve,reject)=>{

let done=false;

const cleanup=()=>{

w.removeEventListener(
‘message’,
onMessage
);

w.removeEventListener(
‘error’,
onError
);

};

const onMessage=e=>{

if(
e.data&&
e.data.type===’ready’
){

done=true;

cleanup();

resolve();

}

else if(
e.data&&
e.data.type===’error’
){

if(!done){

done=true;

cleanup();

reject(
new Error(
e.data.message
)
);

}

}

};

const onError=err=>{

if(!done){

done=true;

cleanup();

reject(err);

}

};

w.addEventListener(
‘message’,
onMessage
);

w.addEventListener(
‘error’,
onError
);

const latCopy=
lat.slice().buffer;

const lonCopy=
lon.slice().buffer;

w.postMessage(
{
type:’init’,
M,
lat:latCopy,
lon:lonCopy
},
[
latCopy,
lonCopy
]
);

}
);

}

/*
Send one scan job to one child worker.
*/

function scanWorker(
w,
routeCopy,
iStart,
iEnd
){

return new Promise(
(resolve,reject)=>{

let done=false;

const cleanup=()=>{

w.removeEventListener(
‘message’,
onMessage
);

w.removeEventListener(
‘error’,
onError
);

};

const onMessage=e=>{

const d=e.data;

if(
d&&
d.type===’scanResult’
){

done=true;

cleanup();

resolve(d);

}

else if(
d&&
d.type===’error’
){

if(!done){

done=true;

cleanup();

reject(
new Error(
d.message
)
);

}

}

};

const onError=err=>{

if(!done){

done=true;

cleanup();

reject(err);

}

};

w.addEventListener(
‘message’,
onMessage
);

w.addEventListener(
‘error’,
onError
);

w.postMessage(
{
type:’scan’,

route:
routeCopy,

iStart,
iEnd

},
[
routeCopy
]
);

}
);

}

let movesMade=0;
let passes=0;

try{

/*
Initialize all child workers.
*/

await Promise.all(
pool.map(
w=>initWorker(w)
)
);

post(
‘Exhaustive 2-opt using ‘+
workerCount+
‘ parallel workers…’,
true
);

/*
Continue until no improving move exists.

Because the caller passes Infinity, this is genuinely
unlimited from the time perspective.
*/

while(
performance.now()<
polishDeadline
){

passes++;

const jobs=[];

/*
Each worker gets a contiguous range of i values.

The i range covers:

0 … M-4
*/

for(
let w=0;
w<workerCount;
w++
){

const iStart=
Math.floor(
totalI*w/workerCount
);

const iEnd=
Math.floor(
totalI*(w+1)/workerCount
);

if(
iStart>=iEnd
)
continue;

/*
route.slice() creates an independent ArrayBuffer,
which can safely be transferred to the child worker.
*/

const routeCopy=
route.slice().buffer;

jobs.push(
scanWorker(
pool[w],
routeCopy,
iStart,
iEnd
)
);

}

const results=
await Promise.all(jobs);

/*
Select the best move found by ANY worker.
*/

let bestGain=0;
let bestI=-1;
let bestJ=-1;

for(
const d of results
){

if(
d.gain>
bestGain+
1e-12
||
(
Math.abs(
d.gain-bestGain
)<=1e-12&&
d.gain>1e-12&&
(
bestI<0||
d.i<bestI||
(
d.i===bestI&&
d.j<bestJ
)
)
)
){

bestGain=d.gain;
bestI=d.i;
bestJ=d.j;

}

}

/*
No improving move exists anywhere in the entire
2-opt neighborhood.

The route is therefore 2-opt locally optimal.
*/

if(
bestI<0||
bestJ<0||
bestGain<=1e-12
){

break;

}

/*
Apply the best 2-opt reversal.
*/

let left=
bestI+1;

let right=
bestJ;

while(
left<right
){

const tmp=
route[left];

route[left]=
route[right];

route[right]=
tmp;

left++;
right–;

}

movesMade++;

post(
‘2-opt pass ‘+
passes+
‘ — move ‘+
movesMade+
‘ — improvement ‘+
bestGain.toFixed(1)+
‘ m — ‘+
workerCount+
‘ workers’,
false
);

}

return{
moves:movesMade,
passes,
timedOut:
performance.now()>=polishDeadline,
workers:workerCount
};

}
finally{

terminatePool();

}

}

/*

Randomized double-bridge style kick.

The fixed root and duplicate-start remain at the boundaries.
*/

function kick(route){

const cuts=[];

while(
cuts.length<3
){

const x=
2+
Math.floor(
rng()*(M-4)
);

if(
!cuts.includes(x)
){

cuts.push(x);

}

}

cuts.sort(
(a,b)=>a-b
);

const[
a,
b,
c
]=cuts;

const head=
Array.from(
route.slice(0,a)
);

const s1=
Array.from(
route.slice(a,b)
);

const s2=
Array.from(
route.slice(b,c)
);

const tail=
Array.from(
route.slice(c)
);

const out=[
…head,
…s2,
…s1,
…tail
];

out[0]=root;
out[M-1]=dup;

return Int32Array.from(out);

}

/*
Parallel Exhaustive 2-opt child worker.

Each child worker receives:
– the coordinate arrays once during initialization
– a copy of the current route for each scan
– an i-range to examine

It returns the best 2-opt move found in its assigned range.
*/

function twoOptChildMain(){

‘use strict’;

let lat;
let lon;
let latRad;
let lonRad;
let cosLat;
let M=0;

const R=6371008.8;

function prepareCoordinates(){

latRad=
new Float64Array(M);

lonRad=
new Float64Array(M);

cosLat=
new Float64Array(M);

for(
let i=0;
i<M;
i++
){

const p=
lat[i]*
Math.PI/180;

const q=
lon[i]*
Math.PI/180;

latRad[i]=p;
lonRad[i]=q;
cosLat[i]=Math.cos(p);

}

}

function hav(a,b){

const p=latRad[a];
const q=latRad[b];

const dLat=
latRad[b]-p;

const dLon=
lonRad[b]-lonRad[a];

const h=
Math.sin(dLat/2)**2+
cosLat[a]*
cosLat[b]*
Math.sin(dLon/2)**2;

return 2*
R*
Math.atan2(
Math.sqrt(h),
Math.sqrt(
Math.max(
0,
1-h
)
)
);

}

function scan(
route,
iStart,
iEnd
){

let bestGain=1e-12;
let bestI=-1;
let bestJ=-1;

const limitI=
Math.min(
iEnd,
M-3
);

for(
let i=iStart;
i<limitI;
i++
){

const a=route[i];
const b=route[i+1];

const oldAB=
hav(a,b);

for(
let j=i+2;
j<=M-2;
j++
){

const c=route[j];
const d=route[j+1];

const oldCost=
oldAB+
hav(c,d);

const newCost=
hav(a,c)+
hav(b,d);

const gain=
oldCost-newCost;

/*
Deterministic tie-breaking:
prefer the smaller i, then smaller j.
*/

if(
gain>bestGain+
1e-12
||
(
Math.abs(
gain-bestGain
)<=1e-12&&
gain>1e-12&&
(
bestI<0||
i<bestI||
(
i===bestI&&
j<bestJ
)
)
)
){

bestGain=gain;
bestI=i;
bestJ=j;

}

}

}

return{
gain:
bestGain>1e-12
?bestGain
:0,

i:bestI,
j:bestJ

};

}

self.onmessage=async e=>{

try{

const d=e.data;

if(d.type===’init’){

lat=
new Float64Array(d.lat);

lon=
new Float64Array(d.lon);

M=d.M;

prepareCoordinates();

self.postMessage({
type:’ready’
});

return;

}

if(d.type===’scan’){

const route=
new Int32Array(d.route);

const result=
scan(
route,
d.iStart,
d.iEnd
);

self.postMessage({
type:’scanResult’,
gain:result.gain,
i:result.i,
j:result.j
});

}

}
catch(err){

self.postMessage({
type:’error’,
message:
err&&err.message
?err.message
:String(err)
});

}

};

}

self.onmessage=async e=>{

try{

lat=
new Float64Array(
e.data.lat
);

lon=
new Float64Array(
e.data.lon
);

N=
lat.length;

root=N;
dup=N+1;

M=N+2;

/*
Extend coordinates with the real start and the duplicate start.
*/

const extLat=
new Float64Array(M);

const extLon=
new Float64Array(M);

extLat.set(lat);
extLon.set(lon);

extLat[root]=
e.data.start[0];

extLon[root]=
e.data.start[1];

extLat[dup]=
e.data.start[0];

extLon[dup]=
e.data.start[1];

lat=extLat;
lon=extLon;

rngState=
(
Math.floor(
performance.now()
)^N
)>>>0;

/*
One delivery: no optimization search is necessary.
*/

if(
N===1
){

const route=
Int32Array.from([
root,
0,
dup
]);

const d=
hav(
root,
0
);

self.postMessage(
{
type:’done’,
lat:lat.buffer,
lon:lon.buffer,
order:new Int32Array([0]).buffer,
count:1,
initial:d,
final:d,
improvement:0,
ms:0,
runs:0,
moves:0,
maxDepth:0
},
[
lat.buffer,
lon.buffer
]
);

return;

}

const began=
performance.now();

/*
Exact α-nearness candidate budget.

The candidate set is now selected from globally computed
α-values, rather than from a geographically pre-filtered
RAW_K pool.
*/

/*
Hybrid candidate strategy:

– ALPHA_K = exact α-nearness candidates
– GEO_K = geographically nearby candidates

At 10,000 nodes we retain the existing 46 α candidates
and add up to 20 geographic-neighbor candidates.

Smaller datasets use slightly fewer α candidates so
the total candidate count remains manageable.
*/

const ALPHA_K =
N <= 199
? 128
: N >= 7000
? 46
: 64;

const GEO_K =
N <= 199
? 32
: 20;

cands =

Array.from(
{length:M},
()=>[]
);

/*
Build geographic candidates first.
gridCandidates() returns [node,distance] pairs.
*/

const geoCands =
gridCandidates(
GEO_K
);

/*
Now build exact α-nearness candidates and merge
them with the geographic candidates.
*/

buildOneTree(
ALPHA_K,
geoCands,
GEO_K
);

post(

‘Building initial tour…’,
true
);

/*
The browser budget is now much larger than the original
few-hundred-millisecond-per-trial design.

10,000 nodes:
5 runs
180 seconds total

3,000-6,999:
6 runs
150 seconds

Smaller:
8 runs
90 seconds
*/

const runs =
N <= 199
? 14
: N >= 7000
? 5
: N >= 3000
? 6
: 8;

maxDepth =
N <= 199
? 14
: N >= 7000
? 7
: N >= 3000
? 9
: 11;

const totalBudget =
N <= 199
? 360000
: N >= 7000
? 600000
: N >= 3000
? 450000
: 300000;

deadline=
began+
totalBudget;

let best=
initialTour(0);

let bestLen=
cycleLength(best);

const initialLen=
bestLen;

let totalMoves=0;

/*
Multiple independent randomized runs.
*/

for(
let runNo=0;
runNo<runs&&
performance.now()<deadline;
runNo++
){

let current=
runNo===0
?best.slice()
:kick(best);

let currentLen=
cycleLength(current);

const runEnd=
Math.min(
deadline,
began+
Math.floor(
totalBudget/runs
)*(runNo+1)
);

post(
‘LKH-style run ‘+
(runNo+1)+
‘ / ‘+
runs+
‘\nCurrent best: ‘+
(bestLen/1000).toFixed(2)+
‘ km’,
true
);

let pass=0;

/*
Repeated variable-depth passes within each run.
*/

while(
performance.now()<runEnd
){

const r=
improveByLK(
current,
Math.min(
runEnd,
performance.now()+
Math.max(
2500,
Math.floor(
totalBudget/runs/5
)
)
),
maxDepth
);

currentLen=
r.length;

if(
!r.changed
)
break;

pass++;

if(
currentLen<
bestLen-1e-6
){

best=
current.slice();

bestLen=
currentLen;

post(
‘Improved best: ‘+
(bestLen/1000).toFixed(2)+
‘ km — run ‘+
(runNo+1)+
‘ pass ‘+
pass,
true
);

}

}

totalMoves=
moves;

post(
‘Run ‘+
(runNo+1)+
‘ complete\nBest distance: ‘+
(bestLen/1000).toFixed(2)+
‘ km’,
true
);

}

/*
Final backtracking polish.
*/

if(
performance.now()<deadline
){

post(
‘Final backtracking polish…’,
true
);

let end=
Math.min(
deadline,
performance.now()+
Math.min(
30000,
totalBudget/5
)
);

let changed=true;

while(
changed&&
performance.now()<end
){

const r=
improveByLK(
best,
end,
maxDepth
);

bestLen=
r.length;

changed=
r.changed;

if(changed)
best=
best.slice();

}

}

/*
Exhaustive 2-opt polishing.

NO TIME LIMIT:
2-opt continues until it reaches a 2-opt local optimum.

The Web Worker can still be cancelled using the Cancel
Optimization button, so the main page remains usable.
*/

let twoOptMoves=0;

post(
‘Exhaustive 2-opt polishing — running until no improving 2-opt move remains…’,
true
);

const twoOpt=
await exhaustiveTwoOptParallel(
best,
Infinity
);

twoOptMoves=
twoOpt.moves;

bestLen=
cycleLength(best);

post(
‘2-opt complete — ‘+
twoOptMoves+
‘ improving moves. ‘+
‘Final distance: ‘+
(bestLen/1000).toFixed(2)+
‘ km’,
true
);

/*

Return only the original delivery node IDs.
*/

const order=

new Int32Array(N);

for(
let i=1;
i<M-1;
i++
){

order[i-1]=
best[i];

}

const ms=
performance.now()-
began;

self.postMessage(
{
type:’done’,

lat:e.data.lat,

lon:e.data.lon,

order:order.buffer,

count:N,

initial:initialLen,

final:bestLen,

improvement:
initialLen
?100*
(initialLen-bestLen)/
initialLen
:0,

ms,

runs,

moves:totalMoves,

twoOptMoves,

maxDepth

},

[
e.data.lat,
e.data.lon,
order.buffer
]
);

}

catch(err){

self.postMessage(
{
type:’error’,
message:
‘Optimization failed: ‘+
(
err&&err.message
?err.message
:String(err)
)
}
);

}

};

}

})();
</script>
</div>