基于预知信息的占线Nomadic TSP问题

自然灾害的频繁发生使得应急减灾倍受关注, 尤其有效的应急救援车辆调度对应急减灾非常重要. 针对受灾点被提前获知但是不能立即接受救援服务的情形, 通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题, 并分别给出了问题的下界, 直线网络结构下的ENO-dd算法, 和一般网络结构下的GTR-dd算法, 并对算法进行了竞争性能分析. 结果表明两个算法随着预知信息的增多会有明显改进. 更为一般的预知信息结构以及最优的算法设计是下一步研究的方向.     

公平与效率权衡的双目标应急物资分配模型

针对震后首批应急物资供不应求、需求量动态变化等特征,构建以最大化受灾点的最小需求满足率为公平目标,以最小化应急物资的最晚送达时间为效率目标的整数非线性规划模型,据此对多受灾点、多救援点的应急物资分配方案进行决策。根据模型特征,设计基于epsilon约束法的多目标算法,并对算法的收敛性进行分析。算例结果表明,通过模型和算法能够得到不同偏好下的应急物资分配方案,可以更好地权衡应急物资分配的公平与效率,揭示了最大最小公平的最终目的是实现比例公平。     

基于预知信息和实时服务选择的在线TSP问题

现实生活中,提供外送服务的快餐店为了降低成本、提高效率,在接到顾客的订餐信息时,可能会因为距离等因素拒绝一些顾客的送餐要求,而拒绝顾客需求会带来一定的惩罚(如丧失部分客户).针对快餐店选择性提供送餐服务,同时送餐点信息被提前获知但是不能马上被服务的情形,提出了基于预知信息和实时服务选择的在线旅行商问题(traveling salesman problem,TSP).针对需求点在正半轴和直线上的情形分析了问题的下界,并设计了相应的算法,同时分析了每个算法的竞争性能.结果表明,算法的竞争性能会随着预知信息的增加而得到改善.     

基于灾情信息更新的应急物资配送多目标随机规划模型

研究了多出救点、多受灾点、多物资、多车型的应急车辆选址、路径选择和物资配送问题. 考虑到灾害预测准确性和物流成本效率之间的悖反关系, 从多目标规划和随机规划的角度, 建立了应急物资配送的多目标随机规划模型. 建模中同时考虑需求和配送路径连通性的随机性, 以及出救点对受灾点的最大覆盖范围限制. 将统计决策与运筹规划相结合, 设计一个加权贝叶斯风险将多目标规划问题转化为单目标规划问题, 以及设计一个决定最优停止观测时刻的决策规则使原问题转化为最优停止问题. 通过Xpress软件编程求解. 最后, 算例分析表明了模型和软件的求解速率与精度, 并分别证明了两阶段随机规划和灾情信息更新的优势.     

运力受限的应急物资动态调度模型及算法

针对大规模突发事件下应急物资动态调度问题, 把灾民的损失用物资未满足度的形式进行量化, 构建以最小化灾民损失和车辆调度费用为目标的混合整数规划模型, 以对运力受限情况下的救 援车辆路径选择和应急物资分配进行综合决策. 利用分层求解策略缩小问题的求解空间, 改进 基于客户点的编码方式, 设计了针对此问题的遗传算法. 代入实验数据得出了物资集散地不同 运力下的应急物资动态调度方案, 进而确定了最优运力配置量, 与现实情况下的配送方案比较 表明此模型和算法是有效的.     

应急物资运输的两阶段车辆调度模型

针对大规模突发事件爆发后,应急物资运输车辆不足,需要多次、分阶段将应急物资运送到需求点的情况,本文将传统车辆调度模型中车辆在完成阶段运输任务后返回原始出发点的假设条件予以放松,以应急物资运输的全局完成时间最早为目标,建立了基于车辆紧缺假设的两阶段车辆调度模型,并根据问题的特点设计了相应的启发式算法并给出了算例,在可接受的时间内得到了较为满意的优化结果,有效提升了应急物资运输车辆的使用效率。     

带限制期的震后应急物资配送模糊多目标开放式定位-路径问题

为提高震后应急物资配送绩效,针对应急物资配送中心选址与配送车辆路径安排的集成优化问题,综合考虑应急物资需求的模糊性、限制期和多次往返配送,有限数量不同类型的配送车辆,开放式车辆路径,有容量限制的临时物流设施选址以及震后路网部分受损等特点,以各物资需求点的应急物资运达时间之和以及系统总成本最小为目标,采用机会约束规划方法建立了一个模糊多目标开放式定位-路径问题(LRP)优化模型,并设计了一种结合启发式规则的混合遗传算法。最后,对该模型和算法进行了数值验证,并通过与NSGA-Ⅱ多目标遗传算法的比较,证明该混合遗传算法具有良好的性能,从而为解决震后应急物资配送的模糊多目标LRP提供了有效的方法。     

面向应急物资调度的一种模糊规划模型

灾害救援问题具有信息缺失、数据难以收集与整理的特点.为了科学、合理地进行救援物资的调度,考虑在满足处置应急需求时,从总体上最大限度地降低处置应急物资运输调度的费用和时间.在现有研究成果的基础上,引入了模糊评价方法,建立多出救点、多受灾地的多目标模糊规划模型.模型采用加权语言标签空间描述救援地到受灾地可能发生的费用与时间,考虑决策者对风险的偏好建立无差异函数,将其转化成决策者的效用作为目标值,给出相关算法,确定为每一个应急需求点提供应急物资的供应点以及相应的供应量.最后,给出算例证明其可行性.     

模糊环境下多出救点应急救援车辆路径与物资运输优化研究

