基于偏好信息的多目标旅行商问题Pareto优化求解

多目标旅行商问题(MOTSP)是经典旅行商问题的扩展,其优化目标包含了距离、成本、收益及风险等多个相互冲突的指标.本文提出了一种基于偏好的Pareto演化算法p-PEA用于建模并求解此NP-hard问题.该优化算法建立在MOTSP的智能体仿真模型之上,从而解决了数学建模不能真实再现实际MOTSP中众多影响因素的问题.通过仿真的方法,算法能够得到MOTSP可行解的各项评价指标值.在此基础士,通过设计演化算法搜索问题的Pareto优化解集.其中,将决策者的决策偏好信息引入到Pareto优化解集的求解过程中,所得结果将更合理.最后,以一个130个城市的旅行商问题为例验证了算法的有效性.     

时变网络环境下旅行商问题研究

对时变旅行商问题进行描述,提出处理一般跨时段的新方法,并建立数学模型.在求解方法上构造动态搜索优化算法ds-k-opt(k=2,2.5,3)求解该问题.通过实验仿真,大部分动态搜索优化算法解质量优于动态规划启发式算法,且求解规模更大.动态搜索优化算法解随k值增大而更优,算法运行时间也随之增加.     

基于差分进化算法的多旅行商问题优化

针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的.     

基于递阶遗传算法的一类多旅行商问题优化

针对最小化单个旅行商路程的多旅行商问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

求解多旅行商问题的新混合遗传算法:以应急物资配送为例

为优化生物反恐条件下的应急物资配送过程,将该环境下的应急物资配送问题构造为一多旅行商问题(MTSP),并从理论上分析了该旅行商回路为最短Hamilton路径。以此问题为背景,针对应用传统遗传算法求解多旅行商问题时存在收敛速度缓慢等问题,提出并设计了一类新的混合遗传算法。该类新遗传算法与传统遗传算法的最主要区别在于,针对多旅行商问题专门设计了一种新的染色体编码规则、排序算子和交叉算子。仿真结果表明,该算法能够快速收敛到问题的近似最优解,并能很好地维持种群的多样性。     

一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

解旅行商问题的混沌蚁群算法

利用混沌运动的遍历性、随机性和规律性等特点,提出了一种求解旅行商问题的混沌蚁群(CACO)算法.该算法的思想是采用混沌初始化进行改善个体质量和利用混沌扰动避免搜索过程陷入局部极值.与模拟退火算法、标准遗传算法进行比较,仿真结果表明该方法是一种简单有效的算法.     

一种求解TSP的生物信息启发式遗传算法

遗传算法是解决旅行商问题（traveling salesman problem，TSP）的通用路径优化算法之一。为解决传统遗传算法收敛速度慢且解不稳定的问题，提出一种生物信息启发式遗传算法（bioinformation heuristic genetic algorithm，BHGA）。通过优化适应度函数和初始种群，引入生物信息学中的基因序列对比手法进行交叉重组排序，采用基因逆转操作进行变异，对遗传算法进行改进，使算法能够加快收敛速度，得到更优路径解。利用BHGA对TSPLIB数据库中算例进行求解，实验仿真结果表明：该算法在中小型规模的TSP中求解效果好且结果稳定。     

解旅行商问题的一个新的遗传算法

对旅行商(TSP)问题设计了一个新的遗传算法.首先,对n个城市的旅行商问题设计了一个新的编码方法,并且对这种编码方法,给出了简便的解码方法.其次,针对编码的特点,设计了一种新的、有效的杂交算子和变异算子,这些算子均能直接产生可行的后代.为提高杂交算子的搜索能力,结合了一个局部搜索技术来改进杂交算子.在此基础上,提出了求解TSP的一个新的遗传算法,并证明了其全局收敛性.为了验证算法的有效性,对10个国际标准算例(城市规模从14到1000)进行了计算机仿真,结果表明算法是有效的.     

易腐货物配送中时变车辆路径问题的优化算法

以易腐货物配送中的时变车辆路径问题为研究对象.由于时变车辆路径问题中每条道路上的车辆行驶速度随时间变化,此类问题难以用传统的数学建模方法进行建模及实现优化求解.因此,提出应用计算机建模的方法建立此类时变车辆路径问题的仿真模型.在此基础上,设计并集成遗传算法于计算机仿真模型用于搜索问题的最优解,所提出的自适应性优化算法能够根据来自车辆驾驶员回传的实时数据动态调整后续的最优行驶路线.最后,在多智能体建模与仿真平台上实现了该算法,并以15个顾客的时变车辆路径问题为例验证了算法的有效性.     

基于蚁群算法的人车混合疏散优化及混合比例分析

为解决紧急情况下的人车混合疏散问题, 以人车混合疏散的总时间最短、混合道路利用程度最高为目标,建立了一种人车混合疏散的多目标优化模型, 针对该模型设计了多目标蚁群优化算法及其改进算法,并应用于大型体育场及其周边路网集成环境中进行了仿真实验, 分析了不同人车混合比例下的疏散性能,结果表明:该模型及算法对人车混合交通流疏散问题具有良好的效果, 尤其是当行人所占比例为 50%-80% 时,人车混合疏散效果在两个目标上较优.该模型和算法有助于为大型公共场所人车混合安全疏散预案的制定提供决策支持.     

城市路网系统大气污染物排放量计算方法

为解决城市复杂路网系统特定时期各路段机动车大气污染物排放量的精确计算问题,提出一种新的机动车污染物排放量计算方法.首先构建路网拓扑模型;其次利用复杂管网液体流动模拟路网机动车流动行为,根据流动规律构建机动车流计算模型,并给出其求解算法-邻域自适应差分进化(NADE,neighborhood adaptive differential evolution)算法;然后结合排放因子计算机动车污染物排放量,并揭示其排放特征;最后以大西安主城区路网为例对该方法进行实例验证.结果表明:该方法计算结果贴近各路段污染物实际排放情况,通用性强,适用于复杂路网机动车流量和污染物排放量的动态测算.     

