累积旅行商问题 (CTSP) 的目标是最小化到达客户的时间总和，而不是总旅行时间。这与最小化总旅行时间不同。例如，如果一个人拥有无限的车辆（#车辆与位置数量相同），并且目标是最大限度地减少到达位置的总时间，则可以为每个位置发送一辆车，因为这是满足所述需求的最快方式。可以看出，or-tools 路由模块主要关注于最小化总体旅行时间（而不是到达地点的时间）。有没有办法解决 CTSP，并且更好的是在最小化到达地点的时间与最小化旅行时间之间取得平衡（可能使用权重）？
让我展示一个分析示例。
假设我们有一个仓库 (0) 和两个客户（1 和 2）。让我们考虑以下时间矩阵：
[[0, 10, 20],
[10, 0, 15],
[20, 15, 0]]
假设我们的车辆数量等于位置数量（2 辆车）。让我们考虑以下两种情况：
目标 1：如果我们想最大程度地减少总体旅行时间
解决办法是0 -> 1 -> 2 -> 0（使用一辆车），其中：
-
旅行时间 is 45.
0 -> 1: 10 + 1 -> 2: 15 + 2 -> 0: 20 = 10 + 15 = 45.
-
地点 时间是 35。对于位置 1：
0 -> 1： 10.对于位置2（注意我们必须经过位置1）：0 -> 1: 10 + 1 -> 2： 15. 总而言之，我们有：10 + 10 + 15 = 35.
目标 2：如果我们想尽量减少到达地点的时间
解决办法是0 -> 1 -> 0 and 0 -> 2 -> 0（使用两辆车），其中：
-
旅行时间是 60。对于车辆 1：
0 -> 1: 10 + 1 -> 0： 10. 对于车辆 2：0 -> 2: 20 + 2 -> 0: 20. 综上所述，我们有10 +
10 + 20 + 20 = 60.
-
地点 时间是 30。对于位置 1：
0 -> 1： 10. 对于位置 2（请注意，我们do not必须经过地点 1):0 -> 2: 20. 总而言之，我们有：10 + 20 = 30.
那么……这可以吗？能否解决 CTSP（目标 2）？是否有可能有一个目标函数，以便我们可以平衡这两个目标（即min alpha * overall_travel_time + beta * time_to_locations，使得alpha and beta是权重）。Python代码非常感谢。谢谢你！
目标 1 的工作代码：最小化总行程时间
"""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
