water/server/plugin/saiadmin/app/service/routing/RouteOptimizer.php

<?php
declare(strict_types=1);
namespace plugin\saiadmin\app\service\routing;

use plugin\saiadmin\exception\ApiException;

/** 固定出发点、不返回仓库；对最多8站穷举，求给定有向道路矩阵下的最优站序。 */
final class RouteOptimizer
{
    public static function strategy(string $name): RouteStrategy
    {
        return match ($name) {
            'shortest' => new ShortestDistanceStrategy(),
            'fastest' => new FastestArrivalStrategy(),
            'deadline' => new DeadlinePriorityStrategy(),
            default => throw new ApiException('不支持的线路优化策略'),
        };
    }

    public function optimize(array $tasks, array $matrix, string $strategy, string $departure, int $serviceMinutes): array
    {
        $policy = self::strategy($strategy);
        $count = count($tasks);
        if ($count < 1 || $count > 8) throw new ApiException('每条路线支持1至8个配送站点，请拆分批次');
        if ($serviceMinutes < 0 || $serviceMinutes > 120) throw new ApiException('每站配送停留须为0至120分钟');
        $date = \DateTimeImmutable::createFromFormat('!Y-m-d H:i:s', $departure, new \DateTimeZone('Asia/Shanghai'));
        if (!$date || $date->format('Y-m-d H:i:s') !== $departure) throw new ApiException('出发时间格式不正确');
        if (!array_is_list($matrix) || count($matrix) !== $count + 1) throw new ApiException('道路矩阵与站点数量不符');
        foreach ($matrix as $row) {
            if (!is_array($row) || !array_is_list($row) || count($row) !== $count + 1) throw new ApiException('道路矩阵不完整');
            foreach ($row as $edge) {
                if ($edge === null) continue; // 无道路连接，不用直线替代。
                if (!is_array($edge)) throw new ApiException('道路指标格式不正确');
                foreach (['distance', 'time'] as $key) {
                    if (!isset($edge[$key]) || !is_numeric($edge[$key]) || !is_finite((float)$edge[$key]) || $edge[$key] < 0 || $edge[$key] > 100000000) throw new ApiException('道路距离或时间无效');
                }
            }
        }
        $departureTimestamp = $date->getTimestamp();
        $deadlines = [];
        foreach ($tasks as $task) {
            $value = $task['deadline_at'] ?? null;
            $deadlines[] = $value ? (new \DateTimeImmutable($value, new \DateTimeZone('Asia/Shanghai')))->getTimestamp() : null;
        }
        $evaluate = static function (array $order) use ($tasks, $matrix, $departureTimestamp, $deadlines, $serviceMinutes): ?array {
            $metrics = ['distance'=>0, 'drive_seconds'=>0, 'duration'=>0, 'late_count'=>0, 'late_seconds'=>0];
            $stops = []; $previous = 0;
            foreach ($order as $index) {
                $edge = $matrix[$previous][$index + 1];
                if ($edge === null) return null;
                $metrics['distance'] += (float)$edge['distance'];
                $metrics['drive_seconds'] += (float)$edge['time'];
                $arrival = $departureTimestamp + $metrics['duration'] + (float)$edge['time'];
                $metrics['duration'] += (float)$edge['time'] + $serviceMinutes * 60;
                $complete = $departureTimestamp + $metrics['duration'];
                $late = $deadlines[$index] === null ? 0 : max(0, $complete - $deadlines[$index]);
                $metrics['late_count'] += $late > 0 ? 1 : 0;
                $metrics['late_seconds'] += $late;
                $stops[] = ['id'=>(int)$tasks[$index]['id'], 'arrival_at'=>date('Y-m-d H:i:s', (int)ceil($arrival)),
                    'completed_at'=>date('Y-m-d H:i:s', (int)ceil($complete)), 'late_seconds'=>$late];
                $previous = $index + 1;
            }
            return $metrics + ['stops'=>$stops, 'task_ids'=>array_column($stops, 'id')];
        };
        $baseline = $evaluate(range(0, $count - 1));
        $best = null; $bestScore = null;
        $search = function (array $order, array $remaining) use (&$search, &$best, &$bestScore, $evaluate, $policy): void {
            if (!$remaining) {
                $candidate = $evaluate($order);
                if ($candidate === null) return;
                $score = $policy->score($candidate);
                if ($bestScore === null || $score < $bestScore) { $best = $candidate; $bestScore = $score; }
                return;
            }
            foreach ($remaining as $key=>$index) {
                $next = $remaining; unset($next[$key]);
                $search([...$order, $index], $next);
            }
        };
        $search([], range(0, $count - 1));
        if ($best === null) throw new ApiException('部分站点无可通行道路，无法生成完整路线');
        return ['strategy'=>$strategy, 'departure_at'=>$departure, 'service_minutes'=>$serviceMinutes,
            'baseline'=>$baseline, 'optimized'=>$best, 'exact'=>true];
    }
}