有服务时长和服务可选择性的快递车辆调度在线策略研究

针对快递揽件需求出现无法提前获知、服务每一个快递需求需要一定的服务时长,且无法接受全部请求的情形,提出带有服务时长和服务可选择性的快递车辆在线调度问题,证明了该问题在线策略竞争比的下界。在正半轴上提出Replan策略,在直线上提出ReOPT策略,在一般网络上提出GRH策略,证明了上述在线策略的竞争比。结果表明,考虑服务时长能够改善在线策略的竞争性能,所提在线策略在实际应用中具有实用性。结论将为快递车辆的科学调度提供理论依据。     

总服务时间已知的两台同类机调度问题

研究调度问题上机器服务总时间已知的问题,针对机器的速度和准备时间不同,分析研究带机器准备时间的服务总时间已知的两台同类机半在线调度优化问题.目标为最小化最大机器服务时间,对于机器服务所有工件的时间已知的半在线情形,给出了人一个竞争比不超过2(s+1)/(2s+1)的半在线算法,其中s_i为机器速度,s_1=1,s_2=s>1.     

一种新的在线调度算法竞争比分析方法——基于实例转换的方法

针对工件动态到达的在线调度模型提出了一种基于实例转换的竞争分析方法,该方法从问题的一个任意实例出发,逐步沿着性能比增加的方向修改工件的各种参数而得到结构更加简单特殊的实例,最后所导出的简单实例的性能比可以直接计算,且是算法竞争比的一个上界.该方法为在线调度算法的竞争比分析提供了一种新颖的、规律性的思路,以最小化总加权完工时间的单机在线调度问题为例,使用提出的分析方法为该问题一个已有的竞争分析结论提供了更加简洁明了的替代性证明.     

带有配额的在线Nomadic旅行商问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了社会的广泛重视,而应急车辆尽快地将应急物资送到受灾点显得尤为重要。针对应急车辆装载物资能力有限和应急车辆不必返回出发点的情形,提出了带有配额的在线Nomadic旅行商问题。分析了该问题在正半轴和一般网络上的下界,针对受灾点仅在正半轴上的情形设计了WTAIB算法,针对受灾点在一般网络上设计了WSB算法,并进一步分析了两个算法的竞争性能。     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

基于实际路网情境的配送车辆调度优化

在实际路网情境下结合车道数、车道宽度、路口信号灯设置等路网物理特性,构建了考虑综合交通阻抗的多车型车辆调度模型,提出了两阶段求解策略:第1阶段设计了改进A-star精确解算法用于计算客户时间距离矩阵;第2阶段针对实际路网的特征设计了混合模拟退火算法求解调度方案。以大连市某配送中心运营实例进行路网情境仿真试验,结果表明:改进A-star算法较改进Dijkstra算法具有更短的路径搜索时间;混合模拟退火算法求解结果较实际调度方案优化了13.1% 的综合成本;路网增流、区域拥堵和路段禁行三类路网情境均能对配送方案的车辆配置、路径选择、客户服务次序、作业时间和违约费用等5方面内容产生干扰,调度计划的制定需要详细考虑这些因素的变化。     

预知信息下集装箱码头资源联合调度在线策略研究

探讨了有限预知信息下的集装箱码头泊位与岸桥联合调度over-list在线模型,当分配每个船舶服务请求时预知后续k≥2个请求,要求完成所有请求的最大完工时间最小。着重考虑了由3个离散泊位组成的混合型泊位、6个岸桥以及只有两种请求的联合调度模型,证明了任意k≥2个请求预知能力下确定性在线策略的竞争比下界为9/7;同时,设计了k=2时的在线联合调度策略并证明其具有最优竞争比9/7,表明有限的预知能力即可实现在线策略最优调度效果,这也为集装箱码头资源调度实践中的策略设计提供理论依据。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

Option contracts: a solution for overloading problems in the delivery service supply chain

Owing to the limited service capacity of express delivery providers, most online retailers have to reject many orders during hot selling seasons. In this paper, we consider an express delivery service supply chain consisting of an express delivery provider and an online retailer whereby the selling season includes both regular periods and online sales periods. Utilizing a modified newsvendor model, we derive the express delivery provider’s optimal capacity decision and find that the overloading problem cannot be avoided because delivery service cannot be inventoried. To solve such a problem, we introduce an option contract to coordinate the supply chain. By allowing the online retailer to book the capacity, the express delivery provider can rent capacity from a third party in advance. Results show this approach can mitigate the problem significantly. We also extend our model to a supply chain consisting of a delivery provider and two retailers.     

Approximation results for a min-max location-routing problem

This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min-max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.     

Scheduling data transfers in a network and the set scheduling problem

In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.     

Agent-based modelling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies

This study investigates the effectiveness of simultaneous and staged evacuation strategies using agent-based simulation. In the simultaneous strategy, all residents are informed to evacuate simultaneously, whereas in the staged evacuation strategy, residents in different zones are organized to evacuate in an order based on different sequences of the zones within the affected area. This study uses an agent-based technique to model traffic flows at the level of individual vehicles and investigates the collective behaviours of evacuating vehicles. We conducted simulations using a microscopic simulation system called Paramics on three types of road network structures under different population densities. The three types of road network structures include a grid road structure, a ring road structure, and a real road structure from the City of San Marcos, Texas. Default rules in Paramics were used for trip generation, destination choice, and route choice. Simulation results indicate that (1) there is no evacuation strategy that can be considered as the best strategy across different road network structures, and the performance of the strategies depends on both road network structure and population density; (2) if the population density in the affected area is high and the underlying road network structure is a grid structure, then a staged evacuation strategy that alternates non-adjacent zones in the affected area is effective in reducing the overall evacuation time.     

竞争环境下基于退换货的网购供应链动态均衡研究

研究竞争环境下基于退换货的网购供应链动态均衡模型.此供应链包含多个生产商、电商、快递商及需求市场.将快递商的运输速度作为竞争的一个重要因素进行研究.通过正弦函数说明,网购供应链的市场需求也呈季节性变化.利用纳什均衡及变分不等式得到各层决策者的竞争均衡解.通过分析换货比重得出电商应减少消费者的退货率,以提高整条供应链的利润和竞争能力.并利用数值算例说明模型的正确性与合理性.     

公路隧道围岩稳定性评价的改进人工神经网络方法

本文运用改进的人工神经网络方法 ,研究了公路隧道围岩稳定性的评价定级问题 .首先讨论了模型建立和算法选择与分析 ,并对实际的工程问题进行了计算和模拟 .所得的评价定级结果接近于实际 ,计算方法可靠 ,计算时间适中 ,方法稳定性良好 .本文的研究结果表明 ,利用人工神经网络方法评价隧道围岩的稳定性具有广阔应用前景 .     

Distributed Online Frequency Assignment in Cellular Networks

A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multicoloring problem on a weighted graph, where the weight vector associated with the vertices models the number of calls to be served at the vertices and is assumed to change over time. In this paper, we develop a framework for studying distributed online frequency assignment in cellular networks. We present the first distributed online algorithms for this problem with proven bounds on their competitive ratios. We show a series of algorithms that use at each vertex information about increasingly larger neighborhoods of the vertex, and that achieve better competitive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.     

具有服务等级的两台同型机实时在线排序

考虑具有服务等级的两台同型机在线排序问题, 其中工件带有到达时间, 目标为最小化最大完工时间, 设计了竞争比为\frac{7}{4}的在线算法.     

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。