Genel python yazılım

Gezgin Satıcı Problemi(Google OR Tools & Python)

Nisan 6, 2022
Emre Özgöz

Merhabalar, bu makalede Gezgin Satıcı Problemini ele alacağım ve Google OR Tools yardımı ile ufak bir örnek anlatmaya çalışacağım.

İlk Olarak Gezgin Satıcı problemi nedir? Buna bir göz atalım.

Gezgin Satıcı Problemi(TSP) kişinin gideceği rotayı en kısa olacak şekilde gitmeyi optimize etme amacını taşır.

Aklımızda kalması amacıyla Wikipedia’nın yapmış olduğu örneğe bir göz atalım.

Seyyar satıcı problemi şu şekilde tanımlanabilir:

  • Bir seyyar satıcı var;
  • Bu satıcı, mallarını şehirde satmak istiyor;
  • Öte yandan, mantıklı bir şekilde, bu satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir şehre maksimum bir kere uğrayarak turlamak istiyor.

Problemin amacı, satıcıya bu en kısa yolu sunabilmektir.

Problemimizi anladıysak Google OR Tools ile çözme kısmına geçelim;

Örneğimizi ben de bir seyyar satıcı üzerinden anlatmak istiyorum.

Seyyar satıcımız New York şehrinden başlamak üzere aşağıdaki şehirleri rotası en kısa olacak şekilde gezip satış yapmak istiyor.(Aşağıdaki şehirlerin sırası yoktur, sadece New York başlangıç olduğu için sıfır olarak yazılmıştır. Diğer şehirler rastgeledir.)

0. New York – 1. Los Angeles – 2. Chicago – 3. Minneapolis – 4. Denver – 5. Dallas – 6. Seattle – 7. Boston – 8. San Francisco – 9. St. Louis – 10. Houston – 11. Phoenix – 12. Salt Lake City

Ben bu örneği Python dili üzerinden gerçekleştireceğim. Dilerseniz kaynakça kısmında yer alan linke giderek, daha fazla dil seçeneği görebilirsiniz.(C#, Java, C++).

İlk olarak bir “Import” işlemleri ile işe başlıyoruz.

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

Daha sonra “Modelimizi” oluşturuyoruz.

def create_data_model():
    data = {}
#Matris uzaklıkları tamamen rastgeledir.
    data['distance_matrix'] = [
        [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
        [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
        [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
        [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
        [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
        [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
        [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
        [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
        [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
        [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
        [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
        [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
        [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],
    ] 
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

Burada create_data_model adı isminde bir adet Model oluşturuyoruz ve içerisine “data” isminde bir adet dict veri tipinde bir değişken tanımlıyoruz.

Daha sonrasında Belirlemiş olduğumuz lokasyonlar arasındaki uzaklığı belirten bir “distance_matrix” oluşturup, her noktanın birbirine olan uzaklığını yazıyoruz.

datamızın “num_vehicles” kısmına kaç adet aracımızın olduğunu yazıyoruz.(Bizim bir adet seyyar satıcımız olduğu için 1 yazdık.)

Son olarak depomuzun, yani başlangıç yerimizin hangi lokasyon olduğunu belirten (Yukarıda New York’a 0 demiştik) sayımızı giriyoruz.

return komutu ile bu Modelimizi döndürüyoruz.

Modeli oluşturduktan sonra “Routing Model” oluşturmamız gerekiyor. Bunu yapma amacımız ise “Modelimizi” oluştururken “data” isminde bir adet “dict” tipinde bir property tanımlamıştık. Routing model oluştururkenki amacımız, burada vermiş olduğumuz birden fazla matrisi eşlemek diyebilirizi.(Detaylı bilgi için Pythonda dictionary tipine bakmanızı öneririm)

data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                       data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

RoutingIndexManager’ımıza girenler:

  • Konum sayısı(Depo dahil)
  • Araç Sayısı
  • Depoya karşılık gelen nokta(New York için 0 demiştik)

Daha sonrasında bir CallBack metodu oluşturarak ilk başta numaralandırdığımız lokasyonlara mesafe matrislerini veriyoruz

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]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

Daha iyi görebilmek için kodu Debug modda çalıştırdığımda aşağıdaki gibi her bir noktanın diğer her noktayla eşleştirildiğini görebiliyorsunuz.

Her bir mesafe matrisini birbiri ile eşleyerek en ideal çözümü buluyor.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

“SetArcCostEvaluatorOfAllVehicles” metodunu kullanarak yapmış olduğumuz seyahatin bize olan maliyetini hesaplatabiliyoruz.

Daha sonrasında bu uzaklıkların hangi şekilde çözülmesi gerektiğini belirten kodu yazmamız gerekiyor.

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

Burada PATH_CHEAPEST_ARC özelliği ile vermiş olduğumuz matrislerin çözüm stratejisini belirlemiş oluyoruz. Bu özellik ile depo dışında diğer yerleri en az mesafeleri birbirine ekleyecek şekilde çözümlemiş oluyor. (Diğer özellikleri Kaynakça kısmında bulabilirsiniz.)

def print_solution(manager, routing, solution):
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route for vehicle 0:\n'
    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, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Route distance: {}miles\n'.format(route_distance)

“print_solution” metodu ile hesaplatmış olduğumuz mesafeleri ekrana yazdırıyoruz.

Çıktı şu şekilde

Yukarıdaki şekilde bir rota izleyerek seyahat etmesi mesafe açısından en kısa olacaktır. Tabi ki biz burada trafik, yol şartları vb. gibi durumları ele almadık. Sadece mesafeleri baz alarak böyle bir sonuç elde etmiş olduk. Kısıtları arttırarak çok daha gerçekçi bir sonuca varabilirsiniz.

Okuduğunuz için teşekkürler.

KAYNAKÇA

https://developers.google.com/optimization/routing/tsp

https://developers.google.com/optimization/routing/routing_options#first_sol_options

https://en.wikipedia.org/wiki/Travelling_salesman_problem

https://www.w3schools.com/python/python_datatypes.asp

https://dergipark.org.tr/tr/download/article-file/98220