Memecahkan Masalah Traveling Salesman

Nov 29 2022

Mengoptimalkan rute pengiriman parsel menggunakan python untuk menghemat biaya pengiriman (Studi kasus: pengiriman parsel di Bandung, Indonesia dengan data sederhana) Traveling Salesman Problem atau TSP adalah masalah optimisasi kombinatorial yang mencoba menjawab pertanyaan “Diberikan daftar kota dan jarak antara setiap pasangan kota, berapakah rute terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal?”. Secara sederhana, TSP bertugas untuk mencari rute terpendek antara sekumpulan titik yang harus dikunjungi.

Mengoptimalkan rute pengiriman parsel menggunakan python untuk menghemat biaya pengiriman (Studi kasus: pengiriman parsel di Bandung, Indonesia dengan data sederhana)

Foto oleh José Martín Ramírez Carrasco di Unsplash

Traveling Salesman Problem atau TSP adalah masalah optimisasi kombinatorial yang mencoba menjawab pertanyaan “Diberikan daftar kota dan jarak antara setiap pasangan kota, apa rute terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal? ”. Secara sederhana, TSP bertugas untuk mencari rute terpendek antara sekumpulan titik yang harus dikunjungi. Ini menjadi masalah nyata dalam rantai pasokan dan industri logistik saat mereka meroket mengikuti kenaikan e-commerce.

Jadi, mengapa TSP penting? Intinya, ini membantu perusahaan untuk mendapatkan lebih banyak keuntungan dengan menghemat waktu dan sumber daya. Dalam industri logistik, salah satu cara untuk menghasilkan keuntungan lebih adalah dengan efisiensi biaya dan waktu pengiriman. Ada berbagai cara untuk mencapainya, salah satunya adalah dengan menyelesaikan Traveling Salesman Problem (TSP), di mana Anda mencoba mencari rute yang paling efisien untuk ditempuh di jalan raya. Semakin efisien diselesaikan, semakin sedikit waktu yang dihabiskan untuk mengemudi, semakin banyak bahan bakar yang dihemat, semakin sedikit jam yang dibutuhkan, dan bahkan semakin banyak paket yang dikirimkan . Akibatnya, neraca setiap aktivitas bisnis berbasis pengiriman akan mendapat keuntungan dua kali lipat.

Oleh karena itu saya mencoba membuat demo Traveling Salesman Problem ini untuk kurir perusahaan pengiriman parsel di Bandung untuk menekan biaya pengiriman .

Catatan : karena ini adalah demo sederhana, data yang digunakan hanya 8 poin dummy pengiriman dan data tersebut merupakan data yang dihasilkan secara acak.

Skenario

Anda adalah seorang manager di salah satu pusat jasa pengiriman parsel di Bandung. Anda harus mengirimkan paket ke beberapa pelanggan dari depot Anda dengan 1 kendaraan. Distribusi titik pengiriman dan depo dapat dilihat di bawah ini (Gambar 1).

Gambar 1. Distribusi spasial titik pengiriman

**Bagaimanapun, Anda dapat menyesuaikan jumlah kendaraan dan jumlah titik pengiriman sesuai keinginan dengan mengedit kode sumber di bawah ini

Tujuan

Temukan rute terbaik untuk mengirimkan semua paket ke pelanggan.

Untuk melacak seberapa bagus model atau solusi yang kami coba terapkan, lebih baik menentukan metrik bisnis. Karena data kasus terkait tidak ada, saya hanya akan menyebutkan potensi tanpa mengukur seberapa bagus solusinya. Metrik bisnis potensial tersebut adalah:

Ongkos kirim
Waktu yang dihabiskan
Tingkat pengiriman tepat waktu
Skor Kepuasan Pelanggan (skor CSAT)

Memanfaatkan Google OR-Tools , rute terbaik dengan satu kendaraan adalah:

Depot -> Alamat 5 -> Alamat 6 -> Alamat 7 -> Alamat 4 -> Alamat 3 -> Alamat 2 -> Alamat 1 -> Depot

Jarak rute: 7,44 km

Gambar 2. Animasi rute terpendek

Langkah Teknis

Gambar 3. Flowchart pemrosesan dengan Python

