Какая самая быстрая структура данных для хранения эвристического решения (списка / матрицы смежности) в python? - PullRequest
Новая
       33

Какая самая быстрая структура данных для хранения эвристического решения (списка / матрицы смежности) в python?

0 голосов
/ 02 июля 2019

Я разрабатываю эвристику для вариации проблемы маршрутизации транспортных средств (VRP) и хотел бы улучшить время выполнения вычислений.

В настоящее время решение хранится в виде словаря с идентификаторами транспортных средств в качестве ключей и списками, которые содержат идентификаторы клиентов в качестве значений.Последовательность идентификаторов клиентов представляет последовательность посещений.Основная проблема заключается в том, что решением манипулируют много раз (клиенты меняют позицию и / или транспортные средства), и мне приходится многократно повторять решение, чтобы оценить решение.

Пример решения может быть следующим: 

s = {}
s['v1'] = ['c1', 'c2', 'c3', 'c4']
s['v2'] = ['c5', 'c6']
s['v3'] = ['c7', 'c8', 'c9']

Я знаю, что стандартные словари и списки Python не самый быстрый вариант, и думаю, что в numpy или pandas есть лучшие варианты.Я наткнулся на следующую опцию, где dict преобразуется в dand pandas: 

df=pd.DataFrame.from_dict(d,orient='index').transpose()

Однако моделирование последовательности клиентов в столбце df не сохраняет гибкость списка.

У вас есть предложение, которое сохраняет существующую структуру?

В качестве альтернативы я думал об изменении structore на трехмерную двоичную матрицу, которая идентифицирует последовательность клиентов и распределение транспортных средств.

Дополнительная информация об операциях, выполненных с помощью «решения»:

С общей целью улучшить решение за несколько итераций, один или несколько клиентов удаляются и вставляются из / в маршруты транспортных средств.,В настоящее время это делается с помощью операторов списка python pop (), remove (), insert ().Чтобы принять решение о том, какие клиенты перемещать или рассчитать стоимость решения в конце, эвристика использует функциюvalu () (следующая версия представляет собой упрощенный пример, где рассчитывается время прибытия для каждого клиента и назначается штраф).если автомобиль прибывает с опозданием): 

def evaluate(s, vehicleData, customerData):

  # set objective value == 0:
  obj_val = 0

  # Iterate over all vehicles
  for vehicleId, customerList in s.items():

  # set the current time equal to the start time of the vehicle:
  t_current = vehicleData[vehicleId]['twStart']

  # Iterate over the customers in each vehicle route:
  for customer in customerList:
     # If a vehicle arrives at customer location after the visitation time is over, add a penalty:
     if t_current > customerData[customer]['twEnd']:
        obj_val -= 100000

     # Set t_current == twStart[job] if vehicle is too early:
     if t_current < customerData[customer]['twStart']:
        t_current = customerData[customer]['twStart']

     # Add time per job (tpj) to t_current:
     t_current += customerData[customer]['tpj']

  return obj_val

vehicleData и customerData - это рамки данных pandas.

...