OR-Tools: Как я могу не подсчитать время ожидания от депо до момента первого выхода?

Я работаю над проблемой планирования, когда у меня есть N сотрудников, которые едут на автомобилях, чтобы посетить дома M клиентов с согласованными датами.

Проблема, которую я вижу, заключается в том, что общее время для каждого транспортного средства включает время ожидания от станции до момента выхода, чтобы прибыть к первой согласованной дате в первом месте для посещения. Например, если временное окно для рабочего дня транспортного средства 0 равно (8:00, 19:00), а первая дата — 3 (9:15 утра):

Route for vehicle 0:
0 Time(09:10, 09:10) -> 3 Time(09:15, 09:15) -> 7 Time(12:00, 12:00) -> 11 Time(16:35, 16:35) -> 0 Time(17:31, 17:31)
Time of the route: 571min

Мое ожидаемое время маршрута будет 501 минута, я не хочу суммировать 70 минут ожидания с 8 утра до 9:10 утра. Как я мог смириться с этим?

Заранее спасибо! Надеюсь, @Mizux может мне помочь

РЕДАКТИРОВАТЬ С ТЕКУЩИМ РЕШЕНИЕМ: отслеживая общее количество минут маршрута и только время в пути, можно сравнивать оба:

# Data
time_matrix=[
[0,350.8,556.1,272.5,401.7,319.4,306.1,521.2,569.4,502.4,722.5,742.1],
[275.4,0,243.5,200.9,404.8,436.4,139.7,279.3,256.8,189.8,409.9,468.6],
[419.6,182.4,0,338,541.9,573.5,283.9,239.4,177.2,73.6,250.2,308.9],
[115.4,245.3,442.8,0,372.4,291.5,289.8,370,446.1,388.2,608.3,614.7],
[391.3,443.9,608.6,410.2,0,292.9,527.5,539.6,615.7,586.8,782.9,747.8],
[248.9,412.8,609.2,351.8,300.1,0,415,478.5,554.6,554.6,774.7,686.7],
[207.7,115.5,320.8,268.1,462.2,378.6,0,356.6,334.1,267.1,487.2,545.9],
[419.5,220.6,199.4,304.1,449.2,507.6,322.1,0,76.1,257.6,306.3,309.9],
[478.8,241.6,135.1,379.5,524.6,583,343.1,75.4,0,208.7,242,245.6],
[346,108.8,134.9,264.4,468.3,499.9,210.3,170.7,148.2,0,309.2,367.9],
[576.8,330.9,229.1,495.2,699.1,730.7,404.2,374.4,299,230.8,0,333.9],
[681.4,444.2,277.6,586.3,706.6,765,545.7,302.8,238.6,335.4,207.8,0]
]
ttw = [(0,660),(0,660),(0,660),(60,75),\
(120,135),(90,105),(180,195),(240,255),(285,300),\
(480,495),(510,525),(510,525)]
services_duration = [0,0,0,90,45,60,30,150,45,30,60,45]
NUM_VEHICLES = 3
MIN_ORDERS_BY_VEHICLE = 3 # minimum 2 orders by vehicle
RELATIVE_START_TIME = 8 # 8AM start work day

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

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['time_matrix'] = time_matrix
    data['time_windows'] = ttw # time windows with concerted dates
    data['time_service'] = services_duration # service time for each order
    data['num_vehicles'] = NUM_VEHICLES 
    # we start from initial routes for trying to optimize them
    data['initial_routes'] = [
        [3,7,11], # order vehicle 0
        [4,6,10], # order vehicle 1
        [5,8,9] # # order vehicle 2
    ]
    # vehicles starts and ends from/to same location
    data['starts'] = [0, 1, 2]
    data['ends'] = [0, 1, 2]
    data['breaks'] = [(360, 360, 120), (360, 360, 120), (360, 360, 120)]
    return data

def print_solution(data, manager, routing, solution):
    time_dimension = routing.GetDimensionOrDie('Time')
    count_dimension = routing.GetDimensionOrDie('count')
    travel_dimension = routing.GetDimensionOrDie('travel')
    total_time = 0
    driving_time = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
        i = 0
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            travel_var = travel_dimension.CumulVar(index)
            if i == 0: # store wait time until first exit moment in order can substract it from total route time later
                first_wait_time_depot = solution.Min(time_var)
            count_var = count_dimension.CumulVar(index)
            plan_output += '{0} Time({1}, {2}) -> '.format(manager.IndexToNode(index),
                                                    "{:02d}:{:02d}".format(*divmod((RELATIVE_START_TIME*60)+solution.Min(time_var), 60)),
                                                    "{:02d}:{:02d}".format(*divmod((RELATIVE_START_TIME*60)+solution.Max(time_var), 60))
                                                    )
            index = solution.Value(routing.NextVar(index))
            i+=1

        
        time_var = time_dimension.CumulVar(index)
        travel_var = travel_dimension.CumulVar(index)
        count_var = count_dimension.CumulVar(index)
        plan_output += '{0} Time({1}, {2})\n'.format(manager.IndexToNode(index),
                                                    "{:02d}:{:02d}".format(*divmod((RELATIVE_START_TIME*60)+solution.Min(time_var), 60)),
                                                    "{:02d}:{:02d}".format(*divmod((RELATIVE_START_TIME*60)+solution.Max(time_var), 60)))
        
        print('Orders by vehicle: {}'.format(solution.Min(count_var)-1))
        plan_output += 'Time of the route (with waiting and service times): {}min\n'.format(
            solution.Min(time_var)-first_wait_time_depot)
        plan_output += 'Time of the route (only driving time): {}min\n'.format(
            solution.Min(travel_var))
        print(plan_output)
        total_time += solution.Min(time_var)-first_wait_time_depot
        driving_time += solution.Min(travel_var)
    print('Total time of all routes: {}min'.format(total_time))
    print('Total driving time of all routes: {}min'.format(driving_time))
    return {'driving_time': driving_time, 'total_time':total_time}
    
