Kotlin TSP solver + verification harness. DeliveryRoutePlanner computes an optimized multi-stop delivery route (nearest-neighbour TSP heuristic); VerifyDeliveryRoutePlanner asserts correctness of the planner's output.

DeliveryRoutePlanner.kt

import java.util.PriorityQueue

const val DEPOT = 0
const val NO_DUE_TIME = Int.MAX_VALUE

enum class RouteMode { RETURN_TO_DEPOT, OPEN }

data class Stop(
    val id: Int,
    val demand: Int = 1,
    val serviceTime: Int = 0,
    val readyTime: Int = 0,
    val dueTime: Int = NO_DUE_TIME,
)

sealed interface RouteStep
data class Visit(val stopId: Int, val arrivalTime: Int) : RouteStep
data object Reload : RouteStep
data object ReturnToDepot : RouteStep

data class Route(val steps: List<RouteStep>, val completionTime: Int)

class DeliveryRoutePlanner(
    private val travelTime: Array<IntArray>,
    private val stops: List<Stop>,
    private val vehicleCapacity: Int,
    private val startTime: Int = 0,
    private val mode: RouteMode = RouteMode.RETURN_TO_DEPOT,
    private val allowReload: Boolean = true,
) {
    private val n = stops.size
    private val full = (1 shl n) - 1

    init {
        val nodeCount = n + 1
        require(n in 1..12) { "supports 1..12 stops, got $n" }
        require(travelTime.size == nodeCount && travelTime.all { it.size == nodeCount }) {
            "travelTime must be ${nodeCount}x$nodeCount (depot + $n stops)"
        }
        require(stops.all { it.demand in 1..vehicleCapacity }) {
            "every stop demand must be in 1..$vehicleCapacity"
        }
    }

    private data class State(val mask: Int, val node: Int, val cap: Int)

    private class Solution(
        val goal: State,
        val completionTime: Int,
        val arrival: Map<State, Int>,
        val prev: Map<State, State>,
    )

    fun solve(): Route? {
        val solution = search() ?: return null
        return Route(reconstruct(solution), solution.completionTime)
    }

    private fun search(): Solution? {
        val start = State(0, DEPOT, vehicleCapacity)
        val arrival = hashMapOf(start to startTime)
        val prev = HashMap<State, State>()
        val frontier = PriorityQueue<Pair<Int, State>>(compareBy { it.first })
        frontier.add(startTime to start)

        var bestGoal: State? = null
        var bestCost = Int.MAX_VALUE

        while (frontier.isNotEmpty()) {
            val (time, state) = frontier.poll()
            if (time > arrival.getValue(state)) continue
            if (state.mask == full) {
                val cost = time + returnCost(state.node)
                if (cost < bestCost) {
                    bestCost = cost
                    bestGoal = state
                }
                continue
            }
            expand(state, time, arrival, prev, frontier)
        }
        return bestGoal?.let { Solution(it, bestCost, arrival, prev) }
    }

    private fun expand(
        state: State,
        time: Int,
        arrival: HashMap<State, Int>,
        prev: HashMap<State, State>,
        frontier: PriorityQueue<Pair<Int, State>>,
    ) {
        for (j in 0 until n) {
            if (state.mask and (1 shl j) != 0) continue
            val stop = stops[j]
            if (stop.demand > state.cap) continue
            val arriveAt = time + travelTime[state.node][j + 1]
            val serviceStart = maxOf(arriveAt, stop.readyTime)
            if (serviceStart > stop.dueTime) continue
            val next = State(state.mask or (1 shl j), j + 1, state.cap - stop.demand)
            relax(next, serviceStart + stop.serviceTime, state, arrival, prev, frontier)
        }
        if (allowReload && state.cap < vehicleCapacity && state.node != DEPOT) {
            val next = State(state.mask, DEPOT, vehicleCapacity)
            relax(next, time + travelTime[state.node][DEPOT], state, arrival, prev, frontier)
        }
    }

    private fun relax(
        next: State,
        candidateTime: Int,
        from: State,
        arrival: HashMap<State, Int>,
        prev: HashMap<State, State>,
        frontier: PriorityQueue<Pair<Int, State>>,
    ) {
        if (candidateTime >= arrival.getOrDefault(next, Int.MAX_VALUE)) return
        arrival[next] = candidateTime
        prev[next] = from
        frontier.add(candidateTime to next)
    }

    private fun returnCost(node: Int) =
        if (mode == RouteMode.RETURN_TO_DEPOT) travelTime[node][DEPOT] else 0

    private fun reconstruct(solution: Solution): List<RouteStep> {
        val chain = ArrayDeque<State>()
        var cursor: State? = solution.goal
        while (cursor != null) {
            chain.addFirst(cursor)
            cursor = solution.prev[cursor]
        }
        val steps = buildList {
            for (i in 1 until chain.size) add(stepBetween(chain[i - 1], chain[i], solution.arrival))
        }
        return if (mode == RouteMode.RETURN_TO_DEPOT) steps + ReturnToDepot else steps
    }

    private fun stepBetween(from: State, to: State, arrival: Map<State, Int>): RouteStep {
        if (to.mask == from.mask) return Reload
        val deliveredBit = to.mask and from.mask.inv()
        val stopIndex = Integer.numberOfTrailingZeros(deliveredBit)
        val stop = stops[stopIndex]
        val reachedAt = arrival.getValue(from) + travelTime[from.node][to.node]
        return Visit(stop.id, maxOf(reachedAt, stop.readyTime))
    }
}

VerifyDeliveryRoutePlanner.kt

import java.util.Random

private var failures = 0

private fun check(name: String, ok: Boolean, detail: String = "") {
    if (!ok) failures++
    println("[${if (ok) "PASS" else "FAIL"}] $name${if (detail.isEmpty()) "" else " — $detail"}")
}

private fun permutations(items: List<Int>): Sequence<List<Int>> = sequence {
    if (items.size <= 1) {
        yield(items)
        return@sequence
    }
    for (i in items.indices) {
        val rest = items.toMutableList().apply { removeAt(i) }
        for (tail in permutations(rest)) yield(listOf(items[i]) + tail)
    }
}

private fun symmetricMatrix(coords: List<Pair<Int, Int>>) = Array(coords.size) { i ->
    IntArray(coords.size) { j ->
        val dx = coords[i].first - coords[j].first
        val dy = coords[i].second - coords[j].second
        Math.round(Math.sqrt((dx * dx + dy * dy).toDouble())).toInt()
    }
}

private fun bruteForceFull(
    travel: Array<IntArray>,
    stops: List<Stop>,
    capacity: Int,
    startTime: Int,
    mode: RouteMode,
    allowReload: Boolean,
): Int? {
    val n = stops.size
    var best: Int? = null
    val reloadMasks = if (allowReload) 0 until (1 shl n) else 0..0
    for (order in permutations((0 until n).toList())) {
        for (reloadMask in reloadMasks) {
            val cost = simulateOrder(order, reloadMask, travel, stops, capacity, startTime, mode)
            if (cost != null && (best == null || cost < best)) best = cost
        }
    }
    return best
}

private fun simulateOrder(
    order: List<Int>,
    reloadMask: Int,
    travel: Array<IntArray>,
    stops: List<Stop>,
    capacity: Int,
    startTime: Int,
    mode: RouteMode,
): Int? {
    var time = startTime
    var at = DEPOT
    var cap = capacity
    for ((position, stopIndex) in order.withIndex()) {
        if (reloadMask shr position and 1 == 1) {
            time += travel[at][DEPOT]
            at = DEPOT
            cap = capacity
        }
        val stop = stops[stopIndex]
        if (stop.demand > cap) return null
        val serviceStart = maxOf(time + travel[at][stopIndex + 1], stop.readyTime)
        if (serviceStart > stop.dueTime) return null
        time = serviceStart + stop.serviceTime
        at = stopIndex + 1
        cap -= stop.demand
    }
    return time + if (mode == RouteMode.RETURN_TO_DEPOT) travel[at][DEPOT] else 0
}

private fun validateRoute(
    route: Route,
    travel: Array<IntArray>,
    stops: List<Stop>,
    capacity: Int,
    startTime: Int,
    mode: RouteMode,
): String? {
    val nodeOf = stops.withIndex().associate { (i, s) -> s.id to i + 1 }
    var time = startTime
    var at = DEPOT
    var cap = capacity
    val delivered = mutableListOf<Int>()
    for (step in route.steps) when (step) {
        Reload -> {
            time += travel[at][DEPOT]; at = DEPOT; cap = capacity
        }
        ReturnToDepot -> {
            time += travel[at][DEPOT]; at = DEPOT
        }
        is Visit -> {
            val stop = stops.first { it.id == step.stopId }
            val node = nodeOf.getValue(stop.id)
            val serviceStart = maxOf(time + travel[at][node], stop.readyTime)
            if (serviceStart > stop.dueTime) return "late at ${stop.id}"
            if (stop.demand > cap) return "over capacity at ${stop.id}"
            if (step.arrivalTime != serviceStart) return "arrival mismatch ${stop.id}: ${step.arrivalTime} vs $serviceStart"
            time = serviceStart + stop.serviceTime; at = node; cap -= stop.demand; delivered += stop.id
        }
    }
    if (mode == RouteMode.RETURN_TO_DEPOT && route.steps.lastOrNull() != ReturnToDepot) return "missing depot return"
    if (mode == RouteMode.OPEN && route.steps.any { it == ReturnToDepot }) return "unexpected depot return"
    if (delivered.size != stops.size || delivered.toSet() != stops.map { it.id }.toSet()) return "delivery set wrong: $delivered"
    if (time != route.completionTime) return "completion mismatch $time vs ${route.completionTime}"
    return null
}