为研究灾害发生后应急救援车辆的运输路径和救援物资的运输问题,考虑受灾点对救援物资的需求量为模糊变量,将多出救点到多个受灾点的应急救援运输优化问题视为两阶段决策问题.第1阶段建立救援车辆的路径优化模型,实现运输时间最短;在满足第1阶段最优的情况下,第2阶段建立模糊线性规划模型,在运输成本最小前提下,确定出救点与受灾点之间的救援物资调运以及受灾点与受灾点之间救援物资的转运量.最后,利用具体算例来验证该模型的有效性.     

基于受灾人员损失的多受灾点、多商品应急物资分配模型

分析了现有应急物资分配模型的不足,考虑了灾害严重程度、物资属性、受灾点属性等各种因素,构造了受灾人员的损失函数,构建了以受灾人员损失最小为目标的多受灾点、多商品应急物资分配模型,给出了模型的最优条件和求解方法,对模型在不同情况下的算例结果进行了对比分析。     

转向限制网络中基于预知时间的快递车辆在线揽件路径选择研究

针对现实快递服务网络结构上的转向限制及待服务需求出现后不能立即接受服务的特征,将预知时间引入到在线旅行商问题中,提出以服务总时间最小为目标的转向限制网络中基于预知时间的快递车辆在线揽件路径选择问题.在半路径上提出了WBR-dd策略,在路径上提出了REPdd略,在一般网络上提出了PAH-dd策略,证明了上述在线策略的竞争比,分析了该问题竞争比的下界.结果表明预知信息越多,在线算法将获得更优的竞争性能.     

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

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

Performance evaluation of sensor allocation algorithm based on covariance control

1 .INTRODUCTIONSensing platforms for target tracking have becomein-creasingly complex as more and more types of sensorshave been added to them. Sensor management tech-niques can provide automatic or semi-automatic con-trol of a suite of sensors to i mprove the performanceof sensing and give an effective usage of sensor re-sources. Traditionally, sensor allocation approachesselect sensor sets which mini mize a cost function ormaxi mize an efficiency function consisting of sensor-target pair…     

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

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

限制信息条件下基于时间窗的占线装-卸货问题及其竞争分析

提出并研究限制信息条件下基于时间窗的占线装一卸货问题。客户在提出服务请求时只指定需要承运的货物的装载地，而没有提供目的地信息，服务车只有在到达装载地之后才知道目的地的具体位置，如现实中的出租车调度和电梯调度等问题。就两种度量空间对限制信息条件下带时间窗的占线装一卸货问题进行了分析，分别给出了两种竞争策略及其竞争比结果，并得到了针对该问题的任何确定型算法的竞争比下界。     

O2O模式下的配送车辆实时取送货路径选择问题

伴随020模式下外卖市场的迅猛发展,由此导致的最后3公里配送需求日益激增,外卖的配送时效受到了广泛的关注.外卖的及时配送,即配送车辆的路径选择问题成为餐饮服务业重要的研究问题.针对020平台外卖配送服务过程中,需求无法确定和配送车辆必须返回原点取货的情形,提出了带有取送货的在线旅行商问题(traveling salesman problem, TSP).分析了该问题在正半轴和一般网络上的下界,针对需求点仅在正半轴上的情形设计了TAIB算法,针对需求点在一般网络上设计了IGNORE算法,并进一步分析了两个算法的竞争性能,结论可以为现实中外卖配送车辆的实时调度决策提供依据.     

基于椭圆-双曲线马氏度量的图像分类算法

为了进一步拓宽度量学习在图像分类中的适用范围,同时提高分类的性能,本文提出一种基于椭圆双曲线马氏度量的图像分类算法。该算法首先将颜色特征和局部二值模式描述的纹理特征相结合来表示图像特征;然后引入对样本数据具有更好的适应性的椭圆双曲线度量,根据数据统计特性定义椭圆双曲线马氏度量,给出椭圆双曲线马氏度量学习算法,从而获取最优的度量矩阵;最后利用椭圆双曲线马氏度量矩阵将样本变换到新的特征空间,从而降低特征各维度间的相关性,同时计算图像特征间的距离从而完成分类。实验表明该算法提高了图像分类的有效性。     

Lazy learner text categorization algorithm based on embedded feature selection

To avoid the curse of dimensionality, text categorization (TC) algorithms based on machine learning (ML) have to use an feature selection (FS) method to reduce the dimensionality of feature space. Although having been widely used, FS process will generally cause information losing and then have much side-effect on the whole performance of TC algorithms. On the basis of the sparsity characteristic of text vectors, a new TC algorithm based on lazy feature selection (LFS) is presented. As a new type of embedded feature selection approach, the LFS method can greatly reduce the dimension of features without any information losing, which can improve both efficiency and performance of algorithms greatly. The experiments show the new algorithm can simultaneously achieve much higher both performance and efficiency than some of other classical TC algorithms.     

基于滚动优化策略的成像侦察卫星应急调度方法

针对成像侦察卫星应急调度问题进行研究, 在分析主要约束条件的基础上, 构建了多星调度问题的约束满足模型. 根据应急任务具有独立到达时刻与执行截止期需求的特点, 提出了基于滚动优化策略的调度算法. 该策略采用周期驱动与事件驱动相结合的混合驱动模式, 可将调度过程划分为一系列静态的调度区间. 通过优化各区间内任务的规划方案, 实现应急任务的动态调度. 在问题求解过程中, 将滚动优化策略与启发式算法结合, 形成了三种应急调度算法. 最后通过仿真实验, 对不同算法的调度效果进行对比, 验证了滚动优化策略的有效性.