我正在处理日程安排问题，我有N名员工驾驶车辆访问M个日期一致的客户住宅。
我看到的问题是，每辆车的总时间包括从停车场到下车到达第一个地点的第一个协调日期的等待时间。例如，如果车辆0工作日的时间窗口为(上午8点，下午19点(，并且第一个日期为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分钟，我不想加起来从早上8点到上午9点10分的70分钟等待时间。我怎么能满足这个要求？
提前谢谢！我希望@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): {}minn'.format(
solution.Min(time_var)-first_wait_time_depot)
plan_output += 'Time of the route (only driving time): {}minn'.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()
很少有东西：
- 在创建维度时不要"强制累积量开始为零"；也就是说，将其设置为
false，这样车辆就不必精确地启动到上午8点 - 您可以强制仓库等待时间为零：
time_dimension.SlackVar(routing.Start(vehicle)).SetValue(0) - 您可以使用终结器稍后启动并尽早完成
for i in range(manager.GetNumberOfVehicles()):
routing.AddVariableMaximizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
编辑：
也许你的总时间计算是错误的：
17:30 = 17*60 + 30 = 1051 min (from 0:00AM)
9:10 = 9*60+10 = 550 min (from 0:00AM)
和1051 - 550 = 501 min，所以看起来你的总时间(持续时间(计算是错误的。。。