private fun testSingleStop() {
    val travel = arrayOf(intArrayOf(0, 7), intArrayOf(7, 0))
    val stops = listOf(Stop(id = 1))
    val closed = DeliveryRoutePlanner(travel, stops, 1, mode = RouteMode.RETURN_TO_DEPOT).solve()
    val open = DeliveryRoutePlanner(travel, stops, 1, mode = RouteMode.OPEN).solve()
    check("single stop closed = 14", closed?.completionTime == 14, "${closed?.completionTime}")
    check("single stop open = 7", open?.completionTime == 7, "${open?.completionTime}")
}

private fun testWaitForReadyTime() {
    val travel = arrayOf(intArrayOf(0, 3), intArrayOf(3, 0))
    val stops = listOf(Stop(id = 1, readyTime = 20, serviceTime = 2))
    val route = DeliveryRoutePlanner(travel, stops, 1, mode = RouteMode.OPEN).solve()
    val visit = route?.steps?.filterIsInstance<Visit>()?.first()
    check("waits until readyTime: arrival = 20", visit?.arrivalTime == 20, "${visit?.arrivalTime}")
    check("completion = ready + service = 22", route?.completionTime == 22, "${route?.completionTime}")
}

private fun testDueTimeBoundary() {
    val travel = arrayOf(intArrayOf(0, 10), intArrayOf(10, 0))
    val exact = DeliveryRoutePlanner(travel, listOf(Stop(id = 1, dueTime = 10)), 1, mode = RouteMode.OPEN).solve()
    val justLate = DeliveryRoutePlanner(travel, listOf(Stop(id = 1, dueTime = 9)), 1, mode = RouteMode.OPEN).solve()
    check("arrival exactly at dueTime is feasible", exact != null)
    check("arrival one past dueTime is infeasible", justLate == null)
}

private fun testReloadDisabledInfeasible() {
    val travel = arrayOf(
        intArrayOf(0, 4, 6),
        intArrayOf(4, 0, 3),
        intArrayOf(6, 3, 0),
    )
    val stops = listOf(Stop(id = 1, demand = 2), Stop(id = 2, demand = 2))
    val noReload = DeliveryRoutePlanner(travel, stops, vehicleCapacity = 3, allowReload = false).solve()
    val withReload = DeliveryRoutePlanner(travel, stops, vehicleCapacity = 3, allowReload = true).solve()
    check("capacity 3 demand 4 no-reload is infeasible", noReload == null)
    check("capacity 3 demand 4 with reload is feasible", withReload != null)
}

private fun testCapacityEqualsDemandNoReload() {
    val travel = arrayOf(
        intArrayOf(0, 4, 6, 8),
        intArrayOf(4, 0, 3, 7),
        intArrayOf(6, 3, 0, 4),
        intArrayOf(8, 7, 4, 0),
    )
    val stops = listOf(Stop(id = 1, demand = 1), Stop(id = 2, demand = 1), Stop(id = 3, demand = 1))
    val route = DeliveryRoutePlanner(travel, stops, vehicleCapacity = 3, allowReload = true).solve()
    val reloads = route?.steps?.count { it == Reload } ?: -1
    check("capacity == total demand needs zero reloads", reloads == 0, "reloads=$reloads")
}

private fun testValidationRejectsBadInput() {
    val ok3 = arrayOf(intArrayOf(0, 1, 1), intArrayOf(1, 0, 1), intArrayOf(1, 1, 0))
    check("empty stop list rejected", runCatching {
        DeliveryRoutePlanner(arrayOf(intArrayOf(0)), emptyList(), 1)
    }.isFailure)
    check("13 stops rejected", runCatching {
        DeliveryRoutePlanner(Array(14) { IntArray(14) }, (1..13).map { Stop(it) }, 13)
    }.isFailure)
    check("wrong matrix size rejected", runCatching {
        DeliveryRoutePlanner(ok3, (1..3).map { Stop(it) }, 3)
    }.isFailure)
    check("demand over capacity rejected", runCatching {
        DeliveryRoutePlanner(ok3, listOf(Stop(1, demand = 5), Stop(2)), vehicleCapacity = 3)
    }.isFailure)
    check("zero demand rejected", runCatching {
        DeliveryRoutePlanner(ok3, listOf(Stop(1, demand = 0), Stop(2)), vehicleCapacity = 3)
    }.isFailure)
}

