# vrp_solver.py
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import json

def solve_vrp():
    # Sample data: 4 locations including depot (0)
    locations = [
        (0, 0),  # Depot
        (1, 3),
        (4, 3),
        (6, 1),
        (5, 5)
    ]
    
    # Distance matrix
    distance_matrix = [[0, 2, 9, 10],
                       [1, 0, 6, 4],
                       [15, 7, 0, 8],
                       [6, 3, 12, 0]]

    # Create the routing index manager
    manager = pywrapcp.RoutingIndexManager(len(distance_matrix), 1, 0)

    # Create Routing Model
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback to calculate distance
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc (based on distance)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Set parameters for the solver
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Solve the problem
    solution = routing.SolveWithParameters(search_parameters)

    # Get the results
    routes = []
    if solution:
        for vehicle_id in range(1):  # Assuming one vehicle
            index = routing.Start(vehicle_id)
            route = []
            while not routing.IsEnd(index):
                route.append(manager.IndexToNode(index))
                index = solution.Value(routing.NextVar(index))
            routes.append(route)
    
    return json.dumps(routes)

if __name__ == "__main__":
    print(solve_vrp())
