- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
我正在处理由 Google OR Tools 共享的示例代码。此示例适用于具有时间窗的容量化车辆路径问题。
当我运行整个共享程序时 here .它运行良好并提供如 https://developers.google.com/optimization/routing/cvrptw 所示的输出.
但是,当我将 self._num_vehicles 从 4 更改为 3 时。它挂起并且不提供输出。
我知道这 3 辆车无法承受全部负载,这就是它卡住的原因。但它是否可能为我提供 3 辆车的最佳路线,并留下车辆无法满足的其余需求。
你能在这里提出修复建议吗?
代码示例:
"""Capacitated Vehicle Routing Problem with Time Windows (CVRPTW).
"""
from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
###########################
# Problem Data Definition #
###########################
class Vehicle():
"""Stores the property of a vehicle"""
def __init__(self):
"""Initializes the vehicle properties"""
self._capacity = 15
# Travel speed: 5km/h to convert in m/min
self._speed = 5 * 60 / 3.6
@property
def capacity(self):
"""Gets vehicle capacity"""
return self._capacity
@property
def speed(self):
"""Gets the average travel speed of a vehicle"""
return self._speed
class CityBlock():
"""City block definition"""
@property
def width(self):
"""Gets Block size West to East"""
return 228/2
@property
def height(self):
"""Gets Block size North to South"""
return 80
class DataProblem():
"""Stores the data for the problem"""
def __init__(self):
"""Initializes the data for the problem"""
self._vehicle = Vehicle()
self._num_vehicles = 4
# Locations in block unit
locations = \
[(4, 4), # depot
(2, 0), (8, 0), # row 0
(0, 1), (1, 1),
(5, 2), (7, 2),
(3, 3), (6, 3),
(5, 5), (8, 5),
(1, 6), (2, 6),
(3, 7), (6, 7),
(0, 8), (7, 8)]
# locations in meters using the city block dimension
city_block = CityBlock()
self._locations = [(
loc[0]*city_block.width,
loc[1]*city_block.height) for loc in locations]
self._depot = 0
self._demands = \
[0, # depot
1, 1, # 1, 2
2, 4, # 3, 4
2, 4, # 5, 6
8, 8, # 7, 8
1, 2, # 9,10
1, 2, # 11,12
4, 4, # 13, 14
8, 8] # 15, 16
self._time_windows = \
[(0, 0),
(75, 85), (75, 85), # 1, 2
(60, 70), (45, 55), # 3, 4
(0, 8), (50, 60), # 5, 6
(0, 10), (10, 20), # 7, 8
(0, 10), (75, 85), # 9, 10
(85, 95), (5, 15), # 11, 12
(15, 25), (10, 20), # 13, 14
(45, 55), (30, 40)] # 15, 16
@property
def vehicle(self):
"""Gets a vehicle"""
return self._vehicle
@property
def num_vehicles(self):
"""Gets number of vehicles"""
return self._num_vehicles
@property
def locations(self):
"""Gets locations"""
return self._locations
@property
def num_locations(self):
"""Gets number of locations"""
return len(self.locations)
@property
def depot(self):
"""Gets depot location index"""
return self._depot
@property
def demands(self):
"""Gets demands at each location"""
return self._demands
@property
def time_per_demand_unit(self):
"""Gets the time (in min) to load a demand"""
return 5 # 5 minutes/unit
@property
def time_windows(self):
"""Gets (start time, end time) for each locations"""
return self._time_windows
#######################
# Problem Constraints #
#######################
def manhattan_distance(position_1, position_2):
"""Computes the Manhattan distance between two points"""
return (abs(position_1[0] - position_2[0]) +
abs(position_1[1] - position_2[1]))
class CreateDistanceEvaluator(object):
"""Creates callback to return distance between points."""
def __init__(self, data):
"""Initializes the distance matrix."""
self._distances = {}
# precompute distance between location to have distance callback in O(1)
for from_node in xrange(data.num_locations):
self._distances[from_node] = {}
for to_node in xrange(data.num_locations):
if from_node == to_node:
self._distances[from_node][to_node] = 0
else:
self._distances[from_node][to_node] = (
manhattan_distance(
data.locations[from_node],
data.locations[to_node]))
def distance_evaluator(self, from_node, to_node):
"""Returns the manhattan distance between the two nodes"""
return self._distances[from_node][to_node]
class CreateDemandEvaluator(object):
"""Creates callback to get demands at each location."""
def __init__(self, data):
"""Initializes the demand array."""
self._demands = data.demands
def demand_evaluator(self, from_node, to_node):
"""Returns the demand of the current node"""
del to_node
return self._demands[from_node]
def add_capacity_constraints(routing, data, demand_evaluator):
"""Adds capacity constraint"""
capacity = "Capacity"
routing.AddDimension(
demand_evaluator,
0, # null capacity slack
data.vehicle.capacity, # vehicle maximum capacity
True, # start cumul to zero
capacity)
class CreateTimeEvaluator(object):
"""Creates callback to get total times between locations."""
@staticmethod
def service_time(data, node):
"""Gets the service time for the specified location."""
return data.demands[node] * data.time_per_demand_unit
@staticmethod
def travel_time(data, from_node, to_node):
"""Gets the travel times between two locations."""
if from_node == to_node:
travel_time = 0
else:
travel_time = manhattan_distance(
data.locations[from_node],
data.locations[to_node]) / data.vehicle.speed
return travel_time
def __init__(self, data):
"""Initializes the total time matrix."""
self._total_time = {}
# precompute total time to have time callback in O(1)
for from_node in xrange(data.num_locations):
self._total_time[from_node] = {}
for to_node in xrange(data.num_locations):
if from_node == to_node:
self._total_time[from_node][to_node] = 0
else:
self._total_time[from_node][to_node] = int(
self.service_time(data, from_node) +
self.travel_time(data, from_node, to_node))
def time_evaluator(self, from_node, to_node):
"""Returns the total time between the two nodes"""
return self._total_time[from_node][to_node]
def add_time_window_constraints(routing, data, time_evaluator):
"""Add Global Span constraint"""
time = "Time"
horizon = 120
routing.AddDimension(
time_evaluator,
horizon, # allow waiting time
horizon, # maximum time per vehicle
False, # don't force start cumul to zero since we are giving TW to start nodes
time)
time_dimension = routing.GetDimensionOrDie(time)
for location_idx, time_window in enumerate(data.time_windows):
if location_idx == 0:
continue
index = routing.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
routing.AddToAssignment(time_dimension.SlackVar(index))
for vehicle_id in xrange(data.num_vehicles):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data.time_windows[0][0], data.time_windows[0][1])
routing.AddToAssignment(time_dimension.SlackVar(index))
###########
# Printer #
###########
class ConsolePrinter():
"""Print solution to console"""
def __init__(self, data, routing, assignment):
"""Initializes the printer"""
self._data = data
self._routing = routing
self._assignment = assignment
@property
def data(self):
"""Gets problem data"""
return self._data
@property
def routing(self):
"""Gets routing model"""
return self._routing
@property
def assignment(self):
"""Gets routing model"""
return self._assignment
def print(self):
"""Prints assignment on console"""
# Inspect solution.
capacity_dimension = self.routing.GetDimensionOrDie('Capacity')
time_dimension = self.routing.GetDimensionOrDie('Time')
total_dist = 0
total_time = 0
for vehicle_id in xrange(self.data.num_vehicles):
index = self.routing.Start(vehicle_id)
plan_output = 'Route for vehicle {0}:\n'.format(vehicle_id)
route_dist = 0
while not self.routing.IsEnd(index):
node_index = self.routing.IndexToNode(index)
next_node_index = self.routing.IndexToNode(
self.assignment.Value(self.routing.NextVar(index)))
route_dist += manhattan_distance(
self.data.locations[node_index],
self.data.locations[next_node_index])
load_var = capacity_dimension.CumulVar(index)
route_load = self.assignment.Value(load_var)
time_var = time_dimension.CumulVar(index)
time_min = self.assignment.Min(time_var)
time_max = self.assignment.Max(time_var)
slack_var = time_dimension.SlackVar(index)
slack_min = self.assignment.Min(slack_var)
slack_max = self.assignment.Max(slack_var)
plan_output += ' {0} Load({1}) Time({2},{3}) Slack({4},{5}) ->'.format(
node_index,
route_load,
time_min, time_max,
slack_min, slack_max)
index = self.assignment.Value(self.routing.NextVar(index))
node_index = self.routing.IndexToNode(index)
load_var = capacity_dimension.CumulVar(index)
route_load = self.assignment.Value(load_var)
time_var = time_dimension.CumulVar(index)
route_time = self.assignment.Value(time_var)
time_min = self.assignment.Min(time_var)
time_max = self.assignment.Max(time_var)
total_dist += route_dist
total_time += route_time
plan_output += ' {0} Load({1}) Time({2},{3})\n'.format(node_index, route_load, time_min, time_max)
plan_output += 'Distance of the route: {0}m\n'.format(route_dist)
plan_output += 'Load of the route: {0}\n'.format(route_load)
plan_output += 'Time of the route: {0}min\n'.format(route_time)
print(plan_output)
print('Total Distance of all routes: {0}m'.format(total_dist))
print('Total Time of all routes: {0}min'.format(total_time))
########
# Main #
########
def main():
"""Entry point of the program"""
# Instantiate the data problem.
data = DataProblem()
# Create Routing Model
routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot)
# Define weight of each edge
distance_evaluator = CreateDistanceEvaluator(data).distance_evaluator
routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
# Add Capacity constraint
demand_evaluator = CreateDemandEvaluator(data).demand_evaluator
add_capacity_constraints(routing, data, demand_evaluator)
# Add Time Window constraint
time_evaluator = CreateTimeEvaluator(data).time_evaluator
add_time_window_constraints(routing, data, time_evaluator)
# Setting first solution heuristic (cheapest addition).
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
printer = ConsolePrinter(data, routing, assignment)
printer.print()
if __name__ == '__main__':
main()
最佳答案
您必须将您的节点变成可选节点。
关于python - 时间窗口崩溃的容量化车辆路径问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53019804/
我在 iOS 上有一个使用 WebSQL 数据库的 PhoneGap 应用程序。在某些地方,我读到存储容量是 5MB,而在其他地方,我读到它是 50MB,有人可以帮我解决这个问题吗?我还计划在数据库中
我想弄清楚如何更新节点的 pod 容量。我使用文档中概述的 Vagrant/VM 环境进行了简单的集群设置。我尝试使用 kubectl 修补节点的 pod 容量,执行以下操作: 通过以下方式发送补丁所
我想创建一个函数,根据某人系统上的可用 RAM 大小来导入不同批处理的数据。但是如何找到 R 中的可用 RAM 量呢?我可以使用 memory.size() 但这只适用于 Windows。 最佳答案
目前,我正在努力将 Power BI 内容嵌入到我的 Web 应用程序中。我已经通过服务主体实现了它,并且它按预期工作。但是对于产品环境,是否必须为我的报告或工作区添加容量?是否可以在不增加生产环境容
我有一个 3 节点 coros kubernetes 集群启动并运行。 我想使用来自独立 NFS 服务器的 persitentvolumes(pv)。 nfs.yaml apiVersion: v1
我正在学习golang一段时间。我遇到了 channel 问题。 我有两个例子。它们看起来一样,但是其中1个给出了错误。 当我分配 channel 容量(转换为缓冲 channel )时,问题已解决,
我正在尝试创建一个子例程,将一个字符串插入另一个字符串。我想检查主机字符串是否有足够的容量来容纳所有字符,如果没有,则返回错误整数。这需要使用类似 sizeof 的东西,但可以使用指针调用。我的代码如
这个问题在这里已经有了答案: size vs capacity of a vector? (8 个答案) 关闭 7 年前。 在下面的程序中,我只是创建了一个空 vector ,然后将大小调整为 5
免责声明 1 - 我是编程新手免责声明 2 - 我搜索了又搜索,但找不到我正在寻找的帮助。 对于一个项目,我或多或少地以更精简的形式重写了 vector 类。我挂断的部分是编写 push_back 方
我对 BTree 的理解是: if root BTree size is 32, the level 1 have 1024 keys capacity the level 2 can sort 10
我有一个使用 ActionBar 的应用程序,我自己处理方向更改: android:configChanges="keyboard|keyboardHidden|orientation|screenS
如何将 hadoop DFS 的配置容量从默认的 50GB 增加到 100GB? 我目前的设置是在 centOS6 机器上运行的 hadoop 1.2.1,使用了 450GB 中的 120GB。已使用
我的问题是关于 slice 长度和容量。我在这里学习 Go:https://tour.golang.org/moretypes/11 . (我的问题被标记为可能与 this 重复;但是,事实并非如此。
现在尝试从教程中学习 Go,并且有一个非常基本的问题: func main() { a := make([]int, 5) // [0,0,0,0,0] len=5 cap=5 b :=
如何以以下格式获取有关数据库中所有表空间的信息。 TABLESPACE_NAME | FILE_NAME | ALLOCATED_MB | FREE_MB | CAPACITY | 有没有办法自
我想基于每个作业更改群集的减少插槽容量。也就是说, 最初,我为Tasktracker配置了8个reduce插槽,因此对于具有100个reduce任务的作业,将同时运行(8 * datanode数量)r
我正在运行单节点 Hadoop 部署。我知道我的应用程序需要多少数据,我可以设置(和重新设置)HDFS 使用的最大容量吗? 我已经尝试了以下方法,但似乎无法实现。 检查 hdfs-site.xml 和
我安装了 splunk 来监控和分析 hadoop 作业。我在其他节点的Jobtracker、forwarder和TA中安装splunk core和splunk hadoop app后,HDFS ca
vector::operator= 会改变 vector 容量吗?如果有,怎么做? vector的拷贝构造函数是否拷贝容量? 我查看了文档,但找不到具体答案。是否依赖于实现? 最佳答案 您可以保证:
将 SQL 数据库导出到存储时,我们的 DTU 容量已达到,这本质上意味着我们的系统性能受到严重影响。 这对我们来说是一个问题,因为我们使用导出功能来备份和移动数据库。 这个问题有解决办法吗? 最佳答
我是一名优秀的程序员,十分优秀!