Hãy tưởng tượng bạn là tài xế lái xe du lịch, mỗi chuyến đi bạn phải xuất phát từ nhà xe và đi đến đón N vị khách tại nhà riêng của họ, bạn sẽ chọn đón ai trước? Hay công ty của bạn cung cấp nước đóng chai mỗi ngày phải giao hàng ở 100 cửa tiệm khác nhau trên địa bàn thành phố, bạn sẽ giao chúng như thế nào để tiết kiệm quãng đường cũng như thời gian di chuyển nhất?

Vấn đề tối ưu quãng đường di chuyển là một trong những vấn đề quan trọng của Logistic, những công cụ như Badger Map ra đời chính là để giải quyết vấn đề này và đã rất thành công. Trong bài viết này chúng ta sẽ cùng nhau thử xây dựng một thuật toán tối ưu hóa tuyến đường đơn giản bằng ngôn ngữ Python, sau đó bạn có thể so sánh kết quả với kết quả khi dùng những công cụ khác, tôi nghĩ kết quả sẽ làm bạn khá bất ngờ đấy.

Trong bài viết trước "Tính quãng đường vận chuyển bằng hàm API của Google Map" trên website này, bạn đã được giới thiệu về cách lấy khoảng cách giữa các điểm cụ thể trên Google Map, từ đó bạn có thể xây dựng được một ma trận khoảng cách đơn giản bằng excel, link bài viết https://erx.vn/truy-van-so-km-giua-2-dia-diem-bat-ky-bang-ma-tran-vuong-7122103947.html .Ma trận khoảng cách sẽ được dùng để làm input đầu vào cho bài toán tối ưu hóa tuyến đường (Route planner optimizer) với ưu điểm là dễ dàng truy xuất.

Bước 1:

Đầu tiên chúng ta có một ma trận khoảng cách đầu vào có dạng tương tự như trong hình, ở đây tôi giả sử có dữ liệu các địa điểm là A, B, C, D, E, F, G, với những ô có giá trị 0 là địa điểm trùng nhau hoặc là không có đường đi giữa hai điểm đó. Ví dụ: ô ở hàng A cột C có giá trị bằng 0 có nghĩa là không có đường đi từ A đến C. Trên thực tế nếu bạn dùng Google Map để lấy bản đồ thì hầu như là không có những ô có giá trị bằng 0, nhưng ở đây tôi vẫn để ô có giá trị 0 để tổng quát trường hợp nhất.

• Bạn có thể tưởng tượng ma trận này giống như một đồ hình (graph) thể hiện khoảng cách giữa các điểm:

Bước 2:

Dùng thư viện Pandas của Python để đọc dữ liệu khoảng cách trong file excel:

• Code:

# Import thư viện cần sử dụng

import pandas as pd

import itertools

import numpy as np

 

# Load dữ liệu khoảng cách từ file excel

matrix = pd.read_excel('Dijkstra.xlsx')

matrix.set_index(matrix.columns[0], inplace = True)

• Ta sẽ có được ma trận khoảng cách như sau:

• Nếu muốn lấy khoảng cách từ điểm A đến điểm B ta chỉ cần truy xuất đến vị trí A, B trên ma trận matrix.loc['A']['B']

Bước 3:

Thuật toán tìm đường đi ngắn nhất qua các điểm:

• Ý tưởng của thuật toán này rất đơn giản: ta có một danh sách gồm điểm xuất phát (kho), những điểm cần đi (cửa hàng) và điểm đến cuối cùng (kho),  ta sẽ tìm hết tất cả những tuyến đường khả dĩ từ điểm xuất phát đi qua tất cả những điểm cần đến và về điểm đến cuối cùng bằng cách sử dụng chỉnh hợp.
• Với mỗi tuyến đường khả dĩ ta sẽ tính tổng quảng đường của nó.
• Cuối cùng lấy ra tuyến đường có distance nhỏ nhất. 

def route_optimization(start,end,matrix,destination=matrix.columns,number_of_node=len(matrix.columns)):

    list_distance = []

    path_filter = []

    

    ### Tìm tất cả đường đi khả dĩ

    all_path = list(itertools.permutations(destination, number_of_node))

    for i in range(len(all_path)):

        if all_path[i][0] == start and all_path[i][-1] == end:

            path_filter.append(all_path[i])

 

    ### Tính tổng km của tất cả tuyến đường khả dĩ

    for index, value in enumerate(path_filter):

        prev_node = start

        distance = 0 

        count = 0

        for i, current_node in enumerate(value):

            if matrix.loc[current_node][prev_node] == 0 and count>0:

                break

            distance += matrix.loc[current_node][prev_node]

            prev_node = current_node

            count+=1

        if count == number_of_node:

            list_distance.append([distance, index])

 

    ### Chọn ra tuyến đường có tổng km nhỏ nhất

    list_distance = np.array(list_distance)

    min_distance = np.min(list_distance[:,0])

    a = np.where(list_distance == min_distance)

    trajectory = path_filter[list_distance[a[0][0]][1]]

    return  start, end, trajectory, min_distance