多目标最短路径模型及算法

为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.     

一种基于决策者风险偏好的危险品运输路径优化问题研究

在现实情况中,决策者风险偏好的差异性往往会对危险品运输路径优化产生影响。本文将决策者的风险偏好分为远期风险厌恶型、近期风险厌恶型和风险中性三种类型,将决策者风险偏好下的路径风险值、运营时间和运营成本的最小化作为危险品运输路径优化问题的目标函数,依此建立多目标决策模型。通过选择合适的加权开方乘方数将多目标决策模型中的目标函数转化为单目标函数,然后用标号算法求解最优折衷解,最后通过实例进行编程计算,验证了模型和算法的有效性。     

随机时变特征下基于行程时间的路径选择算法

基于南京市实测数据分析了道路交通流实际随机、时变特征,证实现有行程时间最短路径算法相关研究中对道路交通流的随机、时变特征的假设与实际不符.以反例论证道路交通流实际随机、时变特征下,自适应算法(Adaptive Routing Policy)在求解行程时间最短路径方面的无效性.针对交通模式时段内道路交通流随机、时间无关的特征,以及路段行程过程中行程时间的确切概率分布难以知晓的实际情况,提出基于历史概率分布的历史期望行程时间最短k路径基础上的考虑风险衡量及当前道路实际交通流状况的路径选择算法.     

优化蚁群算法在最短路径诱导中的应用

最短路径算法在许多应用领域和研究中起着十分重要的作用。现有文献对最短路径问题提出了大量的优化求解方法和算法,大部分研究仅针对固定权值网络,对权值随时间变化等时变情况考虑较少。在通信系统、智能交通系统等实际网络及应用领域中,随着时间的变化,边的权值往往也同时改变。因此,时变网络中最短路径求解问题的研究更具有实用意义。针对一般算法存在的缺陷,现提出三点优化,使算法既能避免陷入局部最优解,又能更快地收敛到全局最优解。     

�����������绷����Σ��Ʒ��·����·������

随着经济的发展,危险品的运输量在大幅的增长,危险品对环境和人类的潜在风险在扩大。危险品运输事故一旦发生事故,可能会造成惨重的人员伤亡、长久的环境污染及巨大的经济损失。选择一条最佳的危险品运输路径,确保运输安全具有重要的意义。在相对发达的运输网络环境下通过最小化运输风险、最小化运营时间及最小化敏感目标人数,建立了危险品公路运输路径多目标决策模型,并利用基于决策者偏好信息的权重信息和开方乘方集成算子对3个目标函数进行集成,然后用扩展标号法计算最优折衷解,最后用一个例子验证了模型及算法的正确性和有效性。该方法有助于决策者在发达运输网络环境下选择合理的运输路径。     

基于Pareto蚁群算法的船舶风险规避路径优化

船舶在海上航行时,一直面临着海上运输风险的威胁,为了降低海上运输风险同时考虑船舶经济效益,本文建立了以运输风险最小和航行成本最小的双目标路径优化模型,实现船舶风险规避.运用栅格法构建环境模型,为相应的栅格路径赋予航行成本和运输风险,并设计了一种基于Pareto最优解集和NSGA小生境方法的多目标蚁群算法.以印度洋海域的2条航线为案例,以经典单目标蚁群算法为对比,验证了模型和算法的有效性.结果表明,该模型和算法在解决船舶风险规避路径优化问题上具有良好的效果,能为决策者制定船舶海上运输风险规避路径提供决策参考.     

随机时变路网环境下稳健路径选择及实证研究

交通拥挤、天气、突发事故等不确定性因素影响着城市区域之间的路网提供的 连通服务水平.本文对城市片区间道路连通路径选择进行研究.根据随机时变网络描述和 稳健路径选取原则,建立了最优化模型,并采用改进的Dijkstra 算法.通过深圳实例计算, 分析了出发时刻与最短路径行程时间和路段构成之间关系,并与确定性时变路网环境下 进行计算结果对比.结果表明,随机时变路网环境下鲁棒性最优算法选择稳健路径具有合 理性和可行性,可以很好地应用到区域动态连通情况的研究.     

时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

时变单车路径问题建模及算法设计

讨论了一类时变单车配送路径优化问题。综合考虑车辆行驶速度随时间、路段不同而变化的特点,及车辆为多条路线上的客户提供服务时对车辆路径优化的影响,建立了以配送完成时间最早为优化目标的时变单车配送路径优化模型。在行驶时间满足FIFO规则下,设计了基于Inver-over操作的PSO启发式算法及满足贪婪配送策略下的动态规划精确求解算法,并讨论了增加贪婪补货策略的单车配送路径问题解与原问题解的关系。最后分别用两种算法对算例进行求解,并通过对求解优化结果及计算时间的对比分析验证了IOPSO算法的有效性。     

有容量约束车辆路径问题的多目标遗传算法

针对有容量约束车辆路径问题,提出了基于Pareto方法的多目标优化遗传算法.该算法引入基于擂台法的Pareto锦标赛选择算子,避免了求解非凸解的困难.采用最邻近算法和扫描算法构造初始种群及引入启发式交叉算子来加快算法的收敛速度.通过E-n30-k3算例实验表明:应用该算法得到的Pareto解集,为决策者提供了多种途径有效解决有容量约束车辆路径问题.