def main():
    """Entry point of the program."""
    data = create_data_model()
    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['time_matrix']),
                                           data['num_vehicles'], data['starts'],
                                           data['ends'])
    routing = pywrapcp.RoutingModel(manager)
    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['time_service'][from_node]+(int(round(data['time_matrix'][from_node][to_node]/60.)))
    
    def travel_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return int(round(data['time_matrix'][from_node][to_node]/60.))
    
    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    travel_callback_index = routing.RegisterTransitCallback(travel_callback)

    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time dimension.
    time = 'Time'
    routing.AddDimension(
        transit_callback_index,
        660,  # allow waiting time
        660,  # maximum time per vehicle
        False,  # Don't force start cumul to zero. Vehicles don't have to start to exactly start hour
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    
    # Add only travel time dimension.
    routing.AddDimension(
        travel_callback_index,
        0,  # allow waiting time
        660,  # maximum time per vehicle
        True,  # Don't force start cumul to zero. Vehicles don't have to start to exactly start hour
        'travel')
    travel_dimension = routing.GetDimensionOrDie('travel')
    
    # Add time window constraints for each location except depots.
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx in data['starts']:
            continue # except depots
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
        # Set allowed vehicles for order
        routing.SetAllowedVehiclesForIndex([], index) # for the moment, all vehicles can visit any node

    # Add COUNT dimension constraint.
    count_dimension_name = 'count'
    routing.AddConstantDimension(
        1, # increment by one every time
        len(data['time_matrix'])+1,  # make sure the return to depot node can be counted
        True,  # set count to zero
        count_dimension_name)
    count_dimension = routing.GetDimensionOrDie(count_dimension_name)
    
    # enable empty route cost
    # https://github.com/google/or-tools/issues/2067
    # https://github.com/google/or-tools/issues/2161
    for vehicle_id in range(data['num_vehicles']):
        routing.ConsiderEmptyRouteCostsForVehicle(True, vehicle_id)
        
    # Add time window constraints for each vehicle start node.
    for vehicle_id in range(data['num_vehicles']):
        # force depot waiting time to zero
        time_dimension.SlackVar(routing.Start(vehicle_id)).SetValue(0)
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(data['time_windows'][vehicle_id][0],
                                                data['time_windows'][vehicle_id][1])
        
    # https://activimetrics.com/blog/ortools/counting_dimension/
    for vehicle_id in range(data['num_vehicles']):
        index_end = routing.End(vehicle_id)
        count_dimension.SetCumulVarSoftLowerBound(index_end,
                                              MIN_ORDERS_BY_VEHICLE + 1,
                                              100000)
    
    # set break time for vehicles
    
    node_visit_transit = {}
    for n in range(routing.Size()):
        if n >= len(data['time_service']):
            node_visit_transit[n] = 0
        else:
            node_visit_transit[n] = 1

    break_intervals = {}

    for v in range(data['num_vehicles']):
        vehicle_break = data['breaks'][v]
        break_intervals[v] = [
            routing.solver().FixedDurationIntervalVar(vehicle_break[0],
                                            vehicle_break[1],
                                            vehicle_break[2],
                                            False,
                                            'Break for vehicle {}'.format(v))
        ]
        time_dimension.SetBreakIntervalsOfVehicle(
            break_intervals[v], v, node_visit_transit
        )
    
    # Instantiate route start and end times to produce feasible times.
    # to start the later and finish the earliest possible
    for i in range(manager.GetNumberOfVehicles()):
        routing.AddVariableMaximizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.End(i)))
        
    for i in range(manager.GetNumberOfVehicles()):
        routing.AddVariableMaximizedByFinalizer(
            travel_dimension.CumulVar(routing.Start(i)))
        routing.AddVariableMinimizedByFinalizer(
            travel_dimension.CumulVar(routing.End(i)))
        
    initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'], True)
    print("Initial sol:\n")
    ini_times = print_solution(data, manager, routing, initial_solution)
    
    # Setting first solution heuristic.
    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.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.FromSeconds(100)

    solution = routing.SolveFromAssignmentWithParameters(initial_solution, search_parameters)
    if solution:
        print("\nSolved sol:\n")
        end_times = print_solution(data, manager, routing, solution)
        print("\nTotal route minutes saved: {} min".format(ini_times['total_time'] - end_times['total_time']))
        print("Only driving minutes saved: {} min".format(ini_times['driving_time'] - end_times['driving_time']))

if __name__ == '__main__':
    main()