Bài toán người giao hàng là gì

Người giao hàng là bài toán cơ bản trong nhóm bài toán tối ưu. Bài toán được phát biểu như sau: Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.

Có rất nhiều cách để giải bài toán này, các bạn đọc có thể search google để tìm thêm cách giải khác, ở đây, mình sẽ trình bày cách sử dụng thư viện mlrose của python để giải quyết bài toán trên.

Cài đặt chương trình và thực thi

Chúng ta giả định rằng người giao hàng sẽ đi qua 5 thành phố, và mỗi thành phố sẽ có 2 giá trị x và y tương ứng với toạ độ của các thành phố đó trên bản đồ.

1input = [
2[9, 12],
3[24, 15],
4[12 ,30],
5[4 ,3],
6[13, 27],
7]

Theo phần trước, chúng ta sẽ xây dựng 4 phần

Xây dựng vector state

Đơn giản là một vector x có số lượng phần tử bằng số lượng thành phố mà người giao hàng sẽ viết thăm

x = [x0,x1,2,x3,x4], trong đó, giá trị x1 là chỉ số của thành phố người giao hàng sẽ ghé đầu tiên, x0 là toạ độ thành phố bắt đầu

Xây dựng hàm fitness function

Mục tiêu của bài toán là tìm đường đi ngăn nhất, nên chúng ta có thể dễ dàng xây dựng hàn fitness bằng cách tính khoảng cách euclide giữa các thành phố.

 1
 2def fitness_fun(state):
 3    distance = 0
 4
 5    for index in range(1, len(state)):
 6        dist = np.linalg.norm(input[state[index-1]]-input[state[index]])
 7
 8        distance = distance + dist
 9
10    dist = np.linalg.norm(input[state[0]]-input[state[len(state)-1]])
11    distance = distance + dist
12
13    return distance
14
15fitness_cust = mlrose.CustomFitness(fitness_fun,'tsp')

Xác định loại bài toán

Đây là bài toán rời rạc không lặp, nên ta sẽ sử dụng hàm TSPOpt, length = 5 do số lượng phần tử của state là 5, maximize=False do bài toán tìm đường đi ngắn nhất .

1problem_fit = mlrose.TSPOpt(length = 5, fitness_fn = fitness_cust,
2                            maximize=False)

Xác định thuật toán tối ưu

Chúng ta vẫn tiếp tục sử dụng thuật toán simulated_annealing như trước xem kết quả như thế nào

 1#Define decay schedule
 2schedule = mlrose.ExpDecay()
 3
 4# Define initial state
 5init_state = np.array([0, 1, 2, 3, 4])
 6
 7# Set random seed
 8np.random.seed(1)
 9
10# Solve problem using simulated annealing
11best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = schedule,
12                                                      max_attempts = 10, max_iters = 500,
13                                                      init_state = init_state)
14
15print('The best state found is: ', best_state)
16print('The fitness at the best state is: ', best_fitness)

Kết quả

1The best state found is:  [1 4 2 0 3]
2The fitness at the best state is:  71.30882356753094

Đây là kết quả tối ưu của bài toán.

Thử thay bằng giải thuật di truyền GA, với tỷ lệ đột biến là 0.2

1best_state, best_fitness = mlrose.genetic_alg(problem,mutation_prob = 0.2)
2
3print('The best state found is: ', best_state)
4print('The fitness at the best state is: ', best_fitness)

Kết quả

1
2The best state found is:  [0 2 4 1 3]
3The fitness at the best state is:  71.30882356753094

Thử thay đổi tập dữ liệu input có nhiều số phần tử hơn

1input =[(1, 1), (4, 2), (5, 2), (6, 4), (4, 4), (3, 6), (1, 5), (2, 3)]

Kết quả

1The best state found is:  [3 4 5 6 7 0 1 2]
2The fitness at the best state is:  17.34261754766733

Cảm ơn các bạn đã theo dõi. Hẹn gặp bạn ở các bài viết tiếp theo.