File size: 2,479 Bytes
4b02f53 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | from __future__ import annotations
from typing import List
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
def solve_tsp(time_matrix: List[List[float]]) -> List[int]:
"""
OSRMのduration行列（秒）を入力に、0番ノード（Start）発→全訪問→Start戻りの巡回順序を返す。
OR-Toolsで解けない場合は貪欲法でフォールバックします。
返り値例: [0, 3, 2, 1, 0]
"""
n = len(time_matrix) if time_matrix else 0
if n <= 1:
return list(range(n))
# 行列のサニタイズ（Noneや欠損を大値に、対角は0、int秒へ）
BIG = 10**9
matrix: List[List[int]] = []
for i in range(n):
row_i = []
for j in range(n):
try:
v = time_matrix[i][j]
v = float(v) if v is not None else BIG
except Exception:
v = BIG
if i == j:
v = 0.0
row_i.append(int(max(0, round(v))))
matrix.append(row_i)
# OR-Tools セットアップ
manager = pywrapcp.RoutingIndexManager(n, 1, 0) # depot=0
routing = pywrapcp.RoutingModel(manager)
def transit_cb(from_index, to_index):
i = manager.IndexToNode(from_index)
j = manager.IndexToNode(to_index)
return matrix[i][j]
transit_idx = routing.RegisterTransitCallback(transit_cb)
routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
params.time_limit.FromSeconds(1) # 1秒で切り上げ（HF Spaces向けに軽量）
solution = routing.SolveWithParameters(params)
if solution:
index = routing.Start(0)
order: List[int] = []
while not routing.IsEnd(index):
order.append(manager.IndexToNode(index))
index = solution.Value(routing.NextVar(index))
order.append(manager.IndexToNode(index)) # 最後にdepot(0)へ戻る
return order
# フォールバック：近傍貪欲
unvisited = set(range(1, n))
order = [0]
cur = 0
while unvisited:
nxt = min(unvisited, key=lambda j: matrix[cur][j])
order.append(nxt)
unvisited.remove(nxt)
cur = nxt
order.append(0)
return order
|