Combinatorial optimization

Hungarian Algorithm

http://accord-framework.net/docs/html/T_Accord_Math_Optimization_Munkres.htm

import numpy as np
from scipy.optimize import linear_sum_assignment
import datetime
 
# Example weight measurements and truck trips data
weight_measurements = [
    {'timestamp': 1621784000, 'weight': 100},
    {'timestamp': 1621784100, 'weight': 200},
    {'timestamp': 1621784200, 'weight': 150},
    {'timestamp': 1621784300, 'weight': 175}
]
 
truck_trips = [
    {'timestamp': 1621784030, 'trip_id': 'A'},
    {'timestamp': 1621784130, 'trip_id': 'B'},
    {'timestamp': 1621784160, 'trip_id': 'C'}
]
 
# Create a cost matrix
num_measurements = len(weight_measurements)
num_trips = len(truck_trips)
cost_matrix = np.zeros((num_measurements, num_trips))
 
for i, measurement in enumerate(weight_measurements):
    for j, trip in enumerate(truck_trips):
        time_diff = abs(measurement['timestamp'] - trip['timestamp'])
        # Assign cost as time difference or a high value if not compatible
        cost_matrix[i, j] = time_diff if time_diff <= 60 else 9999
 
# Solve using the Hungarian algorithm
row_ind, col_ind = linear_sum_assignment(cost_matrix)
 
# Print the matching results
for i, measurement_idx in enumerate(row_ind):
    trip_idx = col_ind[i]
    measurement = weight_measurements[measurement_idx]
    trip = truck_trips[trip_idx]
    print(f"Weight measurement with timestamp {datetime.datetime.fromtimestamp(measurement['timestamp'])} matched to trip with timestamp {datetime.datetime.fromtimestamp(trip['timestamp'])}.")
    print(f"Weight: {measurement['weight']}, Trip ID: {trip['trip_id']}")
    print()
 
# Handle unmatched measurements or trips
unmatched_measurements = set(range(num_measurements)) - set(row_ind)
unmatched_trips = set(range(num_trips)) - set(col_ind)
 
# Example handling of unmatched measurements
for measurement_idx in unmatched_measurements:
    measurement = weight_measurements[measurement_idx]
    closest_trip_idx = min(range(num_trips), key=lambda x: abs(measurement['timestamp'] - truck_trips[x]['timestamp']))
    trip = truck_trips[closest_trip_idx]
    print(f"Weight measurement with timestamp {datetime.datetime.fromtimestamp(measurement['timestamp'])} unmatched, assigned to closest trip with timestamp {datetime.datetime.fromtimestamp(trip['timestamp'])}.")
    print(f"Weight: {measurement['weight']}, Trip ID: {trip['trip_id']}")
    print()
 
# Example handling of unmatched trips
for trip_idx in unmatched_trips:
    trip = truck_trips[trip_idx]
    print(f"Trip with timestamp {datetime.datetime.fromtimestamp(trip['timestamp'])} unmatched.")
    print(f"Trip ID: {trip['trip_id']}")
    print()

---

🌱 Back to Garden