Distance Decreases After Adding Nodes in the Dataset Randomly

Question

I’m currently solving on the optimizing route in Capacitated Vehicle Routing Problem where initially with 125 (orignal data), the Nearest Neighbor Approach provided optimal solution of 23.51km. However, when I added additional random nodes 10%/13, nearest-neighbor approach will provide optimal result of 20.38km.

I was wondering whether this is a nature of greedy algorithm or would it be a cause of my algorithm?

Below is my code for the Nearest Neighbor Approach:

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

def read_csv_file(filename, fleet_capacity):
    df = pd.read_csv(filename)
    coordinates = df[['latitude', 'longitude']].values
    capacity = df['capacity'].values  
    capacity = np.insert(capacity, 0, fleet_capacity)
    return coordinates, capacity

# Calculate the distance matrix using Haversine formula
def calculate_distance_matrix(coordinates):
    num_points = len(coordinates)
    dist_matrix = np.zeros((num_points, num_points))
    for i in range(num_points):
        for j in range(i + 1, num_points):
            dist = calculate_haversine_distance(coordinates[i], coordinates[j])
            dist_matrix[i, j] = dist
            dist_matrix[j, i] = dist
    return dist_matrix

# Calculate the Haversine distance between two lat-lon points
def calculate_haversine_distance(point1, point2):
    R = 6371  # Earth's radius in kilometers
    lat1, lon1 = np.radians(point1)
    lat2, lon2 = np.radians(point2)
    dlat = lat2 - lat1
    dlon = lon2 - lon1
    a = np.sin(dlat / 2)**2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon / 2)**2
    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1 - a))
    return R * c

# Travel cost [distance between customer node i and j]
def calculate_route_distance(route, dist_matrix):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += dist_matrix[route[i], route[i + 1]]
    return total_distance

def nearest_neighbor_fleet(dist_matrix, capacity, fleet_size, fleet_capacity):
    num_points = dist_matrix.shape[0]
    visited = np.zeros(num_points, dtype=bool)
    visited[0] = True  # Mark depot as visited
    routes = []
    
    for fleet_count in range(fleet_size):
        current_capacity = 0
        route = [0]  # Start from the depot
        
        while True:
            current_node = route[-1]
            nearest = None
            min_dist = float('inf')

            for neighbor in range(1, num_points):  # Exclude depot (0) for neighbors
                # Ensure the node is unvisited, and capacity does not exceed the fleet limit
                if not visited[neighbor] and current_capacity + capacity[neighbor] <= fleet_capacity:
                    if dist_matrix[current_node, neighbor] < min_dist:
                        nearest = neighbor
                        min_dist = dist_matrix[current_node, neighbor]

            if nearest is None:  # No more nodes can be added to this route
                break

            # Add the nearest node to the route
            route.append(nearest)
            visited[nearest] = True
            current_capacity += capacity[nearest]

        # Complete the route by returning to the depot
        route.append(0)
        routes.append(route)

        # Stop if all nodes have been visited
        if np.all(visited[1:]):
            break

    # Final validation: Ensure no route exceeds fleet capacity
    for route_index, route in enumerate(routes):
        route_capacity = sum(capacity[node] for node in route if node != 0)
        if route_capacity > fleet_capacity:
            raise ValueError(f"Route {route_index + 1} exceeds fleet capacity! Capacity: {route_capacity}")

    return routes


# Solve the VRP problem using the improved nearest neighbor heuristic
def vrp_solver(filename, fleet_size, fleet_capacity, depot_coords):
    coordinates, capacity = read_csv_file(filename, fleet_capacity)
    coordinates = np.vstack([depot_coords, coordinates])  # Adding the depot to the start
    dist_matrix = calculate_distance_matrix(coordinates)
    routes = nearest_neighbor_fleet(dist_matrix, capacity, fleet_size, fleet_capacity)
    return routes, dist_matrix, coordinates

