การแก้ปัญหาพนักงานขายเดินทาง

Nov 29 2022

เพิ่มประสิทธิภาพเส้นทางในการจัดส่งพัสดุโดยใช้ python เพื่อประหยัดค่าใช้จ่ายในการจัดส่ง (กรณีศึกษา: การจัดส่งพัสดุในบันดุง อินโดนีเซียด้วยข้อมูลอย่างง่าย) Travelling Salesman Problem หรือ TSP เป็นปัญหาการเพิ่มประสิทธิภาพแบบผสมผสานที่พยายามตอบคำถาม "กำหนดรายชื่อเมืองและ ระยะทางระหว่างเมืองแต่ละคู่ เส้นทางที่สั้นที่สุดที่เป็นไปได้ซึ่งไปแต่ละเมืองเพียงครั้งเดียวและกลับมายังเมืองต้นทางคือเท่าใด” ด้วยวิธีง่ายๆ TSP ได้รับมอบหมายให้ค้นหาเส้นทางที่สั้นที่สุดระหว่างชุดของจุดที่ต้องไป

เพิ่มประสิทธิภาพเส้นทางในการจัดส่งพัสดุโดยใช้ python เพื่อประหยัดต้นทุนการจัดส่ง (กรณีศึกษา: การจัดส่งพัสดุในบันดุง อินโดนีเซียด้วยข้อมูลอย่างง่าย)

ภาพถ่ายโดย José Martín Ramírez Carrasco บน Unsplash

Travelling Salesman Problem หรือ TSP เป็นปัญหาการเพิ่มประสิทธิภาพแบบผสมผสานที่พยายามตอบคำถาม "จากรายชื่อเมืองและระยะทางระหว่างเมืองแต่ละคู่ เส้นทางที่สั้นที่สุดที่เป็นไปได้ในการไปแต่ละเมืองเพียงครั้งเดียวและกลับไปยังเมืองต้นทางคือเส้นทางใด ". ด้วยวิธีง่ายๆ TSP ได้รับมอบหมายให้ค้นหาเส้นทางที่สั้นที่สุดระหว่างชุดของจุดที่ต้องไป มันกลายเป็นปัญหาจริงในห่วงโซ่อุปทานและอุตสาหกรรมลอจิสติกส์ในขณะที่พวกเขาพุ่งสูงขึ้นหลังจากอีคอมเมิร์ซเพิ่มขึ้น

เหตุใด TSP จึงมีความสำคัญ โดยพื้นฐานแล้วจะช่วยให้บริษัทได้รับผลกำไรมากขึ้นโดยประหยัดเวลาและทรัพยากร ในอุตสาหกรรมลอจิสติกส์ วิธีหนึ่งในการสร้างกำไรให้มากขึ้นคือประสิทธิภาพในด้านต้นทุนและเวลาในการจัดส่ง มีหลายวิธีในการบรรลุเป้าหมายนั้น หนึ่งในนั้นคือการแก้ปัญหา Travelling Salesman Problem (TSP) ซึ่งคุณพยายามหาเส้นทางที่มีประสิทธิภาพที่สุดในการเดินทาง ยิ่งแก้ไขได้มีประสิทธิภาพมากขึ้น เวลาก็น้อยลงใน การขับขี่ประหยัดเชื้อเพลิงมากขึ้น ใช้เวลาน้อยลงและยิ่งมีการจัดส่งพัสดุมากขึ้น ด้วยเหตุนี้ งบดุลของกิจกรรมทางธุรกิจที่มีการจัดส่งจะได้รับประโยชน์สองเท่า

ดังนั้น ฉันจึงพยายามสร้างตัวอย่างปัญหาพนักงานขายเดินทางนี้สำหรับผู้ให้บริการจัดส่งพัสดุในบันดุงเพื่อลดต้นทุนการจัดส่ง

หมายเหตุ : เนื่องจากเป็นการสาธิตอย่างง่าย ข้อมูลที่ใช้เป็นเพียง 8 จุดจำลองการจัดส่ง และข้อมูลเป็นข้อมูลที่สร้างขึ้นแบบสุ่ม

สถานการณ์

