2020szcupc_2020深圳杯_2020深圳杯c题_深圳杯_python_源码

#%% 导入python库 from __future__ import print_function from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp import xlrd, math import sys import matplotlib.pyplot as plt import numpy as np from geopy.distance import geodesic #%% 导入数据 def read_data_model(): """Stores the data for the problem.""" data = xlrd.open_workbook("/Users/lzs/Downloads/2020szcupc/data/C2.xlsx") table = data.sheet_by_name("Sheet1") rowNum = table.nrows colNum = table.ncols data = {} data['velocity'] = 50 # 时间窗口：位置的时间窗口数组 data['timeWindows'] = [] for i in range(1, rowNum): if i == 1: data['timeWindows'].append((0, 0)) else: data['timeWindows'].append((0, 68)) data['locations'] = [] for i in range(1, rowNum): data['locations'].append([table.cell_value(i,2), table.cell_value(i,1)]) # 时间矩阵：位置之间旅行时间的数组 data['timeMatrix'] = {} for fromCounter, fromNode in enumerate(data['locations']): data['timeMatrix'][fromCounter] = {} for toCounter, toNode in enumerate(data['locations']): if fromCounter == toCounter: data['timeMatrix'][fromCounter][toCounter] = 0 else: # data['timeMatrix'] = distance / velocity data['timeMatrix'][fromCounter][toCounter] = int(geodesic(fromNode, toNode).meters / data['velocity']) # the number of vehicles of the fleet. data['numVehicles'] = 4 # the index of the depot. data['depot'] = 0 return data #%% def print_solution(data, manager, routing, solution): """Prints solution on console.""" time_dimension = routing.GetDimensionOrDie('Time') total_time = 0 colors = {0:'coral',1:'r',2:'g',3:'b'} # 创建一个绘制 plt.title("VRPTW using OR-Tools") plt.xlabel("longitude caption") plt.ylabel("latitude caption") # 绘图 locationsList = np.array(data['locations']) # 提交绘图 plt.annotate(r'$depot$', xy=(locationsList[0]), xycoords='data', xytext=(+10, +30), textcoords='offset points', fontsize=16, arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=.2")) # 可视化节点 plt.plot(locationsList[:,0],locationsList[:,1],'o') for vehicle_id in range(data['numVehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}:\n'.format(vehicle_id) while not routing.IsEnd(index): previous_index = index time_var = time_dimension.CumulVar(index) plan_output += '{0} Time({1},{2}) -> '.format( manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var)) index = solution.Value(routing.NextVar(index)) # 线 plt.plot([locationsList[previous_index if previous_index < 30 else 0][0],locationsList[index if index < 30 else 0][0]], [locationsList[previous_index if previous_index < 30 else 0][1],locationsList[index if index < 30 else 0][1]], color = colors[vehicle_id]) time_var = time_dimension.CumulVar(index) plt.plot([locationsList[index if index < 30 else 0][0],locationsList[0][0]], [locationsList[index if index < 30 else 0][1],locationsList[0][1]], color = colors[vehicle_id]) plan_output += '{0} Time({1},{2})\n'.format(manager.IndexToNode(index), solution.Min(time_var), solution.Max(time_var)) plan_output += 'Time of the route: {} seconds\n'.format( solution.Min(time_var)) print(plan_output) total_time += solution.Min(time_var) print('Total time of all routes: {}min'.format(total_time)) #%% """Solve the VRP with time windows.""" # 实例化数据问题 data = read_data_model() #%% # 创建路线索引管理器 manager = pywrapcp.RoutingIndexManager(len(data['timeMatrix']), data['numVehicles'], data['depot']) # 创建路线模型 routing = pywrapcp.RoutingModel(manager) # 创建并注册传输回调 def time_callback(from_index, to_index): """Returns the travel time between the two nodes.""" # 从路线变量Index转换为时间矩阵NodeIndex from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['timeMatrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(time_callback) # 定义每条路线的成本 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 添加时间窗口限制 time = 'Time' routing.AddDimension( transit_callback_index, 10, # 允许等待时间 95, # 每次传输最长时间 False, # 开始不一定为零 time) time_dimension = routing.GetDimensionOrDie(time) # Add time window constraints for each location except depot. for location_idx, time_window in enumerate(data['timeWindows']): if location_idx == 0: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) # 为每次传输启动节点添加时间窗口约束 for vehicle_id in range(data['numVehicles']): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange(data['timeWindows'][0][0], data['timeWindows'][0][1]) # 实例化路线的开始和结束时间以产生可行的时间 for i in range(data['numVehicles']): routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.Start(i))) routing.AddVariableMinimizedByFinalizer( time_dimension.CumulVar(routing.End(i))) # 设置第一个解决方案启发式 search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) search_parameters.time_limit.seconds = 30 search_parameters.log_search = True # 解决问题 solution = routing.SolveWithParameters(search_parameters) #%% # 打印结果 if solution: print_solution(data, manager, routing, solution) plt.show() # %%