电动车辆路径问题:可调鲁棒数学模型与算法

针对行驶时间不确定的允许部分充电的带时间窗电动车辆路径问题,考虑多面体不确定集度量行驶时间的不确定性,建立了一个可调鲁棒优化模型,设计了基于行生成和集划分的求解算法,采用标号法对路径的可行性进行判定,并将不可行的路径作为新的约束加入到模型中.数值实验表明,94%的算例可求得最优解,这验证了本算法的效率;利用多面体不确定集进行度量对总行驶距离和车辆总数目具有正向的影响;相比于普通鲁棒优化,可调鲁棒优化的求解结果有显著提高,可以提升车辆调度的灵活性.

需求响应公交和共享单车联合出行系统与优化

需求响应公交运营过程中车辆行程时间存在随机性与乘客出行需求差异大的问题,本文设计了一套需求响应公交和共享单车联合出行系统,针对需求响应公交在服务过程中行程时间随机性的特点,通过极小极大值后悔法构建车辆行程时间不确定的鲁棒优化模型,同时考虑车辆运营成本与乘客出行成本,实现需求响应公交的路径优化与乘客出行方案的制定。针对模型求解难点,提出了一种基于场景的改进自适应大邻域搜索算法,通过不同规模的算例验证模型与算法的有效性与高效性,并对共享单车使用费率与时间价值设计了多组敏感性测试。结果表明:相较于传统的需求响应公交系统,联合出行系统降低总成本最高可达28.6%,同时可有效减少乘客平均出行时间;此外,传统需求响应公交系统受随机行程时间影响带来的成本高于需求响应公交和共享单车联合出行系统,成本增幅在2倍以上,共享单车的加入可以有效提升系统在随机行程时间环境下的抗干扰能力。

基于计划延误成本的出发时间选择模型

出行时间不确定性对出行者造成诸多负面影响,其中之一就是计划延误成本增加。向出行者提供交通信息可减少出行时间不确定性的负面影响,减少计划延误成本。为了估计其负面效应和出行时间信息的价值,研究了一个出行时间不确定性下的出发时间选择模型。假定在不同的出发时间下,出行时间分布的形式不同。模型中出行者可得到交通信息服务系统(ATIS)提供的基于平均出行状况的交通信息或基于当日出行状况的交通信息,同时他对得到的信息有自己的感知值,基于此感知预测出行时间并选择出发时间。用算例反映了出行时间不确定性、不同信息状况和信息预测的质量对出行者广义出行阻抗的影响。结果表明交通信息的收益不应该只表现为传统的出行时间节省,它还能减少约30%~40%的计划延误成本。

考虑均衡性的不确定时间车辆调度问题研究

本文针对车辆调度实际运行过程中时间的不确定性问题,提出了包含时间窗口、车辆容量约束的配送服务线路随机规划模型,以最小化调用的车辆数目和运行距离,降低顾客的不满意度并且尽可能保证每条路线的均衡性。结合模型,给出了基于禁忌搜索的混合启发式算法,并且生成多个算例,依据算例结果说明模型和算法优越性,同时说明可以在不降低顾客满意度和不提高总运输成本的基础上,降低各条线路之间的时间差异。

不确定运行时间环境下的车辆调度问题及启发式算法

考虑到物流公司或者配送中心车辆实际运行过程中时间的不确定性,提出了配送服务线路包含时间窗口、车辆容量约束的随机规划模型,以最小化车辆运行成本同时尽可能降低所服务顾客的不满意度.同时,又稍作改进给出了平均-风险模型,由于VRP问题是NP难的,给出了一种基于禁忌搜索的启发式算法,并以北京市13个点的为例,给出求解结果.