or-tools - Google OR-Tools 找不到解决 VRPtw 问题的方法

Question

我正在解决 VRPtw 问题，并且努力解决求解器找不到任何数据的解决方案，除了人工的小数据。

设置如下。
有几个仓库和地点可供参观。每个位置都有时间窗口。每辆车都有休息时间和工作时间。此外，这些地点有一些限制，只有满足该需求的车辆才能访问那里。

基于这个实验设置，我编写了下面的代码。
正如我所写，它看起来正在处理小型人工数据，但对于真实数据，它从未找到解决方案。我尝试了 5 个不同的数据集。
虽然我设置了 7200 秒的时间限制，但之前我跑了超过 10 个小时，而且是一样的。
数据规模为40~50辆车和200~300个地点。
这段代码有问题吗？如果不是，我应该按照什么样的顺序改变方法（如初始化、搜索方法等）？

（编辑为使用整数作为时间矩阵）

from dataclasses import dataclass
from typing import List, Tuple

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

# TODO: Refactor
BIG_ENOUGH = 100000000
TIME_DIMENSION = 'Time'
TIME_LIMIT = 7200


@dataclass
class DataSet:
    time_matrix: List[List[int]]
    locations_num: int
    vehicles_num: int
    vehicles_break_time_window: List[Tuple[int, int, int]]
    vehicles_work_time_windows: List[Tuple[int, int]]
    location_time_windows: List[Tuple[int, int]]
    vehicles_depots_indices: List[int]
    possible_vehicles: List[List[int]]


def execute(data: DataSet):
    manager = pywrapcp.RoutingIndexManager(data.locations_num,
                                           data.vehicles_num,
                                           data.vehicles_depots_indices,
                                           data.vehicles_depots_indices)

    routing_parameters = pywrapcp.DefaultRoutingModelParameters()
    routing_parameters.solver_parameters.trace_propagation = True
    routing_parameters.solver_parameters.trace_search = True

    routing = pywrapcp.RoutingModel(manager, routing_parameters)

    def time_callback(source_index, dest_index):
        from_node = manager.IndexToNode(source_index)
        to_node = manager.IndexToNode(dest_index)
        return data.time_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    routing.AddDimension(
        transit_callback_index,
        BIG_ENOUGH,
        BIG_ENOUGH,
        False,
        TIME_DIMENSION)
    time_dimension = routing.GetDimensionOrDie(TIME_DIMENSION)

    # set time window for locations start time
    # set condition restrictions
    possible_vehicles = data.possible_vehicles
    for location_idx, time_window in enumerate(data.location_time_windows):
        index = manager.NodeToIndex(location_idx + data.vehicles_num)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
        routing.SetAllowedVehiclesForIndex(possible_vehicles[location_idx], index)

    solver = routing.solver()
    for i in range(data.vehicles_num):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))

    # set work time window for vehicles
    for vehicle_index, work_time_window in enumerate(data.vehicles_work_time_windows):
        start_index = routing.Start(vehicle_index)

        time_dimension.CumulVar(start_index).SetRange(work_time_window[0],
                                                      work_time_window[0])

        end_index = routing.End(vehicle_index)
        time_dimension.CumulVar(end_index).SetRange(work_time_window[1],
                                                    work_time_window[1])

    # set break time for vehicles
    node_visit_transit = {}
    for n in range(routing.Size()):
        if n >= data.locations_num:
            node_visit_transit[n] = 0
        else:
            node_visit_transit[n] = 1

    break_intervals = {}

    for v in range(data.vehicles_num):
        vehicle_break = data.vehicles_break_time_window[v]
        break_intervals[v] = [
            solver.FixedDurationIntervalVar(vehicle_break[0],
                                            vehicle_break[1],
                                            vehicle_break[2],
                                            True,
                                            'Break for vehicle {}'.format(v))
        ]
        time_dimension.SetBreakIntervalsOfVehicle(
            break_intervals[v], v, node_visit_transit
        )

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GREEDY_DESCENT)
    search_parameters.time_limit.seconds = TIME_LIMIT
    search_parameters.log_search = True

    solution = routing.SolveWithParameters(search_parameters)
    return solution


if __name__ == '__main__':

    data = DataSet(
        time_matrix=[[0, 0, 4, 5, 5, 6],
                     [0, 0, 6, 4, 5, 5],
                     [1, 3, 0, 6, 5, 4],
                     [2, 1, 6, 0, 5, 4],
                     [2, 2, 5, 5, 0, 6],
                     [3, 2, 4, 4, 6, 0]],
        locations_num=6,
        vehicles_num=2,
        vehicles_depots_indices=[0, 1],
        vehicles_work_time_windows=[(720, 1080), (720, 1080)],
        vehicles_break_time_window=[(720, 720, 15), (720, 720, 15)],
        location_time_windows=[(735, 750), (915, 930), (915, 930), (975, 990)],
        possible_vehicles=[[0], [1], [0], [1]]
    )
    solution = execute(data)
    if solution is not None:
        print("solution is found")

标签： or-tools