# 如何在python中使用or-tools解決累積旅行商問題？

[[0, 10, 20],
[10, 0, 15],
[20, 15, 0]]


• 旅行時間為45。0 -> 1：10 + 1 -> 2：15 + 2 -> 0：20 = 10 + 15 + 20 =45。
• 位置時間為35。對於位置1：0 -> 1：10。對於位置2（請注意，我們必須經過位置1）：0 -> 1：10 + 1 -> 2：15。總而言之，我們有：10 + 10 + 15 =35。

• 行駛時間為60。對於車輛1：0 -> 1：10 + 0 -> 12：10。對於車輛2：0 -> 13：20 + 2 -> 0：20。總而言之，我們的0 -> 15 =60。
• 位置時間是30。對於位置1：0 -> 1：10.對於位置2（請注意，我們 不必經過位置1）：0 -> 13：20總之，我們有：0 -> 18 = 30.

"""Vehicles Routing Problem (VRP)."""

from __future__ import print_function

from ortools.constraint_solver import pywrapcp

def create_data_model():
"""Stores the data for the problem."""
data = {}
data['time_matrix'] = [
[0, 10, 20],
[10, 0, 15],
[20, 15, 0]
]
data['num_vehicles'] = 2
data['depot'] = 0
return data

def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
max_route_time = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
route_time = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_time += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'time of the route: {}\n'.format(route_time)
print(plan_output)
max_route_time = max(route_time, max_route_time)
print('Maximum of the route times: {}'.format(max_route_time))

def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data['time_matrix']), data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
def time_callback(from_index, to_index):
"""Returns the 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_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(time_callback)

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

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()

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

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

if __name__ == '__main__':
main()


Route for vehicle 0:
0 -> 0
time of the route: 0

Route for vehicle 1:
0 ->  1 ->  2 -> 0
time of the route: 45

Maximum of the route times: 45


This is a heuristic approach to the problem you describe using OR tools. Consider a procedure in which you “guess” what the maximum route duration is (across all routes), and will find this in a binary search fashion. Your guess, $$G$$, is between $$L$$ and $$U$$, and for a particular iteration, set it to $$G=\frac{U+L}{2}$$. At iteration 0, $$L=0$$and $$U=\texttt{max duration vrp}$$ (45 in your example). Now add a constraint to the problem using routing.AddDimension() that says that routes should have a duration less or equal to $$G$$. If the problem is feasible, then $$U=G$$ and update $$G$$. Otherwise, $$L=G$$ and update $$G$$. You do this until the $$L$$ and $$U$$ are arbitrarily close. Note that every time you update $$G$$, you need to update the constraint you added to the routing object (or create a new object from scratch).