# **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

```{image} ./ovrp_construct.png
:width: 80%
:align: center
```

#### 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: 

```python

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."


```