旅行商问题的遗传算法

旅行商问题属于ＮＰ问题，现在还没有找到有效的解法。本文应用遗传算法对解决此类问题的有效性作了探讨。文中对遗传算子的应用，编码，参数选择及其对收敛的影响等问题作了分析与探讨。     

具有服务时长的在线TSP问题

针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据.     

求解TSP的离散人工蜂群算法

针对旅行商问题,提出了一种新型的离散人工蜂群算法.根据该优化问题及离散量的特点,对引领蜂、跟随蜂和侦查蜂角色转变机制和搜索策略进行了重新定义.蜂群角色转变基于定义的收益比因子.引领蜂邻域搜索采用2-Opt算子和学习操作来加速算法收敛速度;跟随蜂搜索引入禁忌表来提高算法的局部求精能力;侦查蜂搜索定义了排斥操作来保持种群的多样性,从而较好地平衡了算法的探索及开采能力.实验结果表明,算法能够在较短时间内找到相对满意解,提高了TSP的求解效率.     

带有预知信息的在线Homing ATSP问题

针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.     

预知信息和有限运载能力下应急车辆路径选择问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法,分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善.     

大规模无线传感网络数据收集的无人机路径规划

针对部署在地表交通困难的大规模无线传感网络,采用目前可控无人机(unmanned aerial vehicles, UAV)进行数据收集能够达到更好的效果. 然而,考虑到无人机自身有限的资源,以及网络中存在大量传感器节点的情况,无人机飞行路径规划对于顺利完成数据收集任务具有重要作用. 无人机路径规划可以看作经典的旅行商问题(traveling salesman problem,TSP). 针对部署具有均匀性特点的大规模无线传感网络,提出了一种规则化快速路径规划(fast path planning with rules, FPPWR)算法. 该算法通过网格划分,将全局区域飞行路径的求解划分到多个较小的方格中进行,并通过成对算子路径优化算法在初等飞行路径上将方格区域中的路径合并为全局路径. 实验证明,该算法在保证了较高精度的同时,显著提升了路径规划的效率.      

野外露宿准备什么？

随着人们生活水平的不断提高,外出郊游已成为青年朋友们的新时尚,特别全国大中小学的暑期已到,许多青年学生都想利用这段假期,带上账篷、炊具到野外风餐露宿,以最大程度体验在大自然中的美好感受。然而中国有句老话说:“乐极而生悲”,游历壮丽山川的喜悦,常常与野外遇到的挫折相抵消。为了使您在野外活动中减少意外,能以最小的代价实现最完美的野外极限享受,我在此向您介绍一下自己20多年的野外工作经验。野外装备俗话说:“兵马未到,粮草先行”。一个完整的野外行动计划最关键的就在于“后勤保障”。在远离城市生活设施的旷野中生活,如果不具备基本条件,没有科学手段及足够的思想准备,一般都会发生许多意想不到的困难。因此在出行之前,首先要根据野外行动总体计划购置野外装备。野外装备可归纳为四大类:1.基本生活设施     

非常留言板

非常留言板,哥迷FANS的俱乐部!无论趣事、心事、还是身边的琐事,无论好事、坏事,还是发生的糗事,非常心事让我们一吐为快!你有好看好玩的电影、图书、模型手工等,show出来和大家非常分享吧!作为回报,悠悠会定时进行非常小编故事播报。最后,让我们一起听听非常消息是不是在你身边发生哟!     

关于旅行推销员问题的一个算法

通过圈上结点下标自足方法，给出了一个关于旅行推销员问题的算法，尽管该算法实质上无法改变问题的NP－完全性的难度，但较分支定界法的执行速度快，比一些近拟算法要好。