城市道路网络交通状态时空演化量化分析

为了使对城市道路网络交通状态的分析不至陷入交叉口或路段内部的交通状态分析,需从中观或宏观的角度去分析交通状态.本文在探讨路网状态特征参数的基础上,定义了"路段拥挤度"指标,通过建立城市交通网络模型,并基于浮动车(GPS)采集数据设计了路网交通拥堵时空演化量化分析的流程,采用"路段拥堵持续时间""区域行程时间延误"区域拥堵路段数量"三个时空参数对路网交通拥堵状态的时空演化进行了量化研究.最后结合上海市浮动车数据与实际交通网络,得出了交通拥堵的延误时间和空间范围与拥堵程度大小的关系等结论.     

基于蚁群算法的交通控制与诱导协同研究

以路网总行程时间最小为目标,兼顾路网流量的均衡,建立了城市交通控制与诱导的协同模型。引入了蚁群算法的思想,并利用此算法对模型进行求解,得到最佳路径和最佳信号配时方案;最后采用小型路网进行仿真试验,通过跟实际的交通流对比,表明此方法能有效均衡路网流量,并能有效节约路网的总行程时间。     

基于O-D网络的交通流模型的分岔与混沌

以交通流O-D网络系统为背景,通过分岔图和相图讨论了在无交通阻塞下的交通费用和交通容量变化下系统非线性动力学行为的变化和运动复杂性.交通费用和交通容量作为交通网络的固有属性,对定性分析交通网络的动力学行为具有至关重要的作用.同时,数值验证了两种计算交通流O-D网络系统分岔图的方法的等价性.     

Application of Drone in Solving Last Mile Parcel Delivery

The article is about solving the last mile delivery problem in rural town or village. We want to test the drone's potential in parcel delivery. The objectives are 1) to introduce the cluster and truck-drone in tandem delivery method, 2) to compare the new method with the traditional TSP method in aspect of truck running distance, energy using and time occupation. The parcel delivery demand is sparse, so it is not dense enough for a truck to carry on delivery. We try to identify the best route for the drone to deliver the goods. We use k-mean method to carry on clustering, then we use enumeration method to fulfill the centroids delivery, which comes from the depot. We design a model and calculate the energy, time and distance saving between drone using method(DTSP) and traditional TSP method. The drone attended delivery saves truck delivery distance, energy consumption and time.The truck running distance of DTSP method saves 91.87%, the truck running distance is shortened from 189.69 km to 15.4252 km. The DTSP method saves 90.45% of energy. The DTSP method brings a29.75% cutoff in time aspect when there are two drone in running. The research introduces the cluster and TSP combination method, which is a good way to carry on last mile delivery. The result shows a bright future for drone to attend parcel delivery. The e-commerce corporation can apply this method in practice.     

双交叉口两级模糊协调控制算法的研究

基于城市交通智能控制研究课题的需要,提出了一种双交叉口的分级模糊协调控制算法和应用混沌优化自动调整隶属度函数的思想,依此设计了双交叉口的两级模糊协调控制器;应用MATLAB编写了仿真程序,对主次干道车流量相差悬殊和相近两种情况进行了实例仿真,并与传统控制算法进行了比较.仿真结果表明,分级模糊协调控制方法可以有效减少有主次干道之分的交叉口车辆的平均延误,对交通流量均衡的交叉口的控制效果,也比传统算法有显著提高.     

基于延时动力系统的多车道交通流仿真

基于延时动力系统思想,提出了关于动力系统的道路交通流量的仿真新算法。针对多车道、路况可变、流量可变的复杂交通环境建立了新模型,在分析多车道封闭系统和多车道路况的基础上,本新模型可以描述前后时间段对道路交通流量的相互影响。仿真数据结果表明,新模型能够模拟交通流量变化,同时对于控制交通流量以及分析交通系统的特点是有效的。结果推广并改进了文献[2,3]中的相关结论。     

异质用户下交通拥挤控制的混合策略研究

随着出行需求及汽车保有量的增加,交通拥挤愈发严重.为了缓解交通拥挤,本文针对公私合营的交通网络,考虑用户异质性,提出了对交通网络同时实行道路收费和可交易电子路票方案的混合策略,即分别对使用政府资建的公有路段和BOT模式下的私有路段的出行用户收取电子路票和费用.通过对用户在混合策略下的出行行为分析,建立了用户均衡和路票市场均衡下的变分不等式模型.接着,对交通网络的系统最优模型进行分析,得到了促使路网在用户均衡状态下达到系统最优的混合策略集合,同时给出了混合策略下系统效率损失的上界.在此基础上进一步提出了涵盖其他目标的双层规划模型,得到能实现双重目标的最优混合策略.最后,对具体路网进行数值实验,可分别得到路网中每一公有和私有路段的具体路票收取量和收费值,以及需要设置的收取总窗口数.     

结合社交媒体数据的城市交通事件可视分析方法

社交媒体中的文本内容可对交通量数据进行补充,为此提出一个交通事件可视分析方法。建立交通事件文本处理模型,提取事件的描述信息;基于图嵌入算法学习道路节点属性的向量表示,建立道路相似性模型;结合核密度模型建立交通事件发生概率预测模型;设计了一个交互式可视分析界面对于交通事件进行可视分析与探索。通过交通信息抽取、道路相似性度量以及交通事件交互预测等案例分析,验证了所提方法的有效性,可以辅助交通部门管理决策。