Giải quyết vấn đề nhân viên bán hàng du lịch

Nov 29 2022

Tối ưu hóa các tuyến đường giao bưu kiện bằng cách sử dụng python để tiết kiệm chi phí giao hàng (Trường hợp nghiên cứu: giao bưu kiện ở Bandung, Indonesia với dữ liệu đơn giản) Bài toán Người bán hàng đi du lịch hay TSP là một bài toán tối ưu hóa tổ hợp cố gắng trả lời câu hỏi “Cho một danh sách các thành phố và khoảng cách giữa mỗi cặp thành phố, con đường ngắn nhất có thể đi qua mỗi thành phố đúng một lần và trở về thành phố ban đầu là bao nhiêu?”. Nói một cách đơn giản, TSP có nhiệm vụ tìm ra con đường ngắn nhất giữa một tập hợp các điểm phải đến.

Tối ưu hóa lộ trình vận chuyển bưu kiện bằng python để tiết kiệm chi phí vận chuyển (Trường hợp nghiên cứu: vận chuyển bưu kiện ở Bandung, Indonesia với dữ liệu đơn giản)

Ảnh của José Martín Ramírez Carrasco trên Bapt

Bài toán người bán hàng du lịch hay TSP là một bài toán tối ưu hóa tổ hợp cố gắng trả lời câu hỏi “Cho một danh sách các thành phố và khoảng cách giữa mỗi cặp thành phố, con đường ngắn nhất có thể đi qua mỗi thành phố đúng một lần và quay trở lại thành phố ban đầu là gì? ”. Nói một cách đơn giản, TSP có nhiệm vụ tìm ra con đường ngắn nhất giữa một tập hợp các điểm phải đến. Nó trở thành một vấn đề thực sự trong chuỗi cung ứng và ngành hậu cần khi chúng phát triển vượt bậc sau sự gia tăng của thương mại điện tử.

Vậy tại sao TSP lại quan trọng? Về bản chất, nó giúp công ty thu được nhiều lợi nhuận hơn bằng cách tiết kiệm thời gian và nguồn lực. Trong ngành hậu cần, một trong những cách để tạo ra nhiều lợi nhuận hơn là hiệu quả về chi phí và thời gian giao hàng. Có nhiều cách khác nhau để đạt được điều đó, một trong số đó là giải Bài toán Người bán hàng Đi du lịch (TSP), trong đó bạn đang cố gắng tìm các tuyến đường hiệu quả nhất để đi trên đường. Nó càng được giải quyết hiệu quả thì càng tốn ít thời gian lái xe, càng tiết kiệm được nhiều nhiên liệu, càng cần ít giờ và thậm chí giao được nhiều kiện hàng hơn . Kết quả là, bảng cân đối kế toán của bất kỳ hoạt động kinh doanh dựa trên giao hàng nào sẽ được hưởng lợi gấp đôi.

Vì vậy, tôi đang cố gắng tạo một bản demo của Bài toán người bán hàng lưu động này cho một nhân viên chuyển phát nhanh của một công ty chuyển phát bưu kiện ở Bandung để giảm chi phí giao hàng .

Lưu ý : vì đây là bản trình diễn đơn giản nên dữ liệu được sử dụng chỉ là 8 điểm giả giao hàng và dữ liệu là dữ liệu được tạo ngẫu nhiên.

Kịch bản

Bạn là quản lý tại một trung tâm dịch vụ chuyển phát bưu kiện ở Bandung. Bạn nên giao các gói hàng cho một số khách hàng từ kho hàng của mình bằng 1 phương tiện. Có thể thấy sự phân bố của các điểm giao hàng và kho hàng bên dưới (Hình 1).

Hình 1. Phân bố không gian của các điểm giao hàng

**Dù sao, bạn có thể điều chỉnh số lượng xe và số điểm giao hàng theo ý muốn bằng cách chỉnh sửa mã nguồn bên dưới

mục tiêu

Tìm các tuyến đường tốt nhất để cung cấp tất cả các bưu kiện cho khách hàng.

Để theo dõi mức độ tốt của mô hình hoặc giải pháp mà chúng tôi đang cố triển khai, tốt hơn hết là xác định các chỉ số kinh doanh. Vì không có dữ liệu của các trường hợp liên quan nên tôi sẽ chỉ đề cập đến tiềm năng mà không đo lường xem giải pháp đó tốt đến đâu. Những số liệu kinh doanh tiềm năng đó là:

Phí vận chuyển
Thời gian sử dụng
Tỷ lệ giao hàng đúng hạn
Điểm hài lòng của khách hàng (điểm CSAT)

Bằng cách sử dụng Google OR-Tools , lộ trình tốt nhất với một phương tiện là:

Kho -> Địa chỉ 5 -> Địa chỉ 6 -> Địa chỉ 7 -> Địa chỉ 4 -> Địa chỉ 3 -> Địa chỉ 2 -> Địa chỉ 1 -> Kho

Khoảng cách tuyến đường: 7,44 km

Hình 2. Hoạt hình tuyến đường ngắn nhất

Các bước kỹ thuật

Hình 3. Lưu đồ xử lý trong Python

Mã đầy đủ được cung cấp ở đây .

I. Nhập thư viện và đọc dữ liệu

Trước hết, chúng tôi phải nhập các thư viện vào Google Colab. Chúng tôi sẽ sử dụng một số thư viện.

numpy và pandas : cho các phép toán số và thao tác dữ liệu
itertools : để tạo các trình vòng lặp để lặp hiệu quả
ast : để xử lý cây ngữ pháp cú pháp trừu tượng Python
yêu cầu : để thực hiện các yêu cầu HTTP
json : để làm việc với dữ liệu JSON
networkx : để tạo, thao tác và nghiên cứu cấu trúc, động lực và chức năng của các mạng phức tạp
osmnx : để tải xuống dữ liệu không gian địa lý từ OpenStreetMap và lập mô hình, dự án, trực quan hóa và phân tích mạng lưới đường phố trong thế giới thực và bất kỳ dạng hình học không gian địa lý nào khác
folium : để trực quan hóa dữ liệu đã được thao tác bằng Python trên bản đồ tờ rơi tương tác
ortools : để giải các bài toán tối ưu tổ hợp

# Install and Import Library
pip install osmnx
pip install ortools

import numpy as np
import pandas as pd
import itertools
import ast
import requests
import json
import networkx as nx
import osmnx as ox
import folium
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

from google.colab import drive
drive.mount('/content/drive')

import warnings 
warnings.filterwarnings('ignore')

# Read data
df_points = pd.read_excel('/content/drive/MyDrive/dataset/delivery_destinations.xlsx')

Hình 4. Bộ dữ liệu điểm giao hàng

II. mã hóa địa lý

Mã hóa địa lý là quá trình chuyển đổi mô tả về một vị trí — chẳng hạn như một cặp tọa độ, địa chỉ hoặc tên của một địa điểm — thành một vị trí trên bề mặt trái đất. Tóm lại, chúng tôi đang cố truy xuất vĩ độ và kinh độ từ địa chỉ của tập dữ liệu. Kinh độ và vĩ độ này sau này sẽ được sử dụng để tính khoảng cách di chuyển giữa các điểm và xác định tuyến đường giao hàng tốt nhất.

Tôi đang sử dụng API TẠI ĐÂY cho Mã hóa địa lý vì nó khá chính xác và miễn phí sử dụng (với các cuộc gọi hạn chế). Bạn có thể đọc bài viết này để biết chi tiết của quá trình này.

# Define variables
apikey = '<YOUR-API-KEY-HERE>'
url = 'https://discover.search.hereapi.com/v1/discover'
headers = {'Content-Type': 'application/json'}
origin_point = '-6.8918336,107.6103212'
latlong_origin = []
latlong_points = []

# Get lat long using HERE Map API
for i, data in df_points.iterrows():
  # your place name is defined below
  place_name = data.address
  my_params = {'at' : origin_point,
               'limit' : 1,
               'apikey' : apikey,
               'q' : place_name}
  r = requests.get(url, params=my_params, headers=headers)
  output = json.loads(r.text)
  latlong_dict = output['items'][0]['position']
  latlong = ', '.join(map(str, latlong_dict.values()))
  latlong_points += [latlong]

# Create dataframe
df_points['lat_lng'] = latlong_points
df_points['lat_lng'] = df_points.lat_lng.apply(ast.literal_eval)

