Using Local Search to solve CBUS problem

Question

I solve this problem by Constraint Programming and Greedy, but my teach had me to solve by Local Search. I have no idea to solve this by Local Search. Can anyone help me ?
Description
There are n passengers 1,2, ...,n. The passenger i want to travel from point i to point i + n (i = 1,2, ...,n). There is a bus located at point 0 and has k places for transporting the passengers (it means at any time, there are at most k passengers on the bus). You are give the distance matrix c in which c(i, j) is the travelling distance from point i to point j (i,j = 0,1, ...,2n). Compute the shortest route for the bus, serving n passengers and coming back to point 0.

Input
The first line contains n and k (1 ≤ n ≤ 11, 1 ≤ k ≤ 10).
Line i + 1 (i = 1,2,..., 2n + 1) contains the (i - 1)-th row of the matrix c (rows and columns are indexed from 0,1,2,...,2n).
Output
Unique line contains the length of the shortest route.

Answer 1

You can use an iterated local search algorithm, which consists of 2 main steps:

1. Generating an initial solution.

2. Improving it by exploring the neighborhood of the current solution.

A neighborhood is a set of solutions that are similar to the current solution in some way, such as changing the order of stops, adding or removing stops, or swapping stops between routes.

The algorithm iteratively applies a local search procedure to find the best solution in the neighborhood, and then uses a perturbation mechanism to escape from local optima and explore new regions of the solution space.