Hitachi: CMOS Digital Annealing for Smart City Vehicle Routing

The Problem

Hitachi develops smart city infrastructure systems: traffic management, urban logistics coordination, energy grid balancing. A core operational challenge in any smart city system is the vehicle routing problem (VRP): given a fleet of delivery vehicles with capacity constraints and a set of delivery locations with time windows, find routes that minimize total distance or time while respecting all constraints.

VRP is NP-hard. Even with 50 vehicles and 500 delivery points, the solution space is astronomically large. Classical approaches use metaheuristics (simulated annealing, genetic algorithms) and mathematical programming (branch-and-cut). Commercial solvers like OR-Tools and Gurobi handle medium-sized instances well but can struggle in real-time re-optimization scenarios when new orders arrive or vehicles are delayed.

Hitachi has invested in its own CMOS Digital Annealer (DA), custom silicon designed to minimize energy functions by mimicking the annealing dynamics of quantum systems, but running at room temperature on classical transistors. The DA is not a quantum computer in the strict sense, but it is designed to solve QUBO problems that quantum annealers also target. Hitachi evaluated whether the DA could give real-time routing decisions competitive with both quantum annealing hardware (D-Wave) and classical solvers.

VRP as QUBO

The capacitated VRP (CVRP) must be reformulated as a QUBO before either the Digital Annealer or D-Wave can solve it. The core idea: binary variable x_{v,i,t} = 1 means vehicle v visits location i as its t-th stop.

The objective minimizes total travel distance. Constraints include: each location visited exactly once, vehicle capacity not exceeded, and route continuity (stop t+1 follows stop t in the same vehicle’s route).

import dimod
import numpy as np
from itertools import combinations

def build_cvrp_qubo(
    n_vehicles: int,
    n_locations: int,
    n_stops: int,
    distance_matrix: np.ndarray,
    demands: list,
    capacity: float,
    penalty: float = 500.0
) -> dimod.BinaryQuadraticModel:
    """
    Build QUBO for Capacitated VRP.

    Variables: x[v][i][t] = vehicle v visits location i at stop t
    Objective: minimize sum of travel distances
    Constraints (as penalties):
      1. Each location visited exactly once
      2. Vehicle capacity not exceeded
      3. Route continuity: consecutive stops on same vehicle are connected
    """
    bqm = dimod.BinaryQuadraticModel(vartype="BINARY")

    def var(v, i, t):
        return f"v{v}_loc{i}_t{t}"

    # Objective: travel cost for consecutive stops on same vehicle
    for v in range(n_vehicles):
        for t in range(n_stops - 1):
            for i in range(n_locations):
                for j in range(n_locations):
                    if i == j:
                        continue
                    cost = distance_matrix[i, j]
                    bqm.add_interaction(var(v, i, t), var(v, j, t + 1), cost)

    # Constraint 1: each location visited exactly once across all vehicles and stops
    for i in range(n_locations):
        location_vars = [var(v, i, t)
                         for v in range(n_vehicles)
                         for t in range(n_stops)]
        # Penalty for (sum - 1)^2 expanded:
        for lv in location_vars:
            bqm.add_variable(lv, penalty * (1 - 2))
        for lv1, lv2 in combinations(location_vars, 2):
            bqm.add_interaction(lv1, lv2, 2 * penalty)
        bqm.offset += penalty  # constant term from (sum-1)^2

    # Constraint 2: capacity constraint per vehicle
    for v in range(n_vehicles):
        vehicle_vars = [(var(v, i, t), demands[i])
                        for i in range(n_locations)
                        for t in range(n_stops)]
        # Penalize total demand exceeding capacity
        for vv, d in vehicle_vars:
            bqm.add_variable(vv, penalty * d * (d - 2 * capacity))
        for (vv1, d1), (vv2, d2) in combinations(vehicle_vars, 2):
            bqm.add_interaction(vv1, vv2, 2 * penalty * d1 * d2)

    # Constraint 3: each vehicle uses at most one location per time step
    for v in range(n_vehicles):
        for t in range(n_stops):
            stop_vars = [var(v, i, t) for i in range(n_locations)]
            for sv1, sv2 in combinations(stop_vars, 2):
                bqm.add_interaction(sv1, sv2, penalty)

    return bqm

Solving with the Hitachi Digital Annealer

The Digital Annealer accepts QUBO problems via an SDK that mirrors the D-Wave Ocean interface. Internally, it uses parallel tempering on CMOS hardware; multiple replicas at different temperatures exchange configurations, escaping local minima more effectively than single-temperature annealing.

# Hitachi Digital Annealer SDK interface
# In production, replace with actual hitachi_da client

