如何建立具有占用时间窗的时变车辆路径问题模型?

Question

我希望在八月建立一个有时间窗口的车辆路由问题模型。具体来说，这个问题涉及到公共道路上的交通执法，所以停车管理员需要调查停车场和路段，并在24小时内多次访问。

我参考以下问题的答案作为发展我的问题的基础:是否有可能使用NetworkX创建VRP解决方案?

我有几个关于建模的问题:

1. OctaPy如何建立时间依赖性模型，即根据一天中的时间代表旅行持续时间的不同边缘权重?
2. 如果每个点需要访问X次，我如何对需求点建模?
3. 如果一个需求点要被访问X次，我如何执行一个时间窗口间隔，使访问之间的持续时间至少是固定的持续时间(例如1小时)?

Answer 1

1. OptaPy以您建模时间依赖性的方式建模时间依赖性。也就是说，无论你用什么来建模时间依赖性(可能是一条边，一个列表，一个矩阵，一个类，等等)，OptaPy都可以在它的约束中使用它。

2. 如果提前知道X，对于每个需求点，您创建X个副本并将其放在@problem_fact_collection_property字段中。如果事先不知道X，可以考虑使用实时规划(https://www.optapy.org/docs/latest/repeated-planning/repeated-planning.html#realTimePlanning)。

3. 这取决于你如何实现你的时间依赖。当OptaPy支持OptaPlanner为列表变量(以及内置的列表影子变量)提供的新的variabelistener API时，这将更容易。在此之前，您需要在函数中进行计算。使Edge为@planning_entity，并给它一个反比阴影变量(https://www.optapy.org/docs/latest/shadow-variable/shadow-variable.html#bidirectionalVariable)。给Vehicle增加一个方法get_arrival_time(edge)，得到visited_edges_list中给定Edge的估计访问时间。

def less_than_one_hour_between(visit_1: Edge, visit_2: Edge):
visit_1_arrival_time = visit_1.vehicle.get_arrival_time(visit_1)
visit_2_arrival_time = visit_2.vehicle.get_arrival_time(visit_2)
duration = visit_2_arrival_time - visit_1_arrival_time
return timedelta(hours=0) <= duration <= timedelta(hours=1)
def one_hour_between_consecutive_visits(constraint_factory):
return (
constraint_factory.for_each(Edge)
.join(Edge, Joiners.equal(lambda edge: edge.graph_from_node),
Joiners.equal(lambda edge: edge.graph_to_node))
.filter(lambda a, b: a is not b and less_than_one_hour_between(a, b))
.penalize('less than 1 hour between visits', HardSoftScore.ONE_HARD)