Distance Matrix Rounding

[boraaktas]

I'm having trouble understanding the rules for rounding in the edge_weight matrix. Below is a code where I calculate the cost by using edge_weight matrix of instance from vrplib and compare it with the cost value from instance file. I calculate these costs based on the edge_weight matrix of the instance obtained from CVRPLIB using vrplib. The output of the code is a bit long, so I've uploaded it as a text file. Thank you.

num = 0 # number of instances
false_num = 0 # number of instances with wrong solution
true_num = 0 # number of instances with correct solution

path = Input_Handler_CVRP.get_input_path()

# FINAL_INSTANCE_NAMES is the list of the instances that are going to be tested
# it contains the names of the instances that has less than 1500 nodes and has node_coord
for index in range(len(FINAL_INSTANCE_NAMES)):

    instance_name = FINAL_INSTANCE_NAMES[index] # name of the instance
    instance_set = FINAL_INSTANCE_SETS[index] # set of the instance

    instance_dict: dict = vrplib.read_instance(path + '/' + instance_set + '/' + instance_name + '.vrp')
    solution_dict: dict = vrplib.read_solution(path + '/' + instance_set + '/' + instance_name + '.sol')

    opt_route: list = solution_dict['routes'] # list of lists (in the instance file, got from vrplib)
    opt_dist = solution_dict['cost'] # optimal distance (in the instance file, got from vrplib)

    dist_matrix: np.ndarray = instance_dict['edge_weight'] # distance matrix (in the instance file, got from vrplib)
    weigth_type: str = instance_dict['edge_weight_type'] # type of the distance matrix (in the instance file, got from vrplib)

    sol_dist = calculate_solution_distance(dist_matrix, opt_route)

    if sol_dist == opt_dist:
        print(instance_name + ' is OKEY with distance ' + str(opt_dist) + ' *** ' + weigth_type)
        true_num += 1
    else:
        print('Solution distance: ' + str(sol_dist) + ' Optimal distance: ' + str(opt_dist) + 
                ' in instance ' + instance_name + ' *** ' + weigth_type)
        false_num += 1

    num += 1

print('True: ' + str(true_num) + ' False: ' + str(false_num) + ' Total: ' + str(num))

The functions that I use to calculate distances are below:

def calculate_route_distance(matrix: np.ndarray, route: list):
    route_distance = 0

    for i in range(len(route)):

        if i == 0:
            node_from = 0 # depot
            node_to = route[i] # first node to visit
        else:
            node_from = route[i - 1] 
            node_to = route[i]

        dist = matrix[node_from][node_to] 
        dist = round(dist, 0)
        route_distance += dist

    last_node = route[-1] # last node before returning to the depot

    dist = matrix[last_node][0] # distance from the last node to the depot
    dist = round(dist, 0)
    route_distance += dist

    return route_distance

def calculate_solution_distance(matrix: np.ndarray, routes: list):
    solution_distance = 0

    for route in routes: # it iterates over the routes and calculates the distance of each route
        route_distance = calculate_route_distance(matrix, route) # it returns the distance of the route
        solution_distance += route_distance

    return solution_distance

I am rounding distances that I get from edge_weight matrix to 0 decimal numbers by using round(dist, 0) method.

Here is the output of the code: output.txt

To use that code you have to just specify the path, FINAL_INSTANCE_NAMES list, and FINAL_INSTANCE_SETS list.

Thank you so much :)

[leonlan]

Hi @boraaktas!

Thanks for opening this issue. There is nothing wrong with your code and the vrplib package (fortunately!). The differences in the solution cost calculation and the cost provided by the files are due to different rounding conventions that are used in the literature.

As can be seen in output.txt file, the X instances work fine. That's because, in this instance set, the convention is to round the distances to the nearest integer. This can be found back in the associated paper.

However, the CMT, tai, Golden, and Li instance sets don't use this rounding convention. Even though their VRPLIB instance format specifies EUC_2D, whether to round or not is something that is not specified accurately by these instances. To know how to round the distances in these instances, you will have to look into the literature and find the corresponding papers on how they handle this.

This is something I can't do much about because the instances are provided by CVRPLIB, which I'm not the maintainer of. I suggest simply using the X instances, which are currently the benchmark instances for CVRP. Hope this helps.

[boraaktas]

Thank you so much for your response, @leonlan. Just as you mentioned, I also noticed that a different approach was used in those sets. However, what puzzled me the most was encountering errors in the instances below:

Solution distance: 1319.0 Optimal distance: 1312 in instance B-n50-k8 EUC_2D Solution distance: 1155.0 Optimal distance: 1153 in instance B-n57-k7 EUC_2D Solution distance: 537.0 Optimal distance: 534 in instance E-n30-k3 EUC_2D Solution distance: 721.0 Optimal distance: 724 in instance F-n45-k4 EUC_2D Solution distance: 1159.0 Optimal distance: 1162 in instance F-n135-k7 *** EUC_2D

It is quite strange that while other instances in these sets provide correct results with rounding to 0 decimals, these cases having errors. Do you think that the values mentioned in the solution files might be incorrect? I don't want to dismiss all other sets based on just a few instances, though! :)

Once again, thank you so much.

[leonlan]

I can't say whether the values are incorrect, but it may well be. The best bet is to contact the maintainers of CVRPLIB or to check the references about these data.

[boraaktas]

Yes, you're right. I appreciate your assistance. Wish you the best with your work.