คุณเป็นผู้จัดการในศูนย์บริการจัดส่งพัสดุในบันดุง คุณควรจัดส่งพัสดุให้กับลูกค้าบางส่วนจากคลังของคุณด้วยรถ 1 คัน การกระจายของจุดจัดส่งและคลังสามารถดูได้ด้านล่าง (รูปที่ 1)

รูปที่ 1 การกระจายเชิงพื้นที่ของจุดจัดส่ง

**อย่างไรก็ตาม คุณสามารถปรับจำนวนรถและจำนวนจุดจัดส่งได้ตามต้องการโดยแก้ไขซอร์สโค้ดด้านล่าง

วัตถุประสงค์

ค้นหาเส้นทางที่ดีที่สุดในการจัดส่งพัสดุทั้งหมดให้กับลูกค้า

เพื่อติดตามว่าโมเดลหรือโซลูชันที่เราพยายามนำไปใช้นั้นดีเพียงใด จะเป็นการดีกว่าหากกำหนดเมตริกทางธุรกิจ เนื่องจากไม่มีข้อมูลของกรณีที่เกี่ยวข้อง ฉันจะพูดถึงศักยภาพโดยไม่ได้วัดว่าโซลูชันนั้นดีเพียงใด เมตริกทางธุรกิจที่เป็นไปได้เหล่านี้คือ:

ค่าจัดส่ง
ใช้เวลา
อัตราการส่งมอบตรงเวลา
คะแนนความพึงพอใจของลูกค้า (คะแนน CSAT)

การใช้Google OR-Toolsเส้นทางที่ดีที่สุดสำหรับรถหนึ่งคันคือ:

คลัง -> ที่อยู่ 5 -> ที่อยู่ 6 -> ที่อยู่ 7 -> ที่อยู่ 4 -> ที่อยู่ 3 -> ที่อยู่ 2 -> ที่อยู่ 1 -> คลัง

ระยะทางของเส้นทาง : 7.44กม

รูปที่ 2 ภาพเคลื่อนไหวเส้นทางที่สั้นที่สุด

ขั้นตอนทางเทคนิค

รูปที่ 3. Flowchart ของการประมวลผลใน Python

รหัสเต็มมีให้ที่นี่

I. นำเข้าไลบรารีและอ่านข้อมูล

ก่อนอื่น เราต้องนำเข้าไลบรารีไปยัง Google Colab เรากำลังจะใช้ห้องสมุดบางแห่ง

numpy และ pandas : สำหรับการดำเนินการเชิงตัวเลขและการจัดการข้อมูล
itertools : เพื่อสร้างตัววนซ้ำสำหรับการวนซ้ำอย่างมีประสิทธิภาพ
ast : เพื่อประมวลผลแผนผังของไวยากรณ์ไวยากรณ์นามธรรมของ Python
คำขอ : เพื่อทำการร้องขอ HTTP
json : เพื่อทำงานกับข้อมูล JSON
networkx :สำหรับการสร้าง จัดการ และศึกษาโครงสร้าง พลวัต และหน้าที่ของเครือข่ายที่ซับซ้อน
osmnx : เพื่อดาวน์โหลดข้อมูลเชิงพื้นที่จาก OpenStreetMap และจำลอง สร้างโครงการ แสดงภาพ และวิเคราะห์เครือข่ายถนนในโลกแห่งความเป็นจริงและเรขาคณิตเชิงพื้นที่อื่นๆ
folium : เพื่อแสดงภาพข้อมูลที่ถูกจัดการใน Python บนแผนที่แผ่นพับแบบโต้ตอบ
ortools : เพื่อแก้ปัญหาการปรับให้เหมาะสมแบบผสมผสาน

# 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')

รูปที่ 4 ชุดข้อมูลจุดส่งมอบ

ครั้งที่สอง พิกัดทางภูมิศาสตร์