private fun testAsymmetricMatrix() {
    val travel = arrayOf(
        intArrayOf(0, 2, 9),
        intArrayOf(8, 0, 1),
        intArrayOf(3, 7, 0),
    )
    val stops = listOf(Stop(id = 1), Stop(id = 2))
    val mode = RouteMode.RETURN_TO_DEPOT
    val route = DeliveryRoutePlanner(travel, stops, 2, mode = mode).solve()
    val brute = bruteForceFull(travel, stops, 2, 0, mode, allowReload = false)
    check("asymmetric matrix matches brute force", route?.completionTime == brute, "planner=${route?.completionTime} brute=$brute")
}

private fun randomInstance(rng: Random): Triple<Array<IntArray>, List<Stop>, IntArray> {
    val n = 1 + rng.nextInt(6)
    val capacity = 1 + rng.nextInt(6)
    val size = n + 1
    val travel = Array(size) { i -> IntArray(size) { j -> if (i == j) 0 else 1 + rng.nextInt(20) } }
    val windowed = rng.nextInt(3) != 0
    val stops = (1..n).map { id ->
        val ready = if (rng.nextInt(4) == 0) rng.nextInt(15) else 0
        val due = if (windowed && rng.nextBoolean()) ready + 12 + rng.nextInt(40) else NO_DUE_TIME
        Stop(id, demand = 1 + rng.nextInt(capacity), serviceTime = rng.nextInt(4), readyTime = ready, dueTime = due)
    }
    val config = intArrayOf(capacity, rng.nextInt(5), if (rng.nextBoolean()) 1 else 0, if (rng.nextBoolean()) 1 else 0)
    return Triple(travel, stops, config)
}

private fun fuzzAgainstBruteForce() {
    val rng = Random(987654321L)
    var mismatches = 0
    var invalidRoutes = 0
    var feasible = 0
    val total = 1500
    repeat(total) {
        val (travel, stops, config) = randomInstance(rng)
        val capacity = config[0]
        val startTime = config[1]
        val mode = if (config[2] == 1) RouteMode.RETURN_TO_DEPOT else RouteMode.OPEN
        val allowReload = config[3] == 1
        val route = DeliveryRoutePlanner(travel, stops, capacity, startTime, mode, allowReload).solve()
        val brute = bruteForceFull(travel, stops, capacity, startTime, mode, allowReload)
        if (route?.completionTime != brute) {
            if (mismatches < 3) println("  mismatch: planner=${route?.completionTime} brute=$brute stops=$stops cap=$capacity mode=$mode reload=$allowReload start=$startTime")
            mismatches++
        }
        if (route != null) {
            feasible++
            validateRoute(route, travel, stops, capacity, startTime, mode)?.let {
                if (invalidRoutes < 3) println("  invalid route: $it")
                invalidRoutes++
            }
        }
    }
    check("$total random instances: planner optimum == brute force", mismatches == 0, "$mismatches mismatches")
    check("every feasible route self-validates", invalidRoutes == 0, "$invalidRoutes invalid of $feasible feasible")
}

private fun stressTwelveStops() {
    val rng = Random(42L)
    val coords = (0..12).map { rng.nextInt(100) to rng.nextInt(100) }
    val travel = symmetricMatrix(coords)
    val stops = (1..12).map { Stop(id = it, demand = 1 + rng.nextInt(3), serviceTime = 1) }
    val started = System.nanoTime()
    val route = DeliveryRoutePlanner(travel, stops, vehicleCapacity = 5, allowReload = true).solve()
    val ms = (System.nanoTime() - started) / 1_000_000
    val err = route?.let { validateRoute(it, travel, stops, 5, 0, RouteMode.RETURN_TO_DEPOT) }
    check("12 stops + reloads solves and self-validates", route != null && err == null, "err=$err time=${ms}ms")
}

fun main() {
    testSingleStop()
    testWaitForReadyTime()
    testDueTimeBoundary()
    testReloadDisabledInfeasible()
    testCapacityEqualsDemandNoReload()
    testValidationRejectsBadInput()
    testAsymmetricMatrix()
    fuzzAgainstBruteForce()
    stressTwelveStops()
    println("\n${if (failures == 0) "ALL TESTS PASSED" else "$failures TEST(S) FAILED"}")
    if (failures > 0) kotlin.system.exitProcess(1)
}