考虑位置效应的电商平台占线品类优化问题

基于电商平台的动态特征,本文研究了一个新的品类优化问题．假设消费者行为服从多项logit (multinominal logit)选择模型,当消费者陆续到达时,平台在满足产品有限库存约束的前提下,从给定产品集合中选择一个子集,并决策对应的展示位置,提供给消费者,以最大化预期收益．以往研究建立的模型一般假设消费者类型到达序列已知或满足某随机分布,但现实中消费者到达序列往往具有高度不确定性且不可随机观测.本文利用占线理论与竞争分析的框架,在消费者类型未来到达序列未知的条件下,以最大化电商平台收益为目标,构建了同时考虑库存约束、品类优化和位置效应的占线决策模型,给出了相应的展示策略.该策略易于求解,能够快速的得到展示方案.从理论上证明了策略的竞争比并分析了问题的竞争比上界,结果说明该策略具有非常好的竞争性能.     

城市交通网络中商业街的选址分析与计算

商业街在城市交通网络体系中的选址是商业街布局的重要方面。本文提出交通网络商业街选址问题并建立数学模型，给出了两种选址原则：（1）城市中所有节点至商业街（只需要达到商业街的其中一个节点）之间的最短路径之和最小。（2）城市中所有点对之间过商业街的最短路径之和最小。针对以上两个方面，分另4给出其计算方法，并进行了算法的时间和空间复杂性分析。     

一般网络上的占线中心选址问题及其竞争算法

对一般网络上的占线中心选址问题及其竞争算法进行了研究.文献[6]证明了该问题的竞争比下界是(n-2△e+√(n-22△e2+4(n-1)/2(n-1)) ,其中△e是所给空间最大的相对距离,并证明了该问题不存在常数竞争比的竞争算法.本文给出了一个多项式时间的竞争算法,并证明该算法的竞争比为△e△w,其中△w是所给空间点间的最大相对权重.所得结论不仅对于理论上占线中心选址问题的竞争算法的设计与分析,还是对于实际中的选址决策,都具有一定的指导意义.     

道路容量不确定情形下可靠应急疏散路径规划问题

本文提出道路容量不确定的基于可靠性的应急疏散路径规划(包含路径的选择和随时间的流量分配)模型.现有的模型假设在制定路径规划时就已知灾害发生后的道路容量,或者为确切不变常数,或者为精确概率分布函数.本文假设道路容量的概率分布难以精确获知,仅知部分分布信息,利用分布鲁棒优化方法,构建寻求以已知信息为特征的不确定集的最坏情形下的可靠疏散路径规划.基于交通流的网络拥塞最小化原则,建立了以最小拥塞概率为目标的机会约束模型,以保证应急疏散路径规划方案分配的流量不超过灾害发生后实际的道路容量,进一步确保路径规划方案的可靠性.给出了求解方法,进行了仿真分析,验证了方法的有效性和疏散路径方案的可靠性.     

具有建设成本的占线中心选址问题及其竞争算法设计

研究待选址个数不确定的动态选址问题. 在实际选址过程中,经常会在全部需要建立的设施个数未知的前提下,决定在哪里建立初始的设施(或设施集),同时要求,当增加建立设施时,已经建立的设施不能被删除.此外,基于实际,待建立的设施间的初始建设成本是不同的. 建立了满足上述约束的占线选址动态模型,并给出一个竞争算法,最后证明该算法具有常数的竞争比.     

占线中心选址问题及其竞争算法分析

基于在建立的设施的个数未知的前提下需要决定如何建立初始设施集,同时要求,当新的设施集建立后,前面已经建立的设施不能被删除的实际选址约束条件下,从占线理论出发考虑了待选址个数不确定的动态选址问题.设计了一个多项式时间的竞争算法,证明了该算法具有的竞争比,该竞争比结果优于已有的结果.     

具有库存持有成本的原材料占线采购问题

本文研究价格不确定且考虑库存持有成本的原材料占线采购问题.以往的研究通常都是假设价格服从某种随机分布,而在实际的原材料采购决策中,原材料的价格往往并不能被随机刻画.同时在采购决策中库存持有成本是不可忽略的.基于该实际背景,根据价格无分布信息假设的占线理论,考虑了具有库存持有成本的原材料采购决策优化问题,在已有研究的基础...     

不确定曝光量下保量投放合约广告鲁棒分配优化

在线广告市场中,保量投放合约广告占有重要份额。在相应的广告分配研究中,通常假设广告发布商平台在分配决策时,已知曝光量的精确值或精确概率分布,但实际决策时该值是高度不确定的。本文假设仅知曝光量部分分布信息,寻求已知部分信息的不确定集的最坏情形下的鲁棒分配方案,建立分布鲁棒机会约束模型。通过分析问题结构特征,对模型进行转化,设计了基于黄金分割搜索的风险概率凸逼近迭代算法,有效提升分配效果。最后进行数值仿真实验,验证得到的广告分配方案和相应设计算法的有效性和鲁棒性。     

占线顶点覆盖问题的结构性下界

在实际 顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.     

最大和搜索结果多样性问题及其贪婪算法分析

研究互联网搜索结果的最优多样性问题.给定用户搜索关键词较少,以及关键词本身的多义性,同时由于搜索系统一次呈现结果存在数量上的限制,系统常不能准确定位用户的真实搜索需求.为了最大化覆盖用户的搜索需求,搜索系统显示的结果不仅需要最大化同关键词的相关性,而且需要最大化结果之间的差异性.考虑了最大和搜索结果多样性问题,给出了贪婪算法,并针对实际中的差异性度量常常不满足三角不等式的情况下,分析证明了该贪婪算法具有的近似性能比.结果表明贪婪算法具有很好的理论近似性能.