我正在尝试解决一个容量路由问题,其中我有一组需要不同数量和不同类型项目的节点。
此外,我想允许节点删除,因为具有一种类型项目的所有节点仍然可能超过车辆容量,因此无法解决。
然而,最终所有节点都应该得到服务,因此我使用迭代方法,将每种项目类型视为单独的路由问题。
但我想知道是否可以使用分离或类似的东西来解决“全局”路由问题。感谢任何关于这是否可能的帮助。
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项:车辆I服务于节点1
编辑我调整了我的方法以适应@mizux答案。代码下方:
EDIT2修复了第一个循环中的需求回调函数仍然引用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)
>
应在增加相关维度的每个位置创建两个容量维度,每种类型一个。
您可以为每种项目类型复制您的车辆,即:
注意:您可以复制它以允许多次旅行
您可以创建一个“门”节点以只允许一种车辆配置。例如,只允许v0或v1进行一些访问
v0_start = routing.Start(0)
v0_end = routing.End(0)
v1_start = routing.Start(1)
v1_end = routing.End(1)
gate_index = manager.NodeToIndex(gate_index)
routing.NextVar(v0_start).setValues[gate_index, v0_end]
routing.NextVar(v1_start).setValues[gate_index, v1_end]
由于节点只能访问一次,v0和v1中的一辆车可以通过门节点,而另一辆车则别无选择,只能前往结束节点,即在后期处理分配时可以删除的空路线。
如果车辆II比车辆I等便宜,您还可以将车辆固定成本添加到激励解算器中,以使用车辆II。。。
将每个位置添加到析取,以便解算器可以在需要时放置它们
location_index = manager.NodeToIndex(location_id)
routing.AddDisjunction(
[location_index], # locations
penalty,
max_cardinality=1 # you can omit it since it is already 1 by default
)
or-tools 是 Google 的优化搜索工具。 Google 优化工具包括: 约束编程解决方案 为线性规划和混合整数规划解决方案提供简单统一的接口,包括 CBC, CLP, GLOP, GLPK, Gurobi, SCIP, 和 Sulum。 背包算法 图算法 (最短路径,线性和分配,最小费用流,最大流) 主要特性 开源免费 持续维护,改进和开发 Alive 详细的文档,提供 C++, Py
我的机器上安装了节点,一切正常。在2019年制作的一个在线课程中,讲师使用的是早期版本的npm(v5.5.1),出于后续原因,建议所有人与他一起使用相同的版本。所以我降级到v5。5.1但是现在我几乎所有的命令都会出现同样的错误(不兼容)。我在这里读了一些类似问题的解决方案,甚至尝试了额外的步骤,但问题仍然存在。我从系统中卸载了node,重新启动了系统并重新安装了node,但npm的版本仍然是v5。
问题内容: 我有一个节点和方式数据库。一种方式包含两个或更多节点。一些节点属于多种方式,因此被称为两种或多种方式之间的“联接”。 我试图找到所有以两种或两种以上方式连接的节点。所以我正在使用这个查询, way_nodes表包含每种方式的节点列表。 但是,在我的数据库上,它有9,021种方式和43,706个节点,这简直令人难以置信地缓慢,并且每秒只能给我20-30个节点。 最初,我尝试对节点使用次数
部署到AWS时,我遇到以下错误 你知道这将如何解决吗? 这将工作,如果我指定的引擎在package.json
优酷土豆路由宝L1固件下载 youku rom downloads rom版本 正式版硬件 公测版硬件 2.0.0629.54182 下载 下载 1.5.0507.51292 下载 1.5.0421.50378 下载 1.5.0417.50253 下载 下载 1.5.0327.49004 下载 1.5.0327.48994 下载 1.5.0320.48610 下载 1.5.0211.47252 下
本文向大家介绍请你说说react的路由的优缺点?相关面试题,主要包含被问及请你说说react的路由的优缺点?时的应答技巧和注意事项,需要的朋友参考一下 browser router 模式下客户端路由在和服务端路由在统一域名下,会存在冲突的问题。 SEO 现在问题应该不存在,可以主动调用搜索引擎的提交或者是google 的引擎会自动跑js