sub optimal solution for vrp

[sudarsanvs]

What version of OR-Tools and what language are you using?
Version: main/v9.6.2534.
Language: Python

Which solver are you using (e.g. Routing Solver)
Routing Solver
What operating system (Windows, ...) and version?
Windows 10
What did you do?
Steps to reproduce the behavior:

1. Go to google or tools , vrp example
2. Changed the distance matrix and ran the code for 500 odd nodes and 3 vehicle and set time limit at 1000 seconds and had a constraint on each vehicle that it can travel to max 600 m
3. kept FirstSolutionStrategy as automatic
4. after running for 1000s the output seems to be very poor and sub optimal ,I am attaching the route image , we can see clusters getting formed randomly , would like to know ways to improve the solution

What did you expect to see
expected to see good reduction in total distance travelled

What did you see instead?
sub optimal result

import pandas as pd
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import numpy as np
import time


def create_data_model():
    """Stores the data for the problem."""
    data = {}

    file_path = 'distance_1.csv'
    df = pd.read_csv(file_path,index_col = 0)
    dist = df.values.tolist()
    data['distance_matrix'] = dist

    print("############")
    data['num_vehicles'] = 3
    data['depot'] = 0
    return data



def print_solution(data, manager, routing, solution):
    """Prints solution on console."""

    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {}m'.format(max_route_distance))



def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)


    # Create and register a transit callback.
    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Distance constraint.
    dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        600,  # vehicle maximum travel distance
        True,  # start cumul to zero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.SWEEP)
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.time_limit.seconds = 1000
    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print('No solution found !')


if __name__ == '__main__':
    start_time = time.time()
    main()
    end_time = time.time()
    total_time = end_time - start_time
    print("Total Time = ", total_time)

[Mizux]

Two things:

1. In your code:

   # Setting first solution heuristic.
   search_parameters = pywrapcp.DefaultRoutingSearchParameters()
   search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.SWEEP)
    search_parameters = pywrapcp.DefaultRoutingSearchParameters() # WHY calling default again ?
   search_parameters.time_limit.seconds = 1000

So here your SWEEP set will be ignored since you overwrite the search_parameters

2. Seems you didn't enable the Guided Local Search metaheuristique....
   So please add:

search_parameters.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(1000)
search_parameters.log_search = True # optional to follow objective cost

[sudarsanvs]

hi update ,
the distance matrix was float values changed to int and the run time came to 600 secs .
@Mizux as u mentioned made changes to add guided local search instead of default parameters , the run time increased to 1000 secs

[Mizux]

run time came to 600 secs .

This means solver took 600s to find a first solution

note: Local Search Metaheuristic will always consume the time budget so that's why using my patch you'll end up with 1000s
note2: GLS can dramatically increase objective and in your case it only run from 600 to 1000 aka 400s....
note3: You can also add a solution callback to stop the search if you want to stop earlier e.g. after solver has reached a plateau...