Hình 5. DataFrame sau khi mã hóa địa lý

Lưu ý rằng bây giờ chúng ta có một trường gọi là lat_lng chứa vĩ độ và kinh độ của các điểm.

III. Tính khoảng cách di chuyển giữa các điểm

Tiếp theo là tính quãng đường di chuyển giữa các điểm. Điều quan trọng trong Bài toán người bán hàng du lịch vì tuyến đường ngắn nhất được tạo ra từ tổng khoảng cách được thực hiện từ mọi tuyến đường có thể. Thay vì sử dụng khoảng cách euclide (vẽ một đường giữa các điểm), chúng ta sẽ sử dụng một khoảng cách phù hợp hơn, đó là tạo một đường đi theo đường giữa các điểm. Đường dẫn này sẽ đại diện cho khoảng cách giữa các điểm.

Để làm điều này, chúng tôi sẽ sử dụng phương pháp short_path từ networkx. Nhưng trước đó ta nên tạo DataFrame điểm gốc-đích để dễ tính khoảng cách giữa các điểm. Khung dữ liệu này được tạo bằng cách thực hiện tất cả các kết hợp/hoán vị có thể có của điểm gốc và điểm đích.

# Create dataframe of origin-destination #

# Create variables
list_points_name = df_points['point_name']
# list_points_latlong = df_points['lat_long']
list_points_latlong = df_points['lat_lng']

# All points combinations
list_pair_name = [i for i in itertools.product(list_points_name, repeat=2)]
list_pair_latlong = [i for i in itertools.product(list_points_latlong, repeat=2)]
df_nodes = pd.DataFrame({'pair_name': list_pair_name, 'pair_latlong': list_pair_latlong})

# Source/Target
df_nodes['origin'] = df_nodes['pair_name'].apply(lambda t: t[0])
df_nodes['destination'] = df_nodes['pair_name'].apply(lambda t: t[1])
df_nodes['latlong_origin'] = df_nodes['pair_latlong'].apply(lambda t: t[0])
df_nodes['latlong_destination'] = df_nodes['pair_latlong'].apply(lambda t: t[1])
df_nodes.drop(['pair_name', 'pair_latlong'], axis =1, inplace = True)

Hình 6. Khung dữ liệu gốc và đích

Bây giờ, chúng ta có thể tính khoảng cách giữa các điểm bằng cách sử dụng networkx.

# Calculate distance from point to point using networkx #

# Location where you want to find your route
place     = 'Bandung, West Java, Indonesia'
# Find shortest route based on the mode of travel
mode      = 'drive'        # 'drive', 'bike', 'walk'
# Find shortest path based on distance or time
optimizer = 'length'        # 'length','time'
# Create graph from OSM within the boundaries of some geocodable place(s)
graph = ox.graph_from_place(place, network_type = mode)

# Create lists
list_route = []
list_route_length = []

# Determining distance and route
for i in range(len(df_nodes)):
  # find the nearest node to the start location
  orig_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route = nx.shortest_path(graph,
                                    orig_node,
                                    dest_node,
                                    weight=optimizer)
  shortest_route_length = nx.shortest_path_length(graph, orig_node, dest_node, weight=optimizer)
  # append list
  list_route.append(shortest_route)
  list_route_length.append(shortest_route_length)

Hình 7. Khoảng cách giữa các điểm DataFrame

IV. Xác định lộ trình xe tốt nhất

Sau đó, chúng tôi có thể xác định lộ trình tốt nhất để giao bưu kiện cho tất cả khách hàng bằng Google OR-Tools . Đầu tiên, chúng ta phải xác định các chức năng để giúp chúng ta tìm ra con đường ngắn nhất. Nó đề cập đến trang này với một số sửa đổi.

def create_data_model(distance_matrix, num_vehicles, depot_order):
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = distance_matrix
    data['num_vehicles'] = num_vehicles
    data['depot'] = depot_order
    return data

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        route_distance = 0
        while not routing.IsEnd(index):
            plan_output += ' {} -> '.format(manager.IndexToNode(index))
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += '{}\n'.format(manager.IndexToNode(index))
        plan_output += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {} m'.format(max_route_distance))

