Routing Engine

Distance-based routing optimization for warehouse operations using 3D zone coordinates.

Overview

The Routing Engine provides intelligent pathfinding and distance calculation for warehouse zones. It uses 3D coordinates (X, Y, Z) to calculate Euclidean distances and find optimal paths through zones.

Features

• 3D Coordinate System: X, Y, Z coordinates for zones
• Euclidean Distance Calculation: Accurate 3D distance computation
• Pre-Computed Distances: Cached pairwise zone distances
• Optimal Path Finding: Nearest-neighbor algorithm for route optimization
• Routing Weight: Cost-based pathfinding with zone weights
• Integration: Used by Pick & Pack, Auto Assignment, Slotting AI

Architecture

graph TB
    A[Zones with Coordinates] --> B[Distance Calculation]
    B --> C[Pre-Computed Cache]
    C --> D[Path Finding]
    D --> E[Optimal Route]
    
    F[Pick & Pack] --> D
    G[Auto Assignment] --> B
    H[Slotting AI] --> B
    
    style B fill:#3b82f6
    style D fill:#10b981
    style E fill:#f59e0b

Database Schema

zones Table Extensions

Column	Type	Constraints	Description
x	integer	NULL	X coordinate in warehouse space
y	integer	NULL	Y coordinate in warehouse space
z	integer	DEFAULT 0	Z coordinate (floor level)
routing_weight	integer	DEFAULT 1	Routing cost multiplier (higher = more expensive)

Indexes:

• idx_zones_coordinates on (x, y, z) WHERE x IS NOT NULL AND y IS NOT NULL

zone_distances Table

Column	Type	Constraints	Description
id	uuid	PRIMARY KEY	Unique distance record
from_zone	uuid	NOT NULL, FK → zones	Source zone
to_zone	uuid	NOT NULL, FK → zones	Destination zone
distance	numeric	NOT NULL, >= 0	Computed distance
computed_at	timestamptz	NOT NULL, DEFAULT now()	Computation timestamp

Constraints:

• UNIQUE (from_zone, to_zone)
• CHECK from_zone <> to_zone (no self-loops)

Indexes:

• idx_zone_distances_from_zone on from_zone
• idx_zone_distances_to_zone on to_zone
• idx_zone_distances_distance on distance

API Functions

Compute Distance

import { computeDistance } from '@/lib/routingEngine';

// Direct calculation
const distance = computeDistance(
  { id: 'zone-1', x: 0, y: 0, z: 0 },
  { id: 'zone-2', x: 10, y: 10, z: 0 }
);
// Returns: 14.14 (Euclidean distance)

Formula:

distance = √((x₂ - x₁)² + (y₂ - y₁)² + (z₂ - z₁)²)

Compute and Store Distance

import { computeAndStoreDistance } from '@/lib/routingEngine';

const { data, error } = await computeAndStoreDistance(
  'from-zone-uuid',
  'to-zone-uuid'
);
// Computes distance and stores in zone_distances table

Returns: { data: ZoneDistance | null, error: any }

Compute All Distances

import { computeAllDistances } from '@/lib/routingEngine';

const { data, error } = await computeAllDistances();
// Computes all pairwise distances for all zones with coordinates
// Returns: number of distance records created

Use Case: Run as background job to pre-compute all distances.

Script:

npm run compute:distances

Find Optimal Path

import { findOptimalPath } from '@/lib/routingEngine';

const { data, error } = await findOptimalPath([
  'zone-1-uuid',
  'zone-2-uuid',
  'zone-3-uuid',
  'zone-4-uuid',
]);

Returns:

{
  zones: string[], // Optimal zone order
  totalDistance: number, // Total path distance
  segments: Array<{
    from_zone_id: string,
    to_zone_id: string,
    distance: number
  }>
}

Algorithm: Nearest-neighbor heuristic with distance optimization.

Score Zone for Shipment

import { scoreZoneForShipment } from '@/lib/routingEngine';

