Использование ortools для максимизации проблемы коммивояжера - PullRequest
Новая
       61

Использование ortools для максимизации проблемы коммивояжера

0 голосов
/ 02 июля 2019

В примерах и руководствах google ortools я вижу реализацию обычного TSP для минимизации времени на поездки.Что если у меня есть еще одна особенность, такая как тариф, которую я хочу вместо этого увеличить?Есть ли способ, которым я могу этого достичь.

У меня есть тарифы для всех комбинаций городов в матрице.

Я надеюсь, что у меня будет возможность использовать эту функцию, чтобы рассчитать, какой будет мой максимальный тариф, если мне придется посетить все города один раз. 

def create_data_model():
final_data= pd.read_csv('C:\\Users\\dojha\\final_data.csv')
rate_city_matrix_df = pd.DataFrame()
rate_city_matrix_df['origin']= final_data['origin_city']
rate_city_matrix_df['destination']= final_data['destination_city']
rate_city_matrix_df['rate']= final_data['line_haul_rate']
rate_city_matrix = rate_city_matrix_df.groupby(['origin','destination']).sum().unstack('destination')
rate_city_matrix_array= rate_city_matrix.values[0:4,:]
all_nans= np.isnan(rate_city_matrix_array)
rate_city_matrix_array[all_nans]=0
data={}
data['rate_matrix']=rate_city_matrix_array
data['num_vehicles']=1
data['depot']=0
return data

def print_solution(manager, routing, assignment):
"""Prints assignment on console."""
print('Objective: {} dollars'.format(assignment.ObjectiveValue()))
index = routing.Start(0)
plan_output = 'Route for vehicle 0:\n'
route_distance = 0
while not routing.IsEnd(index):
    plan_output += ' {} ->'.format(manager.IndexToNode(index))
    previous_index = index
    index = assignment.Value(routing.NextVar(index))
    route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += ' {}\n'.format(manager.IndexToNode(index))
print(plan_output)
plan_output += 'Route distance: {}miles\n'.format(route_distance)

def main():
#entry point for the program
data= create_data_model()
#create the routing index manager
manager= pywrapcp.RoutingIndexManager(
    len(data['rate_matrix']), data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)


def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['rate_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if assignment:
    print_solution(manager, routing, assignment)


if __name__ == '__main__':
    main()

Линейный тарифотрицательное значение

...