一类带时间约束指派问题的分枝定界算法

通过对模型特征分析,提出了一种分枝定界算法,实例应用及算法复杂性分析证明了该算法的有效性.     

有向网络上两顶点间最短路径的双向搜索算法

提出了一种求解有向网络上两顶点间最短路径的双向搜索算法,经理论证明和实际应用,该方法较原Ｄｉｊｋｔｒａ算法可平均提高８倍的计算效率。     

多目标模糊柔性作业车间调度问题优化

为降低柔性作业车间调度中的能耗,针对实际制造车间中工序加工时间和交货期的不确定性,将加工时间和交货期采用模糊数表示,建立以完工时间、平均满意度和最小满意度为柔性作业车间调度问题的多目标函数。同时设计了邻域遗传算法(GANS)求解该问题,算法采用机器选择的方法产生初始种群,并采用工序插入式方法对染色体进行解码;采用动态交叉概率及改进精英保留策略来保证种群的多样性和加快算法的收敛速度;并提出一种基于移动模糊关键工序的邻域结构来加强算法的局部搜索能力。最后通过数值实验验证了模型和算法的有效性和可行性,并对4个基准问题进行测试。结果表明:该算法在求解的精度、鲁棒性和解集的分布性方面与传统算法相比具有一定的优势,是一种有效的求解模糊柔性作业车间调度问题的新方法。     

交通网络k-短路径与最小支撑树问题

为了给交通管理部门提供多个路径诱导信息,基于经典的最短路径算法——Dijkstra算法,研究了赋权交通网络的k-短路径问题。k-短路径问题是在网络G中求出给定起讫点对之间的k条路径P1,P2,…,Pk,满足W(P1)≤W(P2)≤…≤W(Pk),其中W(*)表示路径*的权值。在网络G的基础上,通过对G的点、边重新划分以及对边上的权值重新赋值,构造出了1个新的网络G′并讨论了它的几个性质。从而将G的k-短路径问题转换为求解G′的最小支撑树问题,进一步,最小支撑树问题又等价于求G′中一条边的权值。研究结果表明:由于最小支撑树问题具有多项式算法,得到关于k-短路径问题的多项式算法,其时间复杂性为O(k(m+nlg(n))),m和n为G的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。     

区域物流运作战略与平台规划

区域物流是国家经济的重要组成部分,在区域物流战略规划中需要以合理化为主要内容进行设计,本文就区域物流的特点,规划内容,程序做了归纳处理,并描述了操作流程图,以及AHP方式下的决策过程。最后分析区域物流规划中可能遇到的问题。     

基于蚁群算法的多属性路径选择模型

针对交通网络中多属性条件下的路径选择问题,本文基于蚁群算法讨论了给定起讫点对之间综合最优路径的实现步骤.首先将蚁群按照所给的属性集合分为若干个子蚁群,每个子蚁群给定不同的属性目标.然后在每一次循环的过程中,子蚁群按照既定的属性进行路径选择,在所有的子蚁群完成一次循环后,全局更新信息素.可知,各个子蚁群既按照自己的目标搜索最优解,同时各个子蚁群之间又互相影响,使得所得的结果不仅对于每个属性目标较优,而且综合效果也很好.最后进行了仿真实验并分析了结果.     

成网条件下地铁-公交复杂网络的末班车衔接优化

为解决城市交通末班车衔接效率和成功率低的问题,在城市轨道交通末班车衔接研究的基础上,通过提出末班车衔接矩阵的网络表示法,研究以实际线路末班车运营时刻表为基础的地铁-公交末班车换乘衔接的双层复杂网络模型。同时,使用ucinet计算网络特征参量(度、最短路径、衔接比例)的值并将其作为衡量城市交通网络末班车换乘衔接效率、次数以及成功率的评价指标。针对换乘失败率较高的车站,通过延后其所在线路的末班车时刻优化路网的末班车时刻表。最后,对成都市进行实例研究,系统验证了加入公交末班车网络后可使得换乘站的度大幅增加,最短路径无明显增加,衔接成功率由25.4%大幅提高至39.1%。结果表明了地铁-公交双层复杂网络的末班车衔接效率和成功率相较于城市轨道交通网络的优越性。同时,延后换乘失败率较高车站的末班车时刻,使得地铁-公交双层复杂网络的末班车衔接成功率由39.1%提高至40.7%,改善了城市交通末班车的衔接状况,提高了城市交通末班车的服务水平。     

多目标网络相异路径的Pareto解及其遗传算法

网络相异路径一般是多目标约束路径问题,具有重要应用价值.然而,由于问题的难解性,总是利用妥协思想将其转换为单目标问题求解.本文建立了双目标相异路径的一种优化模型,给出了模型求解过程中伪理想点的概念,提出了基于小生境共享竞争复制算子的遗传算法,该算法可求解多目标优化问题的 Pareto 解集.最后,给出了一个计算分析实例.