Quadratic approximation and convergence of some bush-based algorithms for the traffic assignment problem

This paper first shows that LUCE (Gentile, 2012), a recent addition to the family of bush-based algorithms, is closely related to OBA (Bar-Gera, 2002). LUCE’s promise comes mainly from its use of the greedy method for solving the quadratic approximation of node-based subproblems, which determines the search direction. While the greedy algorithm accelerates the solution of the subproblems and reduces the cost of line search, it unexpectedly disrupts the overall convergence performance in our experiments, which consistently show that LUCE failed to converge beyond certain threshold of relative gap. Our analysis suggests that the root cause to this interesting behavior is the inaccurate quadratic approximation constructed on faulty information of second-order derivatives. Because the quadratic approximations themselves are inaccurate, the search directions generated from them are sub-optimal. Unlike OBA, however, LUCE does not have a mechanism to correct these search directions through line search, which explains why its convergence performance suffers the observed breakdowns. We also attempt to improve LUCE using the ideas that have been experimented for the improvement of OBA. While these improvements do work, their effects are not enough to counteract the inability to adjust sub-optimal search directions. Importantly, the fact that the search direction has to be corrected in line search to ensure smooth convergence attests to the limitation of origin-based flow aggregation shared by both OBA and LUCE. These findings offer guidelines for the design of high performance traffic assignment algorithms.     

基于可靠性最短路的实时定制公交线路优化研究

为实时优化定制公交线路，提出一种基于可靠性最短路的线路优化方法，在复杂的交通环境中，可以高效的将乘客送达目的地. 对可靠性最短路进行问题描述，建立可靠性时空网络；给出求解可靠性最短路的算法步骤，构建乘客和定制公交运营商总成本最小的目标函数，采用禁忌搜索算法对问题进行求解；最后，以某市定制公交路网进行实例分析. 结果表明：与最短路线路方案比较，所提方法更接近于实际运营；在高峰时段，交通拥堵的情况下，所提方法可以提高车辆的可靠性，提升定制公交线路的服务水平.     

Cooperative path following control of UAV and USV cluster for maritime search and rescue北大核心CSCD

［Objectives ］ This paper studies a three-dimensional (3D) cooperative path-following control problem in the process of maritime search and rescue for a heterogeneous unmanned cluster system composed of unmanned aerial vehicles (UAVs) and unmanned surface vehicles (USVs).［Methods ］ First, kinematic models of the UAVs and USVs are established under a fixed coordinate system and body coordinate system. In order to design a 3D path-following controller suitable for motion control, an air coordinate system is established, and the path tracking error models of the UAVs and USVs are established in the Serret-Frenet coordinate system. Next, a 3D line-of-sight (LOS) guidance law is designed at the kinematic level, and a cooperative path-following control method suitable for heterogeneous clusters of marine vehicles is proposed, allowing the UAVs and USVs to track the preset parameterized path. Finally, the stability of the control system is analyzed based on the Lyapunov stability theory.［Results］The simulation results verify the effectiveness of the proposed cooperative path-following control method for heterogeneous clusters of marine vehicles.［Conclusions］The results of this study can provide references for maritime search and rescue by using the proposed cooperative path-following control method. © 2022 Journal of Clinical Hepatology. All rights reserved.     

面向层次资质的机场外航服务人员排班研究

机场外航服务人员排班是机场智能调度系统的重要组成.针对目前我国机场外航服务人员排班主要采用人工方式，排班效率低下，员工工作时间均衡性不高，且难以满足多种类约束这一现状，本文充分考虑员工对任务具有层次资质及各类劳动法规约束，以均衡员工工作时间为优化目标，提出了面向层次资质的机场外航服务人员排班模型，并设计了基于禁忌搜索算法的模型求解策略.在首都机场外航服务部实际数据集上进行实验，验证结果表明，相比较于现有人工排班方案，利用本文模型得到的排班方案能满足所有排班约束条件，且在员工工作时间均衡性上有显著提高.     

一种基于时空距离的带时间窗车辆路径问题算法

带时间窗的车辆路径问题是典型的NP难题,一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法. 传统算法在顾客分组时主要考虑顾客的空间位置关系,但是忽略了顾客对服务时间窗口的要求. 本文同时考虑顾客的时间和空间特性,提出了一种基于时空度量的顾客分组方法. 在路径优化阶段,本文提出了一种禁忌搜索算法来进行求解,该算法中禁忌的对象不是解,而是这些解的目标函数值的区间,以便于提高收敛效率. 作为验证,本文以Solomon标杆问题集为算例进行演算,结果表明,在窄时间窗约束下,基于时空距离的两阶段启发式算法明显优于基于空间距离的算法,且部分算例的解达到了国内外已发表的最好解.     

基于数据库的动态路径寻优算法与实现

为适应当今数据存储和处理的需要,在路径寻优算法的实际应用过程中可以充分利用数据库管理数据的功能。利用实时动态的交通信息,寻找动态实时的最优路径,建立一个基于浮动车数据的动态实时路段速度数据库。通过实时动态地获得数据库中路段数据,提出基于数据库操作的动态路径寻优算法。为提高算法效率,提出动态变化限制搜索区域大小的辅助算法,并通过实例应用实现算法。     

有限经济批量排产和运送问题的禁忌搜索算法

探讨使用禁忌搜索算法解决一个简单的供应链经济批量排产和运送问题。其中供应商通过一个灵活的生产流水线生产多个组件并进行装配。假定所有参数,如组件的需求率等具有确定性,找到本研究的目标就是求解最优的生产批量和排序,使供应链的平均投入和运输费用最小。     

������֪����ʽ��������˶���ѧ��ģ

行人动力学建模的关键是对行人运动方向和速度的选择进行描述.本文构建了基于多层有限状态自动机的行人Agent适应性决策模型;在此基础上,针对行人运动过程中快速决策的特征,通过构建基于认知启发式规则的行人运动行为规则集合,建立了描述行人微观运动行为的动力学模型.通过设计仿真实验并收集数据,对模型的有效性进行了验证.研究结果表明：模拟得到的行人交通流密度-速度关系与实测数据具有较好的一致性,流率-密度关系符合理论计算结果,基本图较好地符合实际观测的行人宏观交通流关系,认为本文提出的行人动力学模型具有交通上的合理性.     

车辆数目未知的带时间窗口的车辆路径混合遗传算法

研究带时间窗口的车辆路径问题(VRPTW),主要考虑车辆容量约束、时间窗口约束、最大距离等约束,且完成配送所需的车辆数目不确定,要求在车辆数目最少的条件下再使总的行驶路径最短.用基于邻域搜索的混合遗传算法求解该问题,该算法既具有遗传算法的全局搜索能力,又具有邻域搜索算法的局部搜索能力.在求解过程中,设计新的前置交叉算子进行遗传操作,然后进行互换和逆转等邻域操作.应用MATLAB语言编程进行模拟计算,结果表明该混合遗传算法明显增强了群体演化的质量,提高了算法收敛速度,较好地解决了早熟收敛问题.     

混合超启发式法求解大规模VRP的优化研究

车辆路径是一类NP(non-deteministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义.提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题.先利用最近邻搜索法构建初步路线,再利用禁忌搜索法对内部线路和互跨线路进...