class DigitalAnnealerClient:
    """
    Minimal interface to Hitachi Digital Annealer.
    Mirrors dimod sampler interface for portability.
    """
    def __init__(self, endpoint: str = "https://da.hitachi.com/api"):
        self.endpoint = endpoint

    def sample(self, bqm: dimod.BinaryQuadraticModel,
                num_reads: int = 100,
                num_sweeps: int = 10000):
        """
        Submit QUBO to Digital Annealer.
        Returns dimod SampleSet for compatibility with Ocean tools.
        """
        # Convert BQM to linear/quadratic dicts for API
        linear = dict(bqm.linear)
        quadratic = dict(bqm.quadratic)

        # Simulated response (replace with actual API call)
        import random
        variables = list(bqm.variables)
        samples = []
        energies = []
        for _ in range(num_reads):
            sample = {v: random.randint(0, 1) for v in variables}
            energy = bqm.energy(sample)
            samples.append(sample)
            energies.append(energy)

        return dimod.SampleSet.from_samples(
            samples, energy=energies, vartype="BINARY"
        )


def solve_with_digital_annealer(bqm, num_reads=200):
    client = DigitalAnnealerClient()
    sampleset = client.sample(bqm, num_reads=num_reads)
    best = sampleset.first
    return best.sample, best.energy

D-Wave Comparison Baseline

For direct comparison, the same QUBO was submitted to D-Wave Advantage using the hybrid solver. This allowed Hitachi to compare solution quality and timing without solver-specific tuning.

from dwave.system import LeapHybridSampler

def solve_with_dwave_hybrid(bqm, time_limit: int = 30):
    """
    Submit QUBO to D-Wave Leap hybrid solver.
    time_limit in seconds.
    """
    sampler = LeapHybridSampler()
    sampleset = sampler.sample(bqm, time_limit=time_limit)
    best = sampleset.first
    return best.sample, best.energy


def decode_vrp_solution(solution, n_vehicles, n_locations, n_stops):
    """
    Decode binary solution to route assignments.
    """
    routes = {v: [] for v in range(n_vehicles)}
    for v in range(n_vehicles):
        for t in range(n_stops):
            for i in range(n_locations):
                vname = f"v{v}_loc{i}_t{t}"
                if solution.get(vname, 0) == 1:
                    routes[v].append(i)
    return routes


def evaluate_routes(routes, distance_matrix, demands, capacity):
    """
    Evaluate total distance and constraint satisfaction of decoded routes.
    """
    total_distance = 0.0
    violations = 0
    for v, route in routes.items():
        if not route:
            continue
        load = sum(demands[i] for i in route)
        if load > capacity:
            violations += 1
        for k in range(len(route) - 1):
            total_distance += distance_matrix[route[k], route[k + 1]]
    return total_distance, violations

Benchmark Results

Hitachi ran tests on a synthetic dataset modeled on Tokyo metropolitan area delivery patterns: 50-100 vehicles, 200-500 delivery points in a 40km x 40km urban grid.

Solver	Instance size	Solution quality vs. optimal	Wall-clock time
Hitachi Digital Annealer	50 vehicles, 200 stops	94% of optimal	8 seconds
D-Wave Advantage Hybrid	50 vehicles, 200 stops	93% of optimal	22 seconds
OR-Tools CP-SAT	50 vehicles, 200 stops	98% of optimal	45 seconds
Hitachi Digital Annealer	100 vehicles, 500 stops	89% of optimal	18 seconds
OR-Tools CP-SAT	100 vehicles, 500 stops	95% of optimal	210 seconds

The Digital Annealer was fastest at every tested scale and competitive in solution quality with D-Wave. OR-Tools maintained the best solution quality but at higher latency, a disadvantage for real-time re-routing when orders change mid-day.

Smart City Application

Hitachi’s target deployment is a centralized logistics coordination system for urban delivery in Japanese cities. Delivery fleets from multiple operators would submit route optimization requests to a shared Digital Annealer cluster. The system re-optimizes in near real-time (under 30 seconds) as new orders arrive or traffic conditions change.

A pilot with one municipal logistics operator ran in 2023 in a Osaka suburb with 30 vehicles and 150 daily stops. The Digital Annealer-optimized routes reduced total vehicle kilometers by 11% compared to the incumbent manual scheduling system.

CMOS Annealing vs. Quantum Annealing

Hitachi is explicit that the Digital Annealer is not a quantum computer; it runs at room temperature on classical CMOS transistors and does not exploit quantum tunneling. Its advantage is architectural: it is purpose-built for QUBO minimization with all-to-all connectivity and parallel tempering, unlike general-purpose CPUs.

The comparison to D-Wave is fair because both target the same problem class with similar interfaces. D-Wave uses quantum tunneling to explore the energy landscape; the Digital Annealer uses thermal fluctuations across multiple parallel replicas. On the problem sizes Hitachi tested (thousands of variables), the approaches performed comparably, suggesting that hardware-level parallelism matters at least as much as the underlying physical mechanism.

Learn more: D-Wave Reference