Kode lengkap disediakan di sini .

I. Impor Pustaka dan Baca Data

Sebelumnya, kita harus mengimpor perpustakaan ke Google Colab. Kami akan menggunakan beberapa perpustakaan.

numpy and pandas : untuk operasi numerik dan manipulasi data
itertools : untuk membuat iterator untuk perulangan yang efisien
ast : untuk memproses pohon tata bahasa sintaksis abstrak Python
permintaan : untuk membuat permintaan HTTP
json : untuk bekerja dengan data JSON
networkx : untuk pembuatan, manipulasi, dan studi tentang struktur, dinamika, dan fungsi jaringan yang kompleks
osmnx : untuk mengunduh data geospasial dari OpenStreetMap dan memodelkan, memproyeksikan, memvisualisasikan, dan menganalisis jaringan jalan dunia nyata dan geometri geospasial lainnya
folium : untuk memvisualisasikan data yang telah dimanipulasi dengan Python pada peta selebaran interaktif
ortools : untuk memecahkan masalah optimisasi kombinatorial

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

Gambar 4. Dataset titik pengiriman

II. Geocoding

Geocoding adalah proses mengubah deskripsi lokasi — seperti sepasang koordinat, alamat, atau nama tempat — ke lokasi di permukaan bumi. Singkatnya, kami mencoba mengambil lintang dan bujur dari alamat kumpulan data. Lintang dan bujur ini nantinya akan digunakan untuk menghitung jarak tempuh antar titik dan menentukan rute pengiriman yang terbaik.

Saya menggunakan HERE API untuk Geocoding mengingat cukup akurat dan gratis untuk digunakan (dengan panggilan terbatas). Anda dapat membaca artikel ini untuk detail proses ini.

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

Gambar 5. DataFrame setelah geocoding

Perhatikan bahwa sekarang kita memiliki bidang bernama lat_lng yang berisi lintang dan bujur dari titik-titik tersebut.

AKU AKU AKU. Hitung Jarak Perjalanan Antar Titik

Selanjutnya adalah menghitung jarak tempuh antar titik. Hal ini penting dalam Traveling Salesman Problem karena rute terpendek dihasilkan dari total jarak yang diambil dari setiap kemungkinan rute. Alih-alih menggunakan jarak euclidean (menggambar garis antar titik), kita akan menggunakan jarak yang lebih relevan yaitu membuat jalur mengikuti jalan antar titik. Jalur ini akan mewakili jarak antar titik.

Untuk melakukan ini, kami akan menggunakan metode shortest_path dari networkx. Namun sebelum itu, kita harus membuat Origin-destination DataFrame untuk memudahkan menghitung jarak antar titik. DataFrame ini dibuat dengan membuat semua kemungkinan kombinasi/permutasi dari titik asal dan tujuan.

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

Gambar 6. DataFrame Asal dan Tujuan

Sekarang, kita dapat menghitung jarak antar titik menggunakan 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)

Gambar 7. Jarak antar titik DataFrame

IV. Tentukan Rute Kendaraan Terbaik

Kemudian, kami dapat menentukan rute terbaik untuk mengirimkan parsel ke semua pelanggan menggunakan Google OR-Tools . Pertama, kita harus mendefinisikan fungsi untuk membantu kita menemukan rute terpendek. Itu merujuk ke halaman ini dengan beberapa modifikasi.

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

Depot -> Alamat 5 -> Alamat 6 -> Alamat 7 -> Alamat 4 -> Alamat 3 -> Alamat 2 -> Alamat 1 -> Depot

Rute terpendek ini akan menempuh jarak sekitar 7,44 km.

V. Buat Jalur untuk Rute Paling Efektif

Visualisasi data adalah salah satu cara terbaik untuk mempermudah memahami kasus ini. Oleh karena itu, pada langkah terakhir ini kita akan membuat visualisasi data spasial untuk menggambarkan rute terbaik. Kita harus membuat DataFrame baru yang menyertakan rute terbaik saja, lalu buat jalurnya.

# 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

Solusinya dapat membantu kami menemukan rute terbaik untuk mengirimkan semua paket ke pelanggan. Jarak tempuh terpendek adalah 7,44 km dengan rute sebagai berikut: