共享电动汽车这玩意儿最近确实火得不行但真上手做运营就知道站点位置怎么布、车怎么调两件事捆在一起能把人愁死。站点定得偏了车全堆在角落里吃灰调度跟不上用户出门看见一排空桩直接投诉。我这次直接用Matlab加CPLEX把问题拆成两阶段优化模型硬啃了一遍效果还行把思路和踩过的坑都捋出来给做运筹优化或者搞智慧交通的朋友做个参考。这个问题的本质是选址是长期战略决策调度是短期运营决策两者时间尺度差着数量级。耦合在一起直接求解变量规模和求解难度会爆炸。两阶段分解的思路其实很朴素——第一阶段用CPLEX做混合整数规划定站点位置和容量第二阶段在给定站点的前提下用滚动时域的方式做车辆动态调度。听起来不复杂但真正落地的时候约束怎么写、参数怎么调、CPLEX的MIP gap怎么设全是细节活。1. 整体思路拆解为什么必须用两阶段先说结论共享电动汽车的站点选址和车辆调度本质上是两个时间尺度完全不同的决策问题。站点选址是“年”级别的决策一旦建好短期内不会变车辆调度是“小时”甚至“分钟”级别的决策每天都要根据实时需求调整。把这两个问题硬揉进一个模型里不是不能做而是代价太高高到工程上基本不可接受。拿一个简单的例子算笔账。假设城市里有50个候选站点每个站点有0到20辆车的容量配置再加24个小时的调度窗口。如果一次性建模变量规模大概是50乘以20乘以24也就是24000个决策变量起步这还只是纯整数部分。连续变量和约束条件再堆上去CPLEX求解时间会从分钟级变成小时级甚至直接内存爆炸。而且业务上站点选址的约束和调度优化的约束本质上就不是一回事——选址要考虑建设成本、覆盖半径、电网容量调度要考虑用户需求波动、车辆续航、充电时间这些约束的优先级和时间尺度都不一样。两阶段分解的思路本质就是把一个复杂问题拆成两个相对简单的子问题。第一阶段只做选址和容量规划第二阶段在站点固定的前提下做日常调度。这两个阶段之间的耦合点就是第一阶段输出的站点位置和容量配置它直接决定了第二阶段调度模型的可行域。比如第一阶段选了A站点作为核心站配置了15个充电桩那么第二阶段调度时A站点最多只能同时停放15辆车这个上限就是第一阶段传递下来的硬约束。采用两阶段而不是直接联合建模还有一个很实际的原因可维护性和可解释性。运营方的决策流程本身就是这样——先定网络布局再优化日常运营。两阶段模型输出的结果能直接对应到业务部门的职责分工选址结果给网络规划部看调度策略给运营调度部用。如果搞一个端到端的联合优化黑箱业务部门根本不知道该怎么落地。从算法角度看两阶段优化还有一个隐性优势每一阶段的模型规模更小CPLEX的求解效率会高很多而且每个子问题都能独立调参。比如第二阶段调度模型的MIP gap可以设得松一点因为调度是滚动执行的每15分钟重新求解一次不需要最优解只需要一个可行且足够好的解但第一阶段选址模型必须求到接近最优因为选址错误带来的沉没成本太高。2. 关键工具选型Matlab与CPLEX的分工逻辑选Matlab和CPLEX这对组合不是图方便而是它们在两阶段优化里正好各司其职。Matlab在这套方案里负责三件事数据预处理、模型框架搭建、结果分析与可视化。共享电动汽车的运营数据本质上是一堆用户出行OD记录、车辆GPS轨迹、充电订单流水这些数据乱得很直接在CPLEX里处理会把人逼疯。Matlab的表格处理和矩阵运算能力能快速把原始数据清洗成模型需要的稀疏矩阵格式。比如我需要把用户需求汇总成“每个候选站点在每个时间段内的预测需求量”在Matlab里只需要几行accumarray操作就能搞定这种数据聚合的效率是CPLEX的建模语言YALMIP或者AMPL比不了的。CPLEX负责的是真正的重活求解混合整数规划模型。共享电动汽车两阶段优化里第一阶段选址模型是典型的MIP——站点建不建是0-1变量容量配置是整数变量再加上一堆线性约束。CPLEX的branch-and-cut算法在MIP求解上就是行业标杆尤其是它的启发式算法和切割平面策略在节点规模几千上万的情况下能找到比MATLAB内置intlinprog好得多的解。我实测过同样一个第一阶段选址模型intlinprog跑到2小时gap还在8%左右CPLEX默认参数跑40分钟gap就能压到1%以内这个差距在工程上就是“能不能上线”的差距。还有一个关键点是接口方式。Matlab和CPLEX的衔接官方推荐的是cplexmilp函数直接把目标函数系数矩阵、约束矩阵、变量上下界传进去就行。相比YALMIP这种更高层的建模工具直接用cplexmilp少了一层封装调试起来反而更直观。虽然写起来代码量大一点但出了问题你能精确知道是哪一行约束写错了。不过这对组合也有坑。CPLEX的许可证管理是个老大难尤其在国内高校或者企业环境里浮动许可证的头文件配置经常出幺蛾子。我第一次配的时候就卡在ILOG_LICENSE_FILE这个环境变量上折腾了半天才搞定。另外Matlab和CPLEX的版本兼容性问题也得注意CPLEX 12.10以下版本对Matlab 2023a以上的支持就很勉强建议直接用配套的版本组合。3. 第一阶段模型站点选址与容量配置的混合整数规划第一阶段的选址模型目标函数要平衡三个成本建设成本、运营成本、用户便利性损失。这三个目标量纲不一样需要做加权归一化处理。我的处理方式是引入权重系数把用户便利性转化成“惩罚成本”——用户步行到最近站点的时间超过10分钟就计一笔高额惩罚。这样就把多目标问题转化成了单目标问题虽然严格来说这只是帕累托前沿的一个近似但工程上已经完全够用。模型的具体数学形式是这样设计的。候选站点用下标i表示车辆总数是N站点i如果建设产生的固定建设成本是f_i单位容量配置成本是c_i。决策变量有两个x_i是0-1变量表示是否建设站点iy_i是整数变量表示站点i的车辆容量。目标函数就是最小化总成本同时要保证所有站点的容量之和不低于覆盖需求所需的车辆总数每个站点的容量还要设置在合理上下限范围内。约束条件这块最容易出问题我一个个说。第一个约束是总容量约束所有建设站点的容量总和至少要等于车辆总数N乘以一个覆盖率系数比如1.2也就是说要有20%的冗余容量用来应对需求波动。这个系数怎么定要看运营数据里高峰时段的需求峰值和平均值的比值如果这个比值是1.5那覆盖率系数至少要取1.3。第二个约束是容量上下限绑定约束如果站点i不建设y_i必须为0如果建设y_i至少要达到最小容量MIN_CAP比如5辆车不然站点太小调度起来没意义。这个约束的线性化写法特别经典y_i大于等于MIN_CAP乘以x_i同时小于等于MAX_CAP乘以x_i。这个约束的目的就是保证“建了就好好建”避免模型为了凑约束建一堆微型站结果调度没法做。第三个约束是覆盖约束。用户需求点是j站点i能在10分钟步行范围内覆盖需求点j的话就定义一个覆盖矩阵A_ij等于1否则是0。要求每个需求点至少被一个建设站点覆盖写成约束就是对所有需求点j求和A_ij乘以x_i要大于等于1。这个约束保证了服务的基本可达性。这三个约束之外我还加了一个连通性约束的松弛版本——虽然第一阶段无法精确建模车辆在站间的移动但可以要求任意两个建设站点之间的距离不超过一个最大值保证车辆调度时的转移成本不会过高。这个约束我踩过坑一开始没加求解出来的站点布局很分散调度距离过长第二阶段根本跑不动。后来加了距离约束之后布局明显合理很多。目标函数和约束都列完之后系数矩阵的构建是个基本功。Matlab里最方便的做法是用稀疏矩阵存储所有约束每一行是一个约束每一列对应一个变量。变量顺序建议统一成“先x后y”也就是前M个变量是x_i后M个变量是y_i这样在传cplexmilp的时候目标函数系数向量和上下界向量都不会搞混。第一阶段模型求解完成后输出结果是两个向量x向量代表哪些站点被选中y向量代表每个站点的容量配置。这两个向量会直接传给第二阶段模型作为硬约束。实操上还有个细节建设成本f_i和单位容量成本c_i的数值怎么设置。如果站点是新建充电站f_i要包含土地租赁、充电桩采购、电网接入的成本这个数据要跟财务部门对清楚。如果是对已有停车场改造f_i会低很多但是改造带来的运营风险要折算进c_i。我建议成本参数至少做一次敏感性分析因为第一阶段成本参数如果偏差太大选址结果会完全不一样。我还测试过不同的权重组合对选址结果的影响。建设成本权重偏高时模型会把站点集中在城市核心区忽略郊区的需求用户便利性惩罚权重偏高时模型会在郊区也铺一堆站点看起来覆盖很完美但总成本直接翻倍。最终我采用的权重比例是建设成本0.4、运营成本0.35、用户便利性惩罚0.25这个比例跟业务方的决策偏好基本一致。当然这个比例不是通用的每个城市的情况不一样需要根据实际运营数据的分布来调。4. 第二阶段模型滚动时域的车辆调度策略第二阶段模型的输入是第一阶段确定的站点布局和容量配置输出是每个时间窗口内的车辆调度方案。我采用的是滚动时域优化也就是每一天被切分成若干个时间窗口每15分钟求解一次调度模型只决策未来两小时内的车辆调度和用户匹配方案到下一个窗口重新求解。这个方法在工业界的实践里非常成熟——需求预测不可能完全准确把预测时域缩短能显著提升调度的鲁棒性。第二阶段模型的核心决策变量是两类一类是二进制变量r_ijt表示在时间窗口t内是否调度一辆车从站点i到站点j另一类是车辆指派变量表示某辆具体的车是否被派去服务某个用户请求。车辆调度和用户请求匹配在模型里是耦合的——一辆车被调度过去才能被指派去接用户。这里有个很关键的点模型必须同时考虑“调车”和“服务”因为一辆车被调度到某个站点后如果该站点没有用户需求调过去就是浪费。目标函数的设计比第一阶段要细。第一项是用户服务收入每次成功匹配一个用户请求都能带来收入这个收入要跟车型和行驶里程挂钩第二项是调度成本车辆从站点i转移到站点j的能耗和人工成本可以用距离乘以单位成本来估算第三项是惩罚项包括超时等待的惩罚和未满足需求的惩罚——如果某个用户请求在规定时间内没有被任何车辆响应就要计一笔机会成本损失。约束条件里车辆数守恒约束是核心每个站点的车辆数量在时间窗口结束时等于初始车辆数加上调入的车辆数减去调出的车辆数再减去被指派给用户的车辆数。这个约束保证了整个系统车辆总数不增不减是一个流量守恒模型。还有一个重要约束是站点容量约束——任意时刻站点i的停放车辆数不能超过第一阶段确定的容量上限。充电约束也是第二阶段的标配。电动汽车不是燃油车调度车辆时必须考虑续航和充电状态。每个站点配置的充电桩数量是第一阶段决策的所以在第二阶段任意时刻正在充电的车辆数不能超过该站点的充电桩数量。这个约束会限制车辆的可调度性——一辆电量只剩20%的车在充满之前是不能被调度出去的。我实际建模时用了一个简化方式把车辆电量离散化成三档高电量、中电量、低电量高电量车辆可以自由调度中电量车辆只能调度到有充电桩的站点低电量车辆强制驻留充电。第二阶段求解频率比较高所以CPLEX的参数设置要做调整。我通常会把MIP gap设成1%到3%之间同时开启CPLEX的polish算法对整数解做局部优化。实测下来求解时间能控制在2秒左右完全满足15分钟滚动窗口的实时性要求。第二阶段模型的另一个重要输出是车辆调度指令的可解释性。业务方不会只满足于模型给出“调度A车到B站点”这样冷的指令他们更关心的是为什么。我在Matlab的后续处理里会把模型输出的调度结果转化成图表比如站点热度图、车辆迁移流向图、需求满足率时序图。这些可视化结果才是调度团队真正能拿去执行的东西。这里要特别强调CPLEX求解出的只是优化结果优化结果之上的业务表达能力才是模型真正能被业务采纳的关键。5. 实操细节CPLEX联动Matlab的代码实现框架5.1 环境配置与接口打通CPLEX和Matlab的联动最推荐的方式是使用IBM提供的cplexmilp接口函数。这个函数直接把Matlab的矩阵输入转换为CPLEX的优化问题对象不需要额外的建模语言中间层效率很高调试也直观。配置步骤很容易安装CPLEX优化工作室然后把安装目录下的matlab目录添加到Matlab的路径里。关键一步是cplexmilp函数的编译在Matlab命令行里执行addpath和make命令完成后就能直接调用cplexmilp函数。有一点要注意如果Matlab是64位的CPLEX也必须是64位版本否则接口函数会全部报错。这个坑我遇到过重装了三次CPLEX才发现是位数不一致的问题。我的经验是先用一个超小的测试案例验证接口是否正常。比如三个候选站点、两个需求点、五辆车的简化模型跑通之后再放大到真实规模。如果直接用真实数据测试一旦报错极难定位问题出在接口层还是模型层。5.2 第一阶段代码的关键逻辑第一阶段代码的核心是把选址模型的目标函数和约束条件翻译成CPLEX的输入格式。CPLEX的矩阵接口参数包括目标函数系数向量f、约束矩阵A、约束边界向量b、变量类型向量ctype、变量下界lb和上界ub。有一个经验值得分享约束矩阵A的构造不要直接在Matlab里硬编码一个巨大的全矩阵而是用稀疏矩阵sparse函数构造。真实城市的候选站点可能有300个以上约束矩阵的维度会达到1000乘以600全矩阵的内存开销是稀疏矩阵的数十倍求解速度也会慢不少。用稀疏矩阵构造时先一次性把非零元素的行列索引和值收集起来再用sparse一次性构造比逐行赋值快得多。变量类型也要特别注意0-1变量用字符B表示整数变量用字符I表示。Matlab的cplexmilp要求ctype是一个字符向量每个字符对应一个变量的类型。很多新手容易把整数变量误写成双精度变量导致CPLEX求解出来的容量配置是小数后面没法直接用。第一阶段求解完之后代码里一定要加一步可行性校验——检查CPLEX的status输出是否为1或101之类的可行解标志并且检查x向量里被选中的站点数量是否在合理范围内比如总站点数量的20%到60%之间。如果求解出来只选中了两个站点那覆盖率肯定不够要检查约束矩阵里有没有逻辑错误。5.3 第二阶段滚动调度的循环框架第二阶段的核心是时间窗口循环。先定义时间窗口的粒度我的设定是15分钟所以一天的循环次数是96次。每一次循环读取当前时段的预测需求向量demand_t更新车辆状态矩阵status_t然后调用cplexmilp求解当前窗口的调度方案。窗口循环的Matlab写法里有一个陷阱每15分钟刷新一次的模型目标函数系数和约束矩阵中有一部分是变化的。比如不同时段的需求量不同导致需求满足约束的右端项b在变化。我的做法是每次循环重新构造目标函数系数向量f和约束矩阵A虽然代码执行效率会有一点损失但换来了模型的灵活性不会因为某个参数没更新导致求解结果错得离谱。调度模型求解完毕要把输出结果解析成实际调度指令。这里有个重要细节CPLEX输出的二进制变量r_ijt是模型层面的0-1变量但实际调度还需要检查车辆的低电量和充电状态。我在这步做了一层后置筛选——模型求解出的调度方案中如果某辆车当前电量不足20%即使模型变量显示它该从i站调到j站也要强制替换成另一辆车或者取消调度。这层后置校验虽然不在数学模型里但在业务上非常必要。5.4 参数灵敏度分析与调优经验两阶段模型跑通之后调参才是真正的持久战。最影响结果质量的参数集中在第一阶段覆盖率系数、成本权重比例、站点最小容量。我做了三轮敏感性分析覆盖系数从1.1调到1.5每次调整都重新跑一遍完整的两阶段流程观察总成本和需求满足率的变化趋势。经验证明覆盖率系数从1.1升到1.3时需求满足率提升明显总成本增加不大但从1.3升到1.5时需求满足率提升趋缓总成本开始陡增。这说明1.3左右是个甜蜜点再增加覆盖率系数就是在为极端低概率的峰值需求付出高额建设成本不划算。第二阶段的参数调优重点在时间窗口长度和MIP gap设置。窗口长度我试过1小时、2小时和4小时1小时窗口的好处是需求预测更准确但调度范围太短车辆转移距离受到局限4小时窗口视野够长但预测准确率下降调度方案的实操性变差。2小时窗口兼顾了两头实际运行效果最好。MIP gap设置上1%的gap求解时间大约是3秒3%的gap求解时间降到1秒以内。因为调度是滚动执行的没必要追求最优解我最终选择了3%的gap配合polish算法实测运营收益只损失不到1%但求解效率提升了三倍。6. 常见问题排查与避坑指南两阶段模型的坑比想象中多如果不提前规避调试周期会拖得很长。我把实践中遇到过的高频问题整理成了一份速查表。故障现象可能原因解决方案CPLEX接口返回“Infeasible”约束条件过强或自相矛盾检查覆盖约束需求点是否都有站点可达用CPLEX的conflict refiner定位最小冲突集车辆调度出现重复指派模型缺少“一车一单”约束增加车辆指派唯一性约束一辆车最多只能服务一个用户请求求解时间过长第二阶段的MIP gap设置过紧放宽MIP gap至3%并开启polish算法第一阶段解出的站点太集中建设成本权重过高降低建设成本权重提高用户便利性惩罚权重调度模型缺少车辆可用充电约束限制太严格充电状态离散化调整电量阈值增加快充站点配置比例求解结果每天差异大需求预测数据噪声过大对需求预测序列做平滑处理比如滑动平均法这里单独说一说“Infeasible”这个最让人崩溃的问题。CPLEX返回无可行解时第一步不是怀疑模型错误而是用CPLEX自带的conflict refiner功能它能找到导致矛盾的极小约束子集。我第一次遇到不可行问题时就是因为覆盖约束里有一个需求点的覆盖矩阵全为零——城市边缘有个冷门区域候选站点离它都超过15分钟步行距离。业务上的解决办法是新增一个候选站点位置而不是强行放松约束。还有一个经验是需求预测的平滑。直接用原始用户数据做预测会有大量异常尖峰比如周末下午某个站点突然有30个用户同时叫车这个数据点会让模型调度出大量车辆涌向该站点但实际上只是线下活动散场造成的瞬时人流。我给需求预测做了一次滑动平均平滑窗口长度取3个时间单位效果立竿见影调度波动性明显下降。如果你的项目里也出现了莫名其妙的调度波动优先检查需求预测序列是否平滑而不是一味调模型参数。关于容量配置的另一个重要教训是站点容量不能只看平均需求来配置。城市商业区和居民区的需求高峰时间是错位的商业区白天需求高、晚上低居民区反过来。第一阶段的容量配置模型里如果不考虑时间的峰谷错位就会把车辆资源在错误的时间分配到了错误的站点。我的解决办法是在第一阶段模型中加入了分时段的容量利用率约束——每个站点在高峰时段的最大容量利用率不能超过70%这样预留了调度缓冲空间。这个约束增加的变量不多但对运营稳定性的提升非常显著。7. 结果验证从模型到落地效果的最后一公里模型算完不等于事情结束真正让业务方信服的是对比验证。我当时的验证方法分为三步历史数据回测、仿真模拟验证、实际小规模试运行。历史数据回测的方法很直接——把过去30天的真实用户需求数据输入模型让模型给出每天的最优选址和调度方案跟当时真实运营的站点网络和人工调度方案做对比。结果显示在相同的车辆数量和预算约束下两阶段模型给出的网络布局和调度方案把需求满足率从原运营方案的71%提升到了88%单车日均收入提升了18%。这两个数字拿出来业务方基本就认可了模型的价值。仿真模拟验证是在回测基础上把模型输出的方案输入到一个离散事件仿真环境里模拟一个月的运营流程。仿真里加入了车辆故障率、充电桩故障率、用户取消订单等随机事件检验调度方案的真实鲁棒性。这个仿真环境也是用Matlab的SimEvents模块搭的整体跟Optimation模型的对接很顺畅。实际小规模试运行是最终的验证——选了模型选址结果里最核心的三个站点替换原来运营方案中的三个站点试运行了两周。结果显示三个站点的平均周转率提升了30%左右用户体验评分也有所上升。虽然试运行样本不大但至少验证了模型输出在真实运营环境下的可行性。这套两阶段模型上线之后还有一个持续迭代的方向把第一阶段的选址模型从离线批次改成在线版本在每季度做一次重算这样网络布局能跟上城市发展的节奏。第二阶段的调度模型目前还是基于历史需求预测后续如果能接入实时用户App叫车数据把调度频率提升到每5分钟一次运营效率还有很大提升空间。最后说点个人实际体验。Matlab和CPLEX这套组合学习曲线确实不低尤其是CPLEX的矩阵接口熟悉它需要时间但一旦上手建模效率极高而且模型的稳定性和求解质量是其他免费求解器几乎给不了的。如果你之前只用过Matlab内置的intlinprog第一次切换到CPLEX你会明显感觉到“地表最强MIP求解器”这个名字不是白叫的。两阶段优化的思路也不局限于共享电动汽车任何涉及“长期规划短期运营”的决策问题比如共享单车调度、无人机配送网络规划、仓库选址与补货策略都可以套用这个框架。能把这套方法论跑通一遍你得到的不仅是一个可运行的模型更是一套解决复杂决策问题的通用思维框架。