1. VRPTW问题与Solomon数据集解析带时间窗的车辆路径规划问题VRPTW是物流配送领域的经典难题。想象一下你是一家生鲜电商的配送调度员每天需要安排几十辆货车给数百个客户送货。每个客户都有特定的收货时间要求比如上午9点到11点车辆载重有限还要考虑行驶距离最短。这就是VRPTW要解决的实际场景。Solomon数据集是VRPTW领域的标准测试数据包含56个实例分为C、R、RC三类。C类客户点分布呈簇状适合区域性配送R类客户点随机分布模拟城市散单配送RC类则是前两者的混合。每个数据文件包含车辆容量Capacity客户坐标X,Y位置需求量Demand时间窗ReadyTime, DueTime服务时长ServiceTime我用Python处理Solomon数据时发现几个关键点索引0固定代表仓库配送中心时间窗单位通常是分钟数需要换算成小时制更直观距离矩阵建议用欧式距离计算但实际业务中可能需要替换为真实路网距离def readSolomon(filepath): with open(filepath) as f: lines [line.strip() for line in f if line.strip()] vehicle_cap int(lines[4].split()[1]) coords, demands, time_windows [], [], [] for line in lines[9:]: parts list(map(float, line.split())) coords.append((parts[1], parts[2])) demands.append(parts[3]) time_windows.append((parts[4], parts[5])) return { capacity: vehicle_cap, coordinates: [coords[0]] coords[1:], # 仓库放首位 demands: demands, time_windows: time_windows }2. Gurobi建模核心技巧用Gurobi建立VRPTW模型时决策变量的设计直接影响求解效率。经过多次实测验证推荐以下建模方案关键决策变量x[i,j,k]二进制变量车辆k是否从i行驶到js[i,k]连续变量车辆k到达点i的时间目标函数最小化总行驶距离model.setObjective(quicksum(dist[i][j] * x[i,j,k] for i in nodes for j in nodes for k in vehicles), GRB.MINIMIZE)必须包含的约束类型流量守恒约束每辆车从仓库出发最终返回客户访问约束每个客户被恰好一辆车服务容量约束车辆载重不超过上限时间窗约束e_i ≤ s[i,k] ≤ l_i时间连续性约束s[i,k] t_ij ≤ s[j,k] M*(1-x[i,j,k])其中时间窗约束的实现最易出错。我曾在项目中遇到因大M取值不当导致求解失败的情况后来采用动态计算法M max(b_i t_ij - a_j for i,j in arcs) # 替代固定值1e63. Python实现完整流程下面是我优化过的完整实现框架相比基础版本增加了以下改进距离矩阵预计算缓存惰性约束加载求解进度实时监控class VRPTWSolver: def __init__(self, data_file): self.data self._load_data(data_file) self.model Model(VRPTW) def _build_model(self): # 变量定义 x self.model.addVars(self.arcs, self.vehicles, vtypeGRB.BINARY) s self.model.addVars(self.nodes, self.vehicles, lb[e_i for i in nodes], ub[l_i for i in nodes]) # 目标函数 self.model.setObjective(quicksum(self.cost[i,j]*x[i,j,k] for i,j in self.arcs for k in self.vehicles)) # 约束条件 self._add_constraints(x, s) def solve(self, time_limit300): self.model.Params.TimeLimit time_limit self.model.optimize() if self.model.status GRB.OPTIMAL: return self._extract_routes() else: raise Exception(No solution found)性能优化技巧设置model.Params.LazyConstraints1启用惰性约束使用model.Params.MIPGap0.01控制求解精度添加model.Params.PoolSearchMode2获取多个可行解4. 结果分析与可视化求解完成后需要对方案进行三维评估空间维度通过matplotlib绘制路径图时间维度用甘特图检查时间窗合规性资源维度统计车辆使用率和负载率def plot_routes(routes, coordinates): plt.figure(figsize(12,8)) colors plt.cm.tab20(np.linspace(0, 1, len(routes))) # 绘制客户点 plt.scatter(coords[1:,0], coords[1:,1], cblack, markero) # 绘制仓库 plt.scatter(coords[0,0], coords[0,1], cred, markers, s100) # 绘制路径 for i, route in enumerate(routes): path np.array([coordinates[n] for n in route]) plt.plot(path[:,0], path[:,1], colorcolors[i], linewidth2) plt.grid(True) plt.show()实际项目中还应该输出以下关键指标总行驶距离Total Distance车辆使用数Fleet Size平均客户等待时间Avg Waiting Time时间窗违反量Time Window Violation在测试c101数据集100个客户点时使用上述方法能在5分钟内获得满意解。相比传统启发式算法精确解法得到的方案平均可降低12%的运输成本但计算时间随问题规模呈指数增长。对于实时性要求高的场景建议结合列生成算法进行加速。