Geocoding คือกระบวนการแปลงคำอธิบายของสถานที่ เช่น คู่ของพิกัด ที่อยู่ หรือชื่อสถานที่ ให้เป็นตำแหน่งบนพื้นผิวโลก โดยสังเขป เรากำลังพยายามดึงข้อมูลละติจูดและลองจิจูดจากที่อยู่ของชุดข้อมูล ละติจูดและลองจิจูดนี้จะใช้ในภายหลังเพื่อคำนวณระยะการเดินทางระหว่างจุดต่างๆ และกำหนดเส้นทางการจัดส่งที่ดีที่สุด

ฉันใช้ HERE API สำหรับ Geocoding เนื่องจากค่อนข้างแม่นยำและใช้งานได้ฟรี (จำกัดการโทร) คุณสามารถอ่านบทความนี้เพื่อดูรายละเอียดกระบวนการนี้ได้

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

รูปที่ 5 DataFrame หลังจาก geocoding

ขอให้สังเกตว่าตอนนี้เรามีฟิลด์ชื่อlat_lngซึ่งมีละติจูดและลองจิจูดของจุดต่างๆ

สาม. คำนวณระยะทางการเดินทางระหว่างจุด

ต่อไปคือการคำนวณระยะการเดินทางระหว่างจุด เป็นสิ่งสำคัญในโจทย์ Travelling Salesman เนื่องจากเส้นทางที่สั้นที่สุดถูกสร้างขึ้นจากระยะทางทั้งหมดจากทุกเส้นทางที่เป็นไปได้ แทนที่จะใช้ระยะทางแบบยุคลิด (การลากเส้นระหว่างจุด) เราจะใช้ระยะทางที่เกี่ยวข้องกันมากขึ้น ซึ่งเป็นการสร้างเส้นทางตามถนนระหว่างจุดต่างๆ เส้นทางนี้จะแสดงระยะทางระหว่างจุด

ในการทำเช่นนี้ เราจะใช้ วิธี shortest_pathจาก networkx แต่ก่อนหน้านั้น เราควรสร้าง DataFrame ต้นทาง-ปลายทาง เพื่อให้ง่ายต่อการคำนวณระยะห่างระหว่างจุด DataFrame นี้สร้างขึ้นโดยการผสมผสาน/การเรียงสับเปลี่ยนของจุดต้นทางและปลายทางที่เป็นไปได้ทั้งหมด

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

รูปที่ 6 DataFrame ต้นทางและปลายทาง

ตอนนี้ เราสามารถคำนวณระยะทางระหว่างจุดโดยใช้ 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)

รูปที่ 7 ระยะห่างระหว่างจุด DataFrame

IV. กำหนดเส้นทางยานพาหนะที่ดีที่สุด

จากนั้น เราสามารถกำหนดเส้นทางที่ดีที่สุดในการจัดส่งพัสดุให้กับลูกค้าทั้งหมดโดยใช้Google OR-Tools ขั้นแรก เราต้องกำหนดฟังก์ชันเพื่อช่วยเราค้นหาเส้นทางที่สั้นที่สุด มันอ้างถึงหน้านี้ด้วยการแก้ไขบางอย่าง

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 !')

เส้นทางที่สั้นที่สุดนี้จะใช้ระยะทางประมาณ7.44กม.

V. สร้างเส้นทางสำหรับเส้นทางที่มีประสิทธิภาพสูงสุด

การแสดงข้อมูลเป็นภาพเป็นวิธีที่ดีที่สุดวิธีหนึ่งในการทำให้เข้าใจกรณีนี้ได้ง่ายขึ้น ดังนั้น ในขั้นตอนสุดท้ายนี้ เราจะสร้างการแสดงข้อมูลเชิงพื้นที่เพื่อแสดงเส้นทางที่ดีที่สุด เราควรสร้าง DataFrame ใหม่ที่มีเฉพาะเส้นทางที่ดีที่สุด แล้วจึงสร้างเส้นทาง

# 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

โซลูชันสามารถช่วยเราค้นหาเส้นทางที่ดีที่สุดในการจัดส่งพัสดุทั้งหมดถึงมือลูกค้า ระยะทางสั้นที่สุดในการเดินทาง7.44 กม.โดยมีเส้นทางดังนี้

ผลกระทบทางธุรกิจที่อาจเกิดขึ้นหรือผลประโยชน์จากโครงการนี้คือ: