Я пытаюсь решить проблему емкостной маршрутизации, когда у меня есть набор узлов, для которых требуется разное количество и разные типы элементов.
Кроме того, я хочу разрешить отбрасывание узлов, потому что все узлы с одним типом элементов могут по-прежнему превышать вместимость транспортного средства и, следовательно, не приведет к решению.
Однако в конечном итоге все узлы должны быть обслужены, поэтому я использую итеративный подход, при котором я рассматривал каждый тип элемента как отдельную проблему маршрутизации.
Но мне было интересно, можно ли использовать дизъюнкции или что-то подобное для решения «глобальной» проблемы маршрутизации. Любая помощь в том, возможно ли это, приветствуется.
Example:
Node 1 - item A - demand 10
Node 2 - item A - demand 10
Node 3 - item A - demand 12
Node 4 - item B - demand 10
Node 5 - item B - demand 10
vehicle I - capacity 20
vehicle II - capacity 10
Мой подход:
Сначала решите для элемента A: транспортное средство, которое я обслуживаю, узлы 1 и 2, узел 3 отброшен, сохраните отброшенные узлы для более поздней итерации
Затем решите для элемента B: транспортное средство, которое я обслуживаю узлы 4 и 5, транспортное средство II простаивает Решить для оставшегося узла 3: машина I обслуживает узел 3
ИЗМЕНИТЬ Я скорректировал свой подход, чтобы он соответствовал ответу @mizux. Ниже кода:
РЕДАКТИРОВАТЬ2. Исправлена ошибка, из-за которой функция обратного вызова спроса из первых циклов по-прежнему ссылалась на переменную product_index и, таким образом, возвращала неправильное требование. Исправить с помощью functools.partial.
import functools
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
class CVRP():
def __init__(self, data):
# assert all(data['demands'] < max(data['vehicle_capacities'])) # if any demand exceeds cap no solution possible
self.data = data
self.vehicle_names_internal = [f'{i}:{j}' for j in data['products'] for i in data['vehicle_names']]
self.manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), len(self.vehicle_names_internal), data['depot'])
self.routing = pywrapcp.RoutingModel(self.manager)
transit_callback_id = self.routing.RegisterTransitCallback(self._dist_callback)
self.routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_id)
# set up dimension for each product type for vehicle capacity constraint
for product_index, product in enumerate(data['products']):
dem_product_callback = functools.partial(self._dem_callback_generic, product_index=product_index)
dem_callback_id = self.routing.RegisterUnaryTransitCallback(dem_product_callback)
vehicle_product_capacity = [0 for i in range(len(self.vehicle_names_internal))]
vehicle_product_capacity[product_index*data['num_vehicles']:product_index*data['num_vehicles']+data['num_vehicles']] = data['vehicle_capacities']
print(product_index, product)
print(self.vehicle_names_internal)
print(vehicle_product_capacity)
self.routing.AddDimensionWithVehicleCapacity(
dem_callback_id,
0,
vehicle_product_capacity,
True,
f'capacity_{product}',
)
# disjunction (allow node drops)
penalty = int(self.data['distance_matrix'].sum()+1) # penalty needs to be higher than total travel distance in order to only drop locations if not other feasible solution
for field_pos_idx_arr in self.data['disjunctions']:
self.routing.AddDisjunction([self.manager.NodeToIndex(i) for i in field_pos_idx_arr], penalty)
def _dist_callback(self, i, j):
return self.data['distance_matrix'][self.manager.IndexToNode(i)][self.manager.IndexToNode(j)]
def _dem_callback_generic(self, i, product_index):
node = self.manager.IndexToNode(i)
if node == self.data['depot']:
return 0
else:
return self.data['demands'][node, product_index]
def solve(self, verbose=False):
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC)
search_parameters.time_limit.FromSeconds(30)
self.solution = self.routing.SolveWithParameters(search_parameters)
