Constructive Heuristics for Open Vehicle Routing Problem (OVRP)

Problem

• The Open Vehicle Routing Problem (OVRP) is a variant of VRP that has open routes.

  • Given: A depot, a set of customers with coordinates and demands, a fleet of vehicles of the same capacity

  • Objective: Minimize the total travelling distances of all routes

  • Constraints: The vehicles start from the depot and do not return to the depot, each customer be visited once and only once, all the demands should be satisfied, the vehicle capacity should not be exceeded

Algorithm Design Task

• Constructive heuristics start from the depot and iteratively select the next unvisited customer. The task is to design the heuristic for selecting the next customer in each iteration.

  • Inputs: Current node, unvisited nodes, demands of unvisited nodes, rest capacity of current vehicle, distance matrix

  • Outputs: Next node

Evaluation

• Dataset: Each designed algorithm is evaluated on 16 OVRP instances. The number of customers in each instance is 50 and the coordinates are randomly sampled from [0,1], the demands are sampled from {1,2,…,9} and the capacity is 40.

• Fitness: The average total distance over the 16 instances is used as the fitness in search.

Template:

template_program = '''
import numpy as np

def select_next_node(current_node: int, depot: int, unvisited_nodes: np.ndarray, rest_capacity: np.ndarray, demands: np.ndarray, distance_matrix: np.ndarray) -> int:
    """Design a novel algorithm to select the next node in each step.
    Args:
        current_node: ID of the current node.
        depot: ID of the depot.
        unvisited_nodes: Array of IDs of unvisited nodes.
        rest_capacity: rest capacity of vehicle
        demands: demands of nodes
        distance_matrix: Distance matrix of nodes.
    Return:
        ID of the next node to visit.
    """
    next_node = unvisited_nodes[0]
    return next_node
'''

task_description = "Help me design a novel algorithm to select the next node in each step."