# dist[t][p] = dist from taxi t to passenger p
dist = [[90, 76, 75, 70, 80, 85],
[35, 85, 55, 65, 45, 65],
[125, 95, 90, 105, 95, 100],
[45, 110, 95, 115, 75, 90],
[60, 105, 80, 75, 90, 100],
[45, 65, 110, 95, 80, 100]]
n = len(dist)
MAX_DIST = max(max(l) for l in dist)
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# passenger_of[taxi t] = passenger p
passenger_of = [0] * n
taxi_of = [0] * n
for i in range(n):
passenger_of[i] = model.NewIntVar(0, n-1, f'passenger of taxi {i}')
taxi_of[i] = model.NewIntVar(0, n-1, f'taxi of passenger {i}')
model.AddInverse(passenger_of, taxi_of)
total_dist = 0
for t in range(n):
travel_dist = model.NewIntVar(0, MAX_DIST, f'dist for taxi {t}')
# travel_dist == dist[t][passenger_of[t]]
model.AddElement(passenger_of[t], dist[t], travel_dist)
total_dist += travel_dist
model.Minimize(total_dist)
solver = cp_model.CpSolver()
if solver.Solve(model) == cp_model.OPTIMAL:
print([f'{v}={solver.Value(v)}' for v in passenger_of])
print(solver.ResponseStats())