考虑拥堵情形的污染路径问题及其求解算法

摘要

考虑拥堵情形的污染路径问题是经典的带时间窗车辆调度问题的一个扩展。该问题的目标函数包括车辆行驶产生的排放成本，约束条件则包括交通拥堵带来的车辆行驶速度约束一一该拥堵只与时间有关（time-dependent），且拥堵的开始时刻和结束时刻都可以自由设定。首先提出了拥堵情形下的行驶时间计算模型，在此基础上建立污染路径问题的线性规划模型，并提出了基于节点时间窗变换以及速度和出发时间优化的求解算法。算例结果验证了该算法的高效性。