带多重选择的最短路问题:复杂性和算法

本文提出了带出重选择的是短路问题,建立了该问题的数学模型,利用背包问题的一个变形问题－带限制选择的背包问题,证明了该问题是ＮＰ－Ｃ的,最后利用动态规则给出了一个伪多项式算法,其时间复杂性Ｏ（Ｃｈｍｎ）,其中ｈ是最大的选择重数。     

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题,证明了该问题是ＮＰ－完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法,对最小点成本最短路问题,给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。     

带点弧约束的最短路问题：复杂性和算法

本文首先提出了带点弧约束的最短路问题,证明了该问题属于ＮＰ－Ｃ,然后给出了一个伪多项式时间算法．最后给出了最小成本最短路问题的一个时间复杂性为Ｏ（ｎ２）的算法．     

物流运输网络多目标最短路问题的模糊满意解

本文对物流运输网络多目标最短路问题进行了研究。提出了一种求解多目标最短路问题的目标集成方法和对集成后目标函数求解的扩展标号法。在将多目标转化为单目标时,综合考虑了每个目标的边缘评价和所有目标的整体评价因素,通过对每个目标的权重分配将决策者的偏好充分体现到决策过程中,采用广义的模糊目标集成算子形成了相应的折衷规划模型。最后,通过实例对本文所提方法进行了说明。     

求最短路问题的改进算法

本对图论中含有负权的最短路问题的算法进行了讨论，给出了一个具有“可节省存储空间、提高运算速度、易编程实现”等优点的改进算法（算法三），并通过例题进一步验证了该改进算法的优越性，具有一定的现实意义。     

求最短路问题的改进算法

本文对图论中含有负权的最短路问题的算法进行了讨论 ,给出了一个具有“可节省存储空间、提高运算速度、易编程实现”等优点的改进算法 (算法三 ) ,并通过例题进一步验证了该改进算法的优越性 ,具有一定的现实意义 .     

一种最短路问题的遗传算法求解

针对最短路径问题,在分析传统遗传算法不足的基础上提出了变长染色体遗传算法(ClvGA),详细论叙了其编码、基因插入(删除、变异)算子的设计,最后通过两个网络对ClvGA进行了实验仿真,结果表明:该方法在最短路径问题上表现出较好的鲁棒性.     

具有最大能量的最短路

本讨论一类新的赋权图,称为双权图,Ｇ＝（Ｖ,Ｅ;ω,ｃ）,ω称为权函数,ｃ为容量函数。并给出了Ｇ中两顶点ｕ与ｖ之间具有最大能量的最短路的算法。     

用嵌套插队算法解决TSP问题

本提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的。TSP问题，直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例。嵌套插队算法(NQJA)能获得质量高于名的启发式算法的解。另外，用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的，但其思想也可以给求解其他NP难解的组合优化问题以启发。     

On the Generalized Elementary Shortest Path Problem: A heuristic approach

We introduce the generalized elementary shortest path problem (GESPP) where in addition to the features of the shortest path problem, nodes belong to predefined non-disjoint clusters. Each cluster is associated to a profit to the cost function, obtained if at least one element in the cluster appears in the path. Several applications can be considered as school bus routing, pricing problems, or telecommunication network design. Thus, depending on the case, clusters could be interpreted as groups of nodes with linking features as, for example, being easily reachable from each other, or some kind of coverage guarantee. We compare the GESPP to similar problems in the literature and we propose a two-phase heuristic algorithm for graphs including negative cycles. Tests on random instances with up to 100 nodes show an average gap of 0.3% to the best known solutions computed in 2.8s in average.     

汽车行驶的时间问题

就d>2R的情形解决如下组合几何极值问题:某平原地区有一个很大的湖泊.湖泊周围有两个村庄A,B.村庄A到村庄B的直线距离为已知.一辆汽车从A村庄出发以已知匀速速度驶向村B庄.问:若这辆汽车以最短路径行驶到达B村庄至多需要多少时间?     

非平衡交通分配的拟Frank-Wolfe迭代算法

提出了基于最短路动态生成的一种新的非平衡交通分配迭代算法.在每轮迭代中,将按全有全无方法在当前最短路上分配的交通量与前一轮迭代所得到的交通量加权组合,而各O-D对的加权系数则依据Logit原则来确定.和Frank-Wolfe算法不同,不必通过一维搜索确定加权系数.同时又避免了Logit方法要求枚举所有路径的困难.本文还证明了算法的收敛性,而计算实例显示,由本算法所得结果与平衡交通分配非常接近,因而它是一个高效而可靠的交通分配算法,适用于大、中型道路交通网络的交通分配计算.     

一类非确定型多目标指派问题及其算法研究

研究每个人承担的工作数不受限制,但每项工作只能由一人承担的情况下,如何给每个人指派工作,才能使完成所有工作的工期最短,并且在此前提下,使完成所有工作的总用时最少.针对这种多目标非确定型指派问题,本文给出了一种向量标记算法,这种算法不但使用方便,而且有很好的运算效率。     

基于模拟扩散的最短路径新算法

基于模拟水流扩散的自然现象,提出了一种寻求最优路径的新算法,介绍了该算法原理和具体计算过程,验证了该算法的正确性和合理性.     

基于油耗的带有车容限制弧路径问题的模型及优化

提出了一种基于油耗的带有车容限制的弧路径问题(Capacitated Arc RoutingProblem,CARP),建立了以降低油耗为目标的问题模型,构造了相应的遗传算法.基于标准测试问题,同传统以距离为优化目标的遗传算法求得的油耗进行比较,实验结果表明,此算法可以快速、有效的求得以油耗为优化目标的CARP问题的优化解,为实际中降低车辆运输服务成本提供了较好方案.     

对Floyd算法的两点注记

本给Floyd算法配置了一种更便于使用的路径标记方法,还给出了在无向网络上减少Floyd算法的计算量的方法。     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

一类网络最优路径的双向模拟扩散算法

基于模拟扩散算法的基本原理,文中提出了一种双向寻求网络最优路径的扩散算法,并介绍了该算法原理和具体计算过程,验证了该算法的正确性和合理性。该算法具有并行计算的能力,适合于分布式计算机,寻求大型复杂网络的最优路径。