const { score, reasons } = await scoreZoneForShipment(
  {
    from_zone_id: 'source-zone-uuid',
    to_zone_id: 'target-zone-uuid',
  },
  {
    id: 'candidate-zone-uuid',
    x: 50,
    y: 50,
    z: 0,
    routing_weight: 1,
  }
);

Returns: { score: number, reasons: string[] }

Scoring Factors:

• Distance from source zone (closer = higher score)
• Routing weight (lower = higher score)
• Zone capacity (if available)

Distance Calculation

Euclidean Distance (3D)

function euclideanDistance(zoneA: ZoneCoordinates, zoneB: ZoneCoordinates): number {
  const dx = zoneB.x - zoneA.x;
  const dy = zoneB.y - zoneA.y;
  const dz = (zoneB.z ?? 0) - (zoneA.z ?? 0);
  
  return Math.sqrt(dx * dx + dy * dy + dz * dz);
}

Weighted Distance

function weightedDistance(
  zoneA: ZoneCoordinates,
  zoneB: ZoneCoordinates
): number {
  const baseDistance = euclideanDistance(zoneA, zoneB);
  const avgWeight = ((zoneA.routing_weight ?? 1) + (zoneB.routing_weight ?? 1)) / 2;
  
  return baseDistance * avgWeight;
}

Path Finding Algorithm

Nearest-Neighbor Heuristic

graph LR
    A[Start Zone] --> B[Find Nearest Unvisited]
    B --> C[Visit Zone]
    C --> D{More Zones?}
    D -->|Yes| B
    D -->|No| E[Complete Path]
    
    style A fill:#3b82f6
    style E fill:#10b981

Algorithm Steps:

1. Start with first zone in sequence
2. Find nearest unvisited zone
3. Add to path
4. Repeat until all zones visited
5. Return optimal path

Integration

Pick & Pack Integration

// Pick & Pack uses routing for optimal item sequence
const zoneIds = items.map(item => item.zone_id);
const { data: optimalPath } = await findOptimalPath(zoneIds);
// Use optimalPath.zones for item ordering

Auto Assignment Integration

// Auto Assignment uses distance for driver scoring
const distance = await computeAndStoreDistance(
  driver.current_zone,
  shipment.from_zone_id
);
// Use distance in scoring algorithm

Slotting AI Integration

// Slotting AI uses distance for movement cost
const distance = computeDistance(fromZone, toZone);
const movementCost = distance * routingWeight;
// Use in optimization calculations

Best Practices

1. Set Zone Coordinates

Always set coordinates when creating zones:

await supabase.from('zones').insert({
  code: 'A1',
  name: 'Zone A1',
  x: 0,
  y: 0,
  z: 0,
  routing_weight: 1,
});

2. Pre-Compute Distances

Run distance computation script regularly:

# After adding/modifying zones
npm run compute:distances

3. Use Routing Weight

Set higher routing weight for difficult zones:

// Narrow aisle = higher weight
await supabase.from('zones').update({
  routing_weight: 2, // More expensive to traverse
}).eq('id', 'narrow-zone-uuid');

4. Validate Coordinates

Ensure all zones have coordinates before routing:

const { data: zones } = await supabase
  .from('zones')
  .select('id, x, y, z')
  .not('x', 'is', null)
  .not('y', 'is', null);

Troubleshooting

Issue: Distances Not Calculated

Symptom: findOptimalPath() returns zero distance.

Solution:

1. Verify zones have coordinates (x, y)
2. Run computeAllDistances() script
3. Check zone_distances table has data

Issue: Suboptimal Routes

Symptom: Routes don't follow shortest path.

Solution:

1. Verify coordinates are accurate
2. Check routing weights are appropriate
3. Consider using more advanced algorithm (A*, Dijkstra)

Issue: Missing Coordinates

Symptom: Some zones don't have coordinates.

Solution:

1. Set coordinates in zone management UI
2. Use floor plan coordinates as fallback
3. System will skip zones without coordinates

Related Documentation

• Pick & Pack Module - Uses routing for pick lists
• Auto Assignment Module - Uses distance for scoring
• Slotting AI Module - Uses distance for optimization
• Warehouse Map Module - Visualizes routes