def get_routes(solution, routing, manager):
  """Get vehicle routes from a solution and store them in an array."""
  # Get vehicle routes and store them in a two dimensional array whose
  # i,j entry is the jth location visited by vehicle i along its route.
  routes = []
  for route_nbr in range(routing.vehicles()):
    index = routing.Start(route_nbr)
    route = [manager.IndexToNode(index)]
    while not routing.IsEnd(index):
      index = solution.Value(routing.NextVar(index))
      route.append(manager.IndexToNode(index))
    routes.append(route)
  return routes

# Instantiate the data problem.
data = create_data_model(distance_matrix=distance_matrix, 
                         num_vehicles=1, 
                         depot_order=0)

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                        data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    50000,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if solution:
    print_solution(data, manager, routing, solution)
else:
    print('No solution found !')

Kho -> Địa chỉ 5 -> Địa chỉ 6 -> Địa chỉ 7 -> Địa chỉ 4 -> Địa chỉ 3 -> Địa chỉ 2 -> Địa chỉ 1 -> Kho

Tuyến đường ngắn nhất này sẽ mất khoảng 7,44 km.

V. Tạo một con đường cho con đường hiệu quả nhất

Trực quan hóa dữ liệu là một trong những cách tốt nhất để hiểu trường hợp này dễ dàng hơn. Do đó, trong bước cuối cùng này, chúng tôi sẽ thực hiện trực quan hóa dữ liệu không gian để mô tả tuyến đường tốt nhất. Chúng ta nên tạo một DataFrame mới chỉ bao gồm tuyến đường tốt nhất, sau đó tạo đường dẫn.

# Create path for the most effective route #

# Create DataFrame of route order
df_nodes_best = pd.DataFrame({'origin' : route_name[:-1], 
                              'destination': route_name[1:]})
df_nodes_best = df_nodes_best.merge(df_nodes, on=['origin', 'destination'], how='inner')
df_nodes_best["route_order"] = [f"Route {i}" for i in range(1, len(df_nodes_best)+1)]
df_nodes_best

# Create lists
list_route_best = []
list_route_length_best = []

# Determining distance and route
for i in range(len(df_nodes_best)):
  # find the nearest node to the start location
  orig_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route_best = nx.shortest_path(graph,
                                    orig_node_best,
                                    dest_node_best,
                                    weight=optimizer)
  shortest_route_length_best = nx.shortest_path_length(graph, orig_node_best, dest_node_best, weight=optimizer)
  # append list
  list_route_best.append(shortest_route_best)
  list_route_length_best.append(shortest_route_length_best)

# Store best route distance in a list
distance_result_best = list_route_length_best.copy()

# Convert nodes code into lat long
all_list_nodes_latlong = []

for i in range(len(list_route_best)):
  list_nodes_latlong = []
  for j in range(len(list_route_best[i])):
    tuple_nodes_latlong = (graph.nodes[list_route_best[i][j]]['y'], graph.nodes[list_route_best[i][j]]['x'])
    list_nodes_latlong.append(tuple_nodes_latlong)
  all_list_nodes_latlong.append(list_nodes_latlong)

# Load map
my_map = folium.Map(location=[-6.897097, 107.621903],
                    zoom_start=15,
                    tiles='cartodbpositron')

# Plot route polyline
for i in range(len(all_list_nodes_latlong)):
  folium.PolyLine(all_list_nodes_latlong[i],
                  tooltip=f"{df_nodes_best['route_order'].iloc[i].upper()}:\
                  {df_nodes_best['origin'].iloc[i]} to {df_nodes_best['destination'].iloc[i]}\
                  - Distance: {round(distance_result_best[i]/1000, 2)} km",
                  # color=random_color(),
                  weight=5).add_to(my_map)

# Plot points
for i in range(len(df_points)):
  if i != 0:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i]).add_to(my_map)
  else:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i],
                  icon = folium.Icon(color='crimson')).add_to(my_map) # mark depot with red symbology

print(f'Total distance: {round(sum(distance_result_best)/1000, 2)} km')
my_map

      
                
                    
                    
       Figure 8. The shortest route

Giải pháp có thể giúp chúng tôi tìm ra các tuyến đường tốt nhất để giao tất cả các bưu kiện cho khách hàng. Quãng đường di chuyển ngắn nhất là 7,44 km với lộ trình như sau: