关于 vrp-time-windows
用于规划带客户时间窗的车辆路线的技能。它涵盖硬性与软性时间窗、车辆容量和服务时间，并介绍从精确优化到启发式方法的求解方式。
主要功能
- 01硬性与软性时间窗建模
- 02车辆容量与路线限制
- 03精确及启发式求解方法
- 04考虑时间窗的路线改进
- 05生成路线时刻表与报告
适用场景
- 01规划需遵守严格预约时间的配送
- 02为灵活站点设置迟到惩罚
- 03权衡行驶距离与车队规模
- 04查看到达、等待和服务时刻表
安装
复制下面的命令，在终端中运行。
$
npx skills add https:/安装后在 Claude Code 中输入/vrp-time-windows确认已加载。
详细介绍
带时间窗的车辆路径问题（VRPTW）
你是带时间窗的车辆路径问题和时间约束优化领域的专家。你的目标是帮助确定车队的最优路线，使每位客户都能在特定时间窗内得到拜访，同时兼顾路径成本与客户服务要求。
初步评估
在求解 VRPTW 实例之前，先了解以下信息：
-
时间窗特征
- 时间窗是硬约束（必须满足）还是软约束（可违反但需付出惩罚）？
- 有多少客户有时间窗？是所有客户还是部分客户？
- 时间窗的宽度是多少？（越窄，问题越难）
- 时间窗在一天中的分布情况如何？
-
时间参数
- 每位客户的服务时间是多少？
- 地点之间的行驶时间是多少？
- 车辆的工作时长／最大路线时间是多少？
- 仓库的营业时间是多少？
- 驾驶员是否需要休息？
-
车队信息
- 有多少辆可用车辆？
- 车辆的载荷能力是多少？
- 从仓库出发的最早时间是什么？
- 返回仓库的最晚时间是什么？
-
问题规模
- 小型（少于 25 位客户）：可使用精确方法
- 中型（25–100 位客户）：可使用高级启发式算法
- 大型（100 位以上客户）：需要使用元启发式算法
-
目标
- 最小化总距离／时间？
- 最小化车辆数量（首要目标）？
- 最小化违反时间窗的次数？
- 最小化等待时间？
数学建模
硬时间窗 VRPTW
集合：
- V = {0, 1, ..., n}：节点（0 = 仓库，1..n = 客户）
- K = {1, ..., m}：车辆
参数：
- c_{ij}：从节点 i 到 j 的成本／距离
- t_{ij}：从节点 i 到 j 的行驶时间
- d_i：客户 i 的需求量
- s_i：客户 i 的服务时间
- [e_i, l_i]：客户 i 的时间窗（最早时间、最晚时间）
- Q_k：车辆 k 的载荷能力
- T_max：最长路线时长
决策变量：
- x_{ijk} ∈ {0,1}：若车辆 k 从 i 行驶到 j，则为 1
- w_i ≥ 0：到达客户 i 的时间
目标函数：
Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V} c_{ij} * x_{ijk}
或先最小化车辆数量：
Minimize: Σ_{k∈K} Σ_{j∈V\{0}} x_{0jk} + α * Σ_{k∈K} Σ_{i,j∈V} c_{ij} * x_{ijk}
约束：
1. Each customer visited exactly once:
Σ_{k∈K} Σ_{i∈V} x_{ijk} = 1, ∀j ∈ V\{0}
2. Flow conservation:
Σ_{i∈V} x_{ihk} - Σ_{j∈V} x_{hjk} = 0, ∀h ∈ V, ∀k ∈ K
3. Vehicle starts from depot:
Σ_{j∈V\{0}} x_{0jk} ≤ 1, ∀k ∈ K
4. Vehicle returns to depot:
Σ_{i∈V\{0}} x_{i0k} ≤ 1, ∀k ∈ K
5. Capacity constraint:
Σ_{i∈V\{0}} Σ_{j∈V} d_i * x_{ijk} ≤ Q_k, ∀k ∈ K
6. Time window constraints:
e_i ≤ w_i ≤ l_i, ∀i ∈ V
7. Time consistency (if vehicle k goes from i to j):
w_i + s_i + t_{ij} ≤ w_j + M*(1 - Σ_k x_{ijk}), ∀i,j ∈ V, i≠j
8. Maximum route duration:
w_i + s_i + t_{i0} ≤ T_max, ∀i ∈ V\{0}
9. Binary variables:
x_{ijk} ∈ {0,1}, ∀i,j ∈ V, ∀k ∈ K
软时间窗建模
添加惩罚变量和成本：
附加变量：
- α_i ≥ 0：提前到达 i 的时间（早于 e_i）
- β_i ≥ 0：迟到 i 的时间（晚于 l_i）
修改后的目标函数：
Minimize: Σ_{k,i,j} c_{ij} * x_{ijk} +
Σ_i (penalty_early * α_i + penalty_late * β_i)
修改后的时间窗约束：
w_i + α_i ≥ e_i, ∀i
w_i - β_i ≤ l_i, ∀i
精确算法
1. VRPTW 分支定价法
from pulp import *
import numpy as np
def vrptw_mip(dist_matrix, time_matrix, demands, time_windows,
service_times, vehicle_capacity, num_vehicles,
depot=0, max_route_time=480):
"""
VRPTW using MIP formulation
Args:
dist_matrix: n x n distance matrix
time_matrix: n x n travel time matrix (minutes)
demands: list of demands
time_windows: list of (earliest, latest) tuples (minutes)
service_times: list of service times (minutes)
vehicle_capacity: vehicle capacity
num_vehicles: number of vehicles
depot: depot index
max_route_time: maximum route duration (minutes)
Returns:
solution dictionary
"""
n = len(dist_matrix)
customers = [i for i in range(n) if i != depot]
# Create problem
prob = LpProblem("VRPTW", LpMinimize)
# Decision variables
x = {}
for i in range(n):
for j in range(n):
if i != j:
for k in range(num_vehicles):
x[i,j,k] = LpVariable(f"x_{i}_{j}_{k}", cat='Binary')
# Arrival time variables
w = {}
for i in range(n):
for k in range(num_vehicles):
w[i,k] = LpVariable(f"w_{i}_{k}",
lowBound=time_windows[i][0],
upBound=time_windows[i][1],
cat='Continuous')
# Objective: Minimize total distance
prob += lpSum([dist_matrix[i][j] * x[i,j,k]
for i in range(n) for j in range(n) if i != j
for k in range(num_vehicles)]), "Total_Distance"
# Constraints
# 1. Each customer visited exactly once
for j in customers:
prob += lpSum([x[i,j,k] for i in range(n) if i != j
for k in range(num_vehicles)]) == 1, f"Visit_{j}"
# 2. Flow conservation
for h in range(n):
for k in range(num_vehicles):
prob += (lpSum([x[i,h,k] for i in range(n) if i != h]) ==
lpSum([x[h,j,k] for j in range(n) if j != h])), \
f"Flow_{h}_{k}"
# 3. Capacity constraints
for k in range(num_vehicles):
prob += lpSum([demands[j] * x[i,j,k]
for i in range(n) for j in customers if i != j]) \
<= vehicle_capacity, f"Capacity_{k}"
# 4. Time consistency constraints
M = 10000 # Big-M
for i in range(n):
for j in range(n):
if i != j:
for k in range(num_vehicles):
prob += (w[i,k] + service_times[i] + time_matrix[i][j] <=
w[j,k] + M * (1 - x[i,j,k])), \
f"Time_{i}_{j}_{k}"
# 5. Time windows already enforced by variable bounds
# 6. Maximum route duration
for k in range(num_vehicles):
for i in customers:
prob += (w[i,k] + service_times[i] + time_matrix[i][depot] <=
time_windows[depot][1]), f"MaxTime_{i}_{k}"
# Solve
import time
start_time = time.time()
prob.solve(PULP_CBC_CMD(msg=1, timeLimit=600))
solve_time = time.time() - start_time
# Extract solution
if LpStatus[prob.status] in ['Optimal', 'Feasible']:
routes = []
arrival_times = []
for k in range(num_vehicles):
route = [depot]
times = [w[depot,k].varValue]
current = depot
while True:
next_node = None
for j in range(n):
if j != current and (current,j,k) in x:
if x[current,j,k].varValue > 0.5:
next_node = j
break
if next_node is None or next_node == depot:
route.append(depot)
times.append(w[depot,k].varValue +
sum(service_times[route[i]] + time_matrix[route[i]][route[i+1]]
for i in range(len(route)-1)))
break
route.append(next_node)
times.append(w[next_node,k].varValue)
current = next_node
if len(route) > 2:
routes.append(route)
arrival_times.append(times)
return {
'status': LpStatus[prob.status],
'total_distance': value(prob.objective),
'routes': routes,
'arrival_times': arrival_times,
'num_vehicles_used': len(routes),
'solve_time': solve_time
}
else:
return {
'status': LpStatus[prob.status],
'total_distance': None,
'routes': None,
'solve_time': solve_time
}
构造启发式算法
1. Solomon 的 I1 插入启发式算法
def solomon_i1_insertion(dist_matrix, time_matrix, demands, time_windows,
service_times, vehicle_capacity, depot=0,
alpha=1.0, mu=1.0, lambda_param=1.0):
"""
Solomon's I1 insertion heuristic for VRPTW
One of the best constructive heuristics for VRPTW
Args:
dist_matrix: distance matrix
time_matrix: travel time matrix
demands: customer demands
time_windows: list of (earliest, latest) tuples
service_times: service times
vehicle_capacity: vehicle capacity
depot: depot index
alpha, mu, lambda_param: criterion weights
Returns:
solution dictionary
"""
n = len(dist_matrix)
customers = set(range(n)) - {depot}
routes = []
route_loads = []
route_times = []
while customers:
# Initialize new route with seed customer
# Select farthest customer from depot
seed = max(customers, key=lambda c: dist_matrix[depot][c])
route = [depot, seed, depot]
current_time = [time_windows[depot][0],
max(time_windows[depot][0] + time_matrix[depot][seed],
time_windows[seed][0]),
0]
# Update current_time[2] (return to depot)
current_time[2] = (current_time[1] + service_times[seed] +
time_matrix[seed][depot])
current_load = demands[seed]
customers.remove(seed)
# Insert remaining customers into this route
while customers:
best_customer = None
best_position = None
best_criterion = float('inf')
# Try inserting each unrouted customer
for customer in list(customers):
if current_load + demands[customer] > vehicle_capacity:
continue
# Try each insertion position
for pos in range(1, len(route)):
i = route[pos - 1]
j = route[pos]
# Calculate feasibility
# Arrival time at customer
arrival_at_customer = (current_time[pos-1] +
service_times[i] +
time_matrix[i][customer])
# Check time window feasibility
if arrival_at_customer > time_windows[customer][1]:
continue # Too late
# Start service time (wait if early)
start_service = max(arrival_at_customer,
time_windows[customer][0])
# Check if rest of route is still feasible
push_forward = max(0, start_service + service_times[customer] +
time_matrix[customer][j] - current_time[pos])
# Check if pushing forward violates time windows
feasible = True
temp_time = current_time[pos] + push_forward
for k in range(pos, len(route) - 1):
if temp_time > time_windows[route[k]][1]:
feasible = False
break
temp_time = (max(temp_time, time_windows[route[k]][0]) +
service_times[route[k]] +
time_matrix[route[k]][route[k+1]])
if not feasible:
continue
# Calculate insertion criterion (c1)
# c11: distance increase
c11 = (dist_matrix[i][customer] + dist_matrix[customer][j] -
mu * dist_matrix[i][j])
# c12: time increase
c12 = (start_service - current_time[pos-1])
c1 = alpha * c11 + (1 - alpha) * c12
# c2: distance from depot (encourages early insertion)
c2 = dist_matrix[depot][customer]
# Combined criterion
criterion = lambda_param * c1 - c2
if criterion < best_criterion:
best_criterion = criterion
best_customer = customer
best_position = pos
if best_customer is None:
break # No more customers fit
# Insert best customer
route.insert(best_position, best_customer)
current_load += demands[best_customer]
# Update arrival times
new_times = [current_time[0]]
for k in range(1, len(route)):
arrival = (new_times[k-1] +
service_times[route[k-1]] +
time_matrix[route[k-1]][route[k]])
start = max(arrival, time_windows[route[k]][0])
new_times.append(start)
current_time = new_times
customers.remove(best_customer)
routes.append(route)
route_loads.append(current_load)
# Calculate total distance
total_distance = sum(
sum(dist_matrix[route[i]][route[i+1]] for i in range(len(route)-1))
for route in routes
)
return {
'routes': routes,
'route_loads': route_loads,
'total_distance': total_distance,
'num_vehicles': len(routes)
}
2. 带时间窗的最近邻算法
def nearest_neighbor_tw(dist_matrix, time_matrix, demands, time_windows,
service_times, vehicle_capacity, depot=0):
"""
Nearest neighbor heuristic adapted for time windows
Args:
dist_matrix, time_matrix: distance and time matrices
demands: customer demands
time_windows: list of (earliest, latest) tuples
service_times: service times
vehicle_capacity: vehicle capacity
depot: depot index
Returns:
solution dictionary
"""
n = len(dist_matrix)
unrouted = set(range(n)) - {depot}
routes = []
while unrouted:
route = [depot]
current_time = time_windows[depot][0]
current_load = 0
current_location = depot
while True:
# Find nearest feasible customer
best_customer = None
best_distance = float('inf')
for customer in unrouted:
# Check capacity
if current_load + demands[customer] > vehicle_capacity:
continue
# Check time window feasibility
arrival_time = current_time + time_matrix[current_location][customer]
if arrival_time > time_windows[customer][1]:
continue # Too late
# This customer is feasible
distance = dist_matrix[current_location][customer]
if distance < best_distance:
best_distance = distance
best_customer = customer
if best_customer is None:
break # No feasible customers
# Add customer to route
route.append(best_customer)
arrival_time = current_time + time_matrix[current_location][best_customer]
current_time = max(arrival_time, time_windows[best_customer][0])
current_time += service_times[best_customer]
current_load += demands[best_customer]
current_location = best_customer
unrouted.remove(best_customer)
# Return to depot
route.append(depot)
routes.append(route)
# Calculate total distance
total_distance = sum(
sum(dist_matrix[route[i]][route[i+1]] for i in range(len(route)-1))
for route in routes
)
return {
'routes': routes,
'total_distance': total_distance,
'num_vehicles': len(routes)
}
改进启发式算法
1. 满足时间窗可行性的 2-Opt 算法
def two_opt_tw(route, dist_matrix, time_matrix, time_windows, service_times):
"""
2-opt improvement with time window checks
Args:
route: route to improve
dist_matrix: distance matrix
time_matrix: travel time matrix
time_windows: time windows
service_times: service times
Returns:
improved route
"""
def check_tw_feasibility(route):
"""Check if route satisfies all time windows"""
current_time = time_windows[route[0]][0]
for i in range(len(route) - 1):
current_time += time_matrix[route[i]][route[i+1]]
# Check if arrival is within time window
if current_time > time_windows[route[i+1]][1]:
return False
# Wait if early
current_time = max(current_time, time_windows[route[i+1]][0])
current_time += service_times[route[i+1]]
return True
improved = True
best_route = route.copy()
while improved:
improved = False
n = len(best_route)
for i in range(1, n - 2):
for j in range(i + 1, n - 1):
# Try reversing segment [i, j]
new_route = best_route.copy()
new_route[i:j+1] = reversed(new_route[i:j+1])
# Check time window feasibility
if not check_tw_feasibility(new_route):
continue
# Calculate distance change
old_dist = (dist_matrix[best_route[i-1]][best_route[i]] +
dist_matrix[best_route[j]][best_route[j+1]])
new_dist = (dist_matrix[new_route[i-1]][new_route[i]] +
dist_matrix[new_route[j]][new_route[j+1]])
if new_dist < old_dist - 1e-10:
best_route = new_route
improved = True
break
if improved:
break
return best_route
2. 带时间窗的交叉交换算法
def cross_exchange_tw(routes, dist_matrix, time_matrix, demands,
time_windows, service_times, vehicle_capacity):
"""
Cross-exchange operator with time window feasibility
Args:
routes: list of routes
dist_matrix, time_matrix: distance and time matrices
demands: customer demands
time_windows: time windows
service_times: service times
vehicle_capacity: vehicle capacity
Returns:
improved routes
"""
def calculate_route_cost(route):
return sum(dist_matrix[route[i]][route[i+1]]
for i in range(len(route)-1))
def check_route_feasibility(route):
"""Check capacity and time window feasibility"""
# Check capacity
load = sum(demands[c] for c in route[1:-1])
if load > vehicle_capacity:
return False
# Check time windows
current_time = time_windows[route[0]][0]
for i in range(len(route) - 1):
current_time += time_matrix[route[i]][route[i+1]]
if current_time > time_windows[route[i+1]][1]:
return False
current_time = max(current_time, time_windows[route[i+1]][0])
current_time += service_times[route[i+1]]
return True
num_routes = len(routes)
improved = True
while improved:
improved = False
for r1 in range(num_routes):
for r2 in range(r1 + 1, num_routes):
route1 = routes[r1].copy()
route2 = routes[r2].copy()
# Try swapping customers
for i in range(1, len(route1) - 1):
for j in range(1, len(route2) - 1):
# Create new routes with swap
new_route1 = route1.copy()
new_route2 = route2.copy()
new_route1[i] = route2[j]
new_route2[j] = route1[i]
# Check feasibility
if (not check_route_feasibility(new_route1) or
not check_route_feasibility(new_route2)):
continue
# Calculate improvement
old_cost = (calculate_route_cost(route1) +
calculate_route_cost(route2))
new_cost = (calculate_route_cost(new_route1) +
calculate_route_cost(new_route2))
if new_cost < old_cost - 1e-10:
routes[r1] = new_route1
routes[r2] = new_route2
improved = True
break
if improved:
break
if improved:
break
if improved:
break
return routes
元启发式算法
1. 自适应大邻域搜索（ALNS）
import random
def alns_vrptw(dist_matrix, time_matrix, demands, time_windows,
service_times, vehicle_capacity, initial_solution,
iterations=1000, destroy_size=0.3):
"""
Adaptive Large Neighborhood Search for VRPTW
Args:
dist_matrix, time_matrix: distance and time matrices
demands: customer demands
time_windows: time windows
service_times: service times
vehicle_capacity: vehicle capacity
initial_solution: initial routes
iterations: number of iterations
destroy_size: fraction of customers to remove
Returns:
best solution found
"""
import copy
def calculate_cost(routes):
return sum(sum(dist_matrix[route[i]][route[i+1]]
for i in range(len(route)-1))
for route in routes)
def shaw_removal_tw(routes, num_remove):
"""Remove related customers (considering location and time)"""
all_customers = []
for route in routes:
all_customers.extend(route[1:-1])
if not all_customers or num_remove == 0:
return routes, []
seed = random.choice(all_customers)
to_remove = {seed}
# Calculate relatedness (distance + time window similarity)
relatedness = []
for customer in all_customers:
if customer != seed:
dist_similarity = dist_matrix[seed][customer]
time_similarity = abs(time_windows[seed][0] - time_windows[customer][0])
combined = dist_similarity + 0.1 * time_similarity
relatedness.append((combined, customer))
relatedness.sort()
for _, customer in relatedness[:min(num_remove-1, len(relatedness))]:
to_remove.add(customer)
# Remove from routes
new_routes = []
depot = routes[0][0]
for route in routes:
new_route = [depot]
for customer in route[1:-1]:
if customer not in to_remove:
new_route.append(customer)
new_route.append(depot)
if len(new_route) > 2:
new_routes.append(new_route)
return new_routes, list(to_remove)
def greedy_insertion_tw(routes, removed_customers, depot):
"""Reinsert customers with time window checking"""
uninserted = removed_customers.copy()
def check_insertion_feasibility(route, customer, position):
"""Check if inserting customer at position is feasible"""
new_route = route[:position] + [customer] + route[position:]
# Check capacity
load = sum(demands[c] for c in new_route[1:-1])
if load > vehicle_capacity:
return False
# Check time windows
current_time = time_windows[new_route[0]][0]
for i in range(len(new_route) - 1):
current_time += time_matrix[new_route[i]][new_route[i+1]]
if current_time > time_windows[new_route[i+1]][1]:
return False
current_time = max(current_time, time_windows[new_route[i+1]][0])
current_time += service_times[new_route[i+1]]
return True
while uninserted:
best_customer = None
best_route_idx = None
best_position = None
best_cost = float('inf')
for customer in uninserted:
# Try existing routes
for r_idx, route in enumerate(routes):
for pos in range(1, len(route)):
if check_insertion_feasibility(route, customer, pos):
cost = (dist_matrix[route[pos-1]][customer] +
dist_matrix[customer][route[pos]] -
dist_matrix[route[pos-1]][route[pos]])
if cost < best_cost:
best_cost = cost
best_customer = customer
best_route_idx = r_idx
best_position = pos
if best_customer is None:
# Create new route
routes.append([depot, uninserted.pop(0), depot])
else:
routes[best_route_idx].insert(best_position, best_customer)
uninserted.remove(best_customer)
return routes
# ALNS main loop
current_routes = copy.deepcopy(initial_solution)
current_cost = calculate_cost(current_routes)
best_routes = copy.deepcopy(current_routes)
best_cost = current_cost
depot = current_routes[0][0]
# Count customers
all_customers = []
for route in current_routes:
all_customers.extend(route[1:-1])
num_remove = max(1, int(len(all_customers) * destroy_size))
for iteration in range(iterations):
# Destroy
partial_routes, removed = shaw_removal_tw(current_routes, num_remove)
# Repair
new_routes = greedy_insertion_tw(partial_routes, removed, depot)
# Evaluate
new_cost = calculate_cost(new_routes)
# Simulated annealing acceptance
temperature = 100 * (1 - iteration / iterations)
accept = (new_cost < current_cost or
random.random() < np.exp(-(new_cost - current_cost) / max(temperature, 1)))
if accept:
current_routes = new_routes
current_cost = new_cost
if new_cost < best_cost:
best_routes = copy.deepcopy(new_routes)
best_cost = new_cost
return {
'routes': best_routes,
'total_distance': best_cost,
'num_vehicles': len(best_routes)
}
使用 OR-Tools
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def solve_vrptw_ortools(dist_matrix, time_matrix, demands, time_windows,
service_times, vehicle_capacities, num_vehicles,
depot=0, time_limit=60):
"""
Solve VRPTW using Google OR-Tools
Most practical approach for real-world VRPTW
Args:
dist_matrix: distance matrix
time_matrix: travel time matrix
demands: customer demands
time_windows: list of (earliest, latest) tuples
service_times: service times at each location
vehicle_capacities: vehicle capacities
num_vehicles: number of vehicles
depot: depot index
time_limit: time limit in seconds
Returns:
solution dictionary
"""
n = len(dist_matrix)
# Handle uniform fleet
if isinstance(vehicle_capacities, (int, float)):
vehicle_capacities = [vehicle_capacities] * num_vehicles
# Create routing index manager
manager = pywrapcp.RoutingIndexManager(n, num_vehicles, depot)
# Create routing model
routing = pywrapcp.RoutingModel(manager)
# Distance callback
def distance_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return int(dist_matrix[from_node][to_node] * 100)
distance_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(distance_callback_index)
# Time callback
def time_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return int(time_matrix[from_node][to_node] + service_times[from_node])
time_callback_index = routing.RegisterTransitCallback(time_callback)
# Add time window constraints
routing.AddDimension(
time_callback_index,
30, # allow waiting time
3000, # maximum time per vehicle
False, # don't force start cumul to zero
'Time')
time_dimension = routing.GetDimensionOrDie('Time')
# Add time window constraints for each location
for location_idx in range(n):
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(
int(time_windows[location_idx][0]),
int(time_windows[location_idx][1])
)
# Add time window constraints for depot (all vehicles)
for vehicle_id in range(num_vehicles):
start_index = routing.Start(vehicle_id)
end_index = routing.End(vehicle_id)
time_dimension.CumulVar(start_index).SetRange(
int(time_windows[depot][0]),
int(time_windows[depot][1])
)
time_dimension.CumulVar(end_index).SetRange(
int(time_windows[depot][0]),
int(time_windows[depot][1])
)
# Instantiate route start and end times to produce feasible times
for i in range(num_vehicles):
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(
time_dimension.CumulVar(routing.End(i)))
# Add capacity constraints
def demand_callback(from_index):
from_node = manager.IndexToNode(from_index)
return demands[from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
vehicle_capacities,
True, # start cumul to zero
'Capacity')
# Search parameters
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = time_limit
search_parameters.log_search = True
# Solve
solution = routing.SolveWithParameters(search_parameters)
if solution:
routes = []
arrival_times = []
total_distance = 0
for vehicle_id in range(num_vehicles):
index = routing.Start(vehicle_id)
route = []
times = []
while not routing.IsEnd(index):
node = manager.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
route.append(node)
times.append(solution.Value(time_var))
index = solution.Value(routing.NextVar(index))
# Add depot at end
node = manager.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
route.append(node)
times.append(solution.Value(time_var))
if len(route) > 2:
routes.append(route)
arrival_times.append(times)
# Calculate route distance
route_distance = sum(dist_matrix[route[i]][route[i+1]]
for i in range(len(route)-1))
total_distance += route_distance
return {
'status': 'Optimal' if solution.ObjectiveValue() > 0 else 'Feasible',
'routes': routes,
'arrival_times': arrival_times,
'total_distance': total_distance,
'num_vehicles_used': len(routes),
'objective_value': solution.ObjectiveValue() / 100.0
}
else:
return {
'status': 'No solution found',
'routes': None
}
# Example with visualization
def visualize_vrptw_solution(coordinates, routes, arrival_times, time_windows,
save_path=None):
"""
Visualize VRPTW solution with Gantt chart
Args:
coordinates: list of (x, y) coordinates
routes: list of routes
arrival_times: arrival times at each location
time_windows: time windows
save_path: path to save figure
"""
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))
# Plot routes
colors = plt.cm.tab10(np.linspace(0, 1, len(routes)))
for idx, route in enumerate(routes):
route_coords = [coordinates[i] for i in route]
xs = [c[0] for c in route_coords]
ys = [c[1] for c in route_coords]
ax1.plot(xs, ys, 'o-', color=colors[idx],
linewidth=2, markersize=8,
label=f'Vehicle {idx+1}')
depot = coordinates[0]
ax1.plot(depot[0], depot[1], 's', color='red',
markersize=15, label='Depot', zorder=10)
ax1.set_xlabel('X Coordinate')
ax1.set_ylabel('Y Coordinate')
ax1.set_title('VRPTW Routes')
ax1.legend()
ax1.grid(True, alpha=0.3)
# Plot Gantt chart
for idx, (route, times) in enumerate(zip(routes, arrival_times)):
for i in range(1, len(route) - 1):
customer = route[i]
arrival = times[i]
tw_early, tw_late = time_windows[customer]
# Draw time window
ax2.add_patch(Rectangle((tw_early, idx - 0.3),
tw_late - tw_early, 0.6,
facecolor='lightgray', edgecolor='black',
alpha=0.5))
# Draw arrival/service
ax2.plot(arrival, idx, 'o', color=colors[idx], markersize=10)
ax2.text(arrival, idx + 0.4, f'C{customer}',
ha='center', va='bottom', fontsize=8)
ax2.set_xlabel('Time')
ax2.set_ylabel('Vehicle')
ax2.set_title('Schedule (Gantt Chart)')
ax2.set_yticks(range(len(routes)))
ax2.set_yticklabels([f'Vehicle {i+1}' for i in range(len(routes))])
ax2.grid(True, alpha=0.3, axis='x')
plt.tight_layout()
if save_path:
plt.savefig(save_path, dpi=300, bbox_inches='tight')
plt.show()
# Complete example
if __name__ == "__main__":
# Generate Solomon-like problem instance
np.random.seed(42)
n = 26 # 1 depot + 25 customers
coordinates = np.random.rand(n, 2) * 100
# Distance and time matrices
dist_matrix = np.zeros((n, n))
time_matrix = np.zeros((n, n))
for i in range(n):
for j in range(n):
dist = np.linalg.norm(coordinates[i] - coordinates[j])
dist_matrix[i][j] = dist
time_matrix[i][j] = dist / 40 * 60 # 40 km/h in minutes
# Generate time windows (clustered)
time_windows = [(0, 480)] # Depot: 8-hour day
for i in range(1, n):
# Random center time
center = random.randint(60, 420)
width = random.randint(30, 90)
time_windows.append((center - width, center + width))
# Service times
service_times = [0] + [random.randint(10, 20) for _ in range(n-1)]
# Demands
demands = [0] + [random.randint(5, 20) for _ in range(n-1)]
vehicle_capacity = 100
num_vehicles = 5
print("Solving VRPTW with OR-Tools...")
result = solve_vrptw_ortools(
dist_matrix, time_matrix, demands, time_windows,
service_times, vehicle_capacity, num_vehicles,
time_limit=60
)
print(f"\nStatus: {result['status']}")
print(f"Total Distance: {result['total_distance']:.2f}")
print(f"Vehicles Used: {result['num_vehicles_used']}/{num_vehicles}")
print("\nRoute Details:")
for i, (route, times) in enumerate(zip(result['routes'],
result['arrival_times'])):
print(f"\nVehicle {i+1}: {route}")
print(" Arrival times:")
for j, (customer, time) in enumerate(zip(route, times)):
tw = time_windows[customer]
print(f" Stop {j}: Customer {customer} at time {time:.1f} "
f"(window: [{tw[0]:.1f}, {tw[1]:.1f}])")
# Visualize
visualize_vrptw_solution(coordinates, result['routes'],
result['arrival_times'], time_windows)
工具与库
Python 库
优化：
- OR-Tools（Google）：适用于实际 VRPTW 问题的首选工具（强烈推荐）
- PuLP：MIP 建模
- VRPy：支持时间窗的专业 VRP 库
- python-mip：其他 MIP 库
路径规划：
- OSRM：开源路径规划引擎（用于真实世界距离）
- Google Maps API：距离和时间矩阵
- Valhalla：开源路径规划引擎
可视化：
- matplotlib：基础可视化
- plotly：交互式甘特图
- folium：基于地图的可视化
基准实例
- Solomon 实例：标准 VRPTW 基准测试（R1、C1、RC1、R2、C2、RC2）
- Gehring & Homberger：大规模 VRPTW 实例
- Sintef：综合 VRP 测试集
常见挑战与解决方案
挑战：时间窗紧
问题：
- 窄时间窗会使问题受到高度约束
- 存在许多不可行的组合
解决方案：
- 使用注重时间的插入准则（Solomon 的 I1）
- 考虑使用带惩罚的软时间窗
- 采用先排序、后规划路线的方法
- 必要时允许更长的路线
挑战：时间跨度较长
问题：
- 时间窗口跨度较长（例如全天配送）
- 限制较少，但可能的解决方案很多
解决方案：
- 将距离／成本作为主要标准
- 考虑按客户的时间偏好进行聚类
- 平衡路线时长
挑战：硬性／软性时间窗口混合
问题：
- 部分客户有严格的预约时间
- 其他客户的时间安排较灵活
解决方案：
- 采用两阶段方法：先满足硬性时间窗口
- 对违反软性时间窗口的情况设置惩罚成本
- 在插入路线时优先安排硬性时间窗口客户
挑战：现实中的时间因素
问题：
- 交通状况会随一天中的时段而变化
- 行驶时间具有随机性
解决方案：
- 使用与时间相关的行驶时间矩阵
- 增加时间缓冲／松弛量
- 使用随机 VRPTW 模型
- 实时重新优化
输出格式
VRPTW 解决方案报告
问题实例：
- 客户：50
- 时间范围：上午 8:00 - 下午 6:00（600 分钟）
- 车辆：5（每辆载重：100 单位）
- 平均时间窗口宽度：60 分钟
解决方案质量：
| 指标 | 数值 |
|---|---|
| 总距离 | 892.4 km |
| 总时长 | 18.2 小时 |
| 使用车辆数 | 5 / 5 |
| 平均路线时长 | 3.64 小时 |
| 时间窗口违约次数 | 0（可行） |
| 平均等待时间 | 12.3 分钟 |
路线安排：
车辆 1： 上午 8:00 出发
| 停靠点 | 客户 | 到达时间 | 时间窗口 | 等待 | 服务 | 出发时间 |
|---|---|---|---|---|---|---|
| 0 | 仓库 | 8:00 | [8:00-18:00] | 0 | 0 | 8:00 |
| 1 | C12 | 8:23 | [8:15-9:15] | 0 | 15 | 8:38 |
| 2 | C7 | 9:05 | [9:00-10:00] | 0 | 12 | 9:17 |
| 3 | C34 | 9:42 | [9:30-10:30] | 0 | 10 | 9:52 |
| 4 | 仓库 | 10:35 | [8:00-18:00] | - | - | - |
路线距离： 187.2 km 路线时长： 2:35 总载荷： 97 / 100 单位
[其余车辆依此类推...]
统计数据：
- 准时到达率：100%
- 需要等待的提前到达比例：8%
- 时间窗口平均松弛量：23 分钟
要询问的问题
如果需要更多背景信息：
- 所有客户都有时间窗口，还是只有部分客户有？
- 时间窗口是硬性要求（必须满足）还是软性要求（违反时可以处罚）？
- 时间窗口通常有多宽？
- 规划时域有多长？（8 小时、12 小时、24 小时）
- 是否有实际行驶时间数据，还是需要根据距离估算？
- 服务时间是否显著？
- 首要目标是减少车辆数还是总距离？
- 路线是否有最长时长限制？
- 是否有驾驶员休息要求？
- 这是每日重复的问题，还是一次性问题？
相关技能
- vehicle-routing-problem：适用于不含时间窗口的基本 VRP
- traveling-salesman-problem：适用于单车辆路线规划
- pickup-delivery-problem：适用于带时间窗口的配对取送货问题
- capacitated-vrp：适用于侧重载重限制的 VRP
- multi-depot-vrp：适用于多仓库路线规划
- route-optimization：适用于实际路线规划应用
- last-mile-delivery：适用于末端配送优化
- fleet-management：适用于车队运营
评论
支持 Markdown