# Plot the resulting VRP routes
def plot_routes(coordinates, routes):
    plt.figure(figsize=(10, 8))
    for route_index, route in enumerate(routes):
        route_coords = np.array([coordinates[node] for node in route])
        plt.plot(route_coords[:, 1], route_coords[:, 0], marker='o', label=f'Fleet {route_index + 1}')
        for i, node in enumerate(route):
            plt.text(coordinates[node][1], coordinates[node][0], str(node), fontsize=12, ha='right')
    plt.xlabel("Longitude")
    plt.ylabel("Latitude")
    plt.title("Vehicle Routing Problem (VRP) Routes")
    plt.legend()
    plt.grid(True)
    plt.show()

# Example parameters
filename = '/Users/jay/Downloads/Logistics_Data.csv' 
fleet_size = 5
fleet_capacity = 300
depot_coords = [(), ()]

# Solve the VRP and get the solution
solution, dist_matrix, coordinates = vrp_solver(filename, fleet_size, fleet_capacity, depot_coords)

# Total Distance Travelled (Minimized)
total_distance_all_fleets = 0
for fleet_index, route in enumerate(solution):
    total_distance = calculate_route_distance(route, dist_matrix)
    total_distance_all_fleets += total_distance
    print(f"Vehicle {fleet_index + 1} Route: {route}")
    print(f"Total distance covered by Vehicle {fleet_index + 1}: {total_distance:.2f} km")


print(f"\nTotal distance covered by all fleets: {total_distance_all_fleets:.2f} km")

# Plot routes
plot_routes(coordinates, solution)

And below is the optimal result obtained with original data:

Vehicle 1 Route: [0, 1, 125, 124, 122, 123, 121, 120, 91, 90, 88, 89, 78, 79, 80, 81, 87, 82, 86, 83, 84, 85, 2, 4, 3, 32, 33, 34, 30, 31, 5, 6, 7, 28, 27, 20, 19, 21, 26, 25, 29, 24, 23, 22, 18, 17, 16, 15, 12, 11, 13, 14, 8, 10, 35, 36, 38, 77, 76, 75, 74, 73, 0] Total distance covered by Vehicle 1: 5.05 km Vehicle 2 Route: [0, 37, 39, 41, 42, 46, 48, 47, 49, 50, 51, 45, 44, 43, 40, 52, 65, 64, 66, 63, 56, 57, 59, 0] Total distance covered by Vehicle 2: 5.15 km Vehicle 3 Route: [0, 9, 92, 93, 94, 95, 97, 98, 100, 99, 96, 119, 101, 102, 103, 117, 118, 116, 115, 105, 104, 106, 114, 113, 112, 110, 109, 53, 0] Total distance covered by Vehicle 3: 6.78 km Vehicle 4 Route: [0, 72, 71, 70, 69, 67, 68, 54, 55, 58, 61, 60, 62, 111, 108, 107, 0] Total distance covered by Vehicle 4: 6.53 km

Total distance covered by all fleets: 23.51 km

And this are the optimal result obtained with 10% addition:

Vehicle 1 Route: [0, 1, 138, 137, 136, 134, 135, 133, 132, 101, 100, 98, 99, 87, 88, 89, 90, 97, 91, 96, 92, 94, 93, 95, 2, 5, 3, 4, 36, 37, 39, 38, 40, 41, 42, 43, 44, 46, 47, 52, 53, 0] Total distance covered by Vehicle 1: 3.43 km Vehicle 2 Route: [0, 6, 7, 35, 34, 33, 29, 30, 24, 22, 25, 20, 21, 19, 18, 17, 23, 31, 32, 8, 9, 16, 15, 12, 14, 13, 11, 10, 27, 28, 26, 86, 85, 84, 83, 80, 81, 82, 79, 78, 77, 75, 74, 72, 73, 71, 61, 62, 64, 63, 65, 66, 69, 67, 59, 0] Total distance covered by Vehicle 2: 5.45 km Vehicle 3 Route: [0, 45, 48, 49, 50, 55, 51, 54, 56, 57, 58, 60, 68, 70, 76, 102, 103, 104, 106, 105, 108, 109, 111, 110, 107, 131, 112, 113, 129, 130, 124, 0] Total distance covered by Vehicle 3: 6.97 km Vehicle 4 Route: [0, 114, 128, 127, 116, 115, 117, 126, 125, 123, 121, 120, 119, 122, 118, 0] Total distance covered by Vehicle 4: 4.53 km

Total distance covered by all fleets: 20.38 km