既然如此，那么代码差不多是一样的，只不过需要额外处理车辆容量问题。

# 导入模块
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

# 创建数据集
def create_data_model():
data = {}
# Array of distances between locations.
_distances =
[
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]

# 每个节点的需求量，0表示起始节点没有需求
demands = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
# 有4辆车，每辆车的最大装载容量
capacities = [15, 15, 15, 15]
# 各个节点之间的距离矩阵
data["distances"] = _distances
# 节点数量
data["num_locations"] = len(_distances)
# 车辆数量
data["num_vehicles"] = 4
# 仓库索引，我们假设所有的车辆都从同一地点出发，也就是车场。
# 或者，你可以允许车辆在任何位置启动和结束。
data["depot"] = 0
data["demands"] = demands
data["vehicle_capacities"] = capacities
return data

# 回调函数，用于计算两个节点间的距离
# 和前面的VRP问题一样的理解
def create_distance_callback(data):
"""Creates callback to return distance between points."""
distances = data["distances"]

def distance_callback(from_node, to_node):
"""Returns the manhattan distance between the two nodes"""
return distances[from_node][to_node]

return distance_callback

# 回调函数，用于计算容量限制或节点需求量
# 可以这么理解，既然有距离的回调函数，那么就有容量或需求的回调函数
def create_demand_callback(data):
"""Creates callback to get demands at each location."""

def demand_callback(from_node, to_node):
return data["demands"][from_node]

return demand_callback

# 容量约束限制
def add_capacity_constraints(routing, data, demand_callback):
"""Adds capacity constraint"""
capacity = "Capacity"
routing.AddDimensionWithVehicleCapacity(
demand_callback,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # 从累积到零，意思应该和「装了这么多剩余空间还能装多少」差不多吧
capacity)

# 列印每辆车的路线(访问的位置)，以及路线的距离。
# 请注意，这些距离包括从仓库到路线中第一个位置的距离以及从最后一个位置返回到仓库的距离。
# IndexToNode, NextVar 函数和前面的tsp问题是相同的意思
def print_solution(data, routing, assignment):
"""Print routes on console."""
total_dist = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = Route for vehicle {0}:
.format(vehicle_id)
route_dist = 0
route_load = 0
while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
next_node_index = routing.IndexToNode(assignment.Value(routing.NextVar(index)))
route_dist += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
route_load += data["demands"][node_index]
plan_output += {0} Load({1}) -> .format(node_index, route_load)
index = assignment.Value(routing.NextVar(index))

node_index = routing.IndexToNode(index)
total_dist += route_dist
plan_output += {0} Load({1})
.format(node_index, route_load)
plan_output += Distance of the route: {0}m
.format(route_dist)
plan_output += Load of the route: {0}
.format(route_load)
print(plan_output)
print(Total Distance of all routes: {0}m.format(total_dist))

# 主函数
def main():

# 创建数据集
data = create_data_model()

# 初始化路由模型
routing = pywrapcp.RoutingModel(
data["num_locations"],
data["num_vehicles"],
data["depot"])

# Define weight of each edge
# 提供距离回调，以便解决程序可以计算位置之间的距离。
distance_callback = create_distance_callback(data)
routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)

# Add Capacity constraint
# 添加容量约束条件
demand_callback = create_demand_callback(data)
add_capacity_constraints(routing, data, demand_callback)

# Setting first solution heuristic (cheapest addition).
# 必须指定启发式方法来找到第一个解决方案
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
# 求解并列印
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
print_solution(data, routing, assignment)

if __name__ == __main__:
main()

# 结果
Route for vehicle 0:
0 Load(0) -> 1 Load(1) -> 4 Load(5) -> 3 Load(7) -> 15 Load(15) -> 0 Load(15)
Distance of the route: 2192m
Load of the route: 15

Route for vehicle 1:
0 Load(0) -> 14 Load(4) -> 16 Load(12) -> 10 Load(14) -> 2 Load(15) -> 0 Load(15)
Distance of the route: 2192m
Load of the route: 15

Route for vehicle 2:
0 Load(0) -> 7 Load(8) -> 13 Load(12) -> 12 Load(14) -> 11 Load(15) -> 0 Load(15)
Distance of the route: 1324m
Load of the route: 15

Route for vehicle 3:
0 Load(0) -> 9 Load(1) -> 8 Load(9) -> 6 Load(13) -> 5 Load(15) -> 0 Load(15)
Distance of the route: 1164m
Load of the route: 15

Total Distance of all routes: 6872m

在这个例子中，所有车辆容量都是相同的，因此可以使用routing.AddDimensionWithVehicleCapacity方法，该方法为所有车辆数量取一个上界。但是该方法也可以处理不同车辆具有不同容量，这种情况更加普遍。

2. 参考

• allow-vehicles-to-start-and-end-any-location
• google_ortools_guide

大家看完记得关注点赞.

master苏.

推荐阅读：