The probabilistic orienteering problem

The probabilistic orienteering problem (POP) is defined on a directed graph where a cost is associated with each arc and a prize is associated with each node. Moreover, each node will be available for visit only with a certain probability. A server starts from a fixed origin, has a given budget to visit a subset of nodes, and ends at a fixed destination. In a first stage, a node subset has to be selected and a corresponding a priori path has to be determined such that the server can visit all nodes in the subset and reach the destination without exceeding the budget. The list of available nodes in the subset is then revealed. In a second stage, the server follows the a priori path by skipping the absent nodes. The POP consists in determining a first-stage solution that maximizes the expected profit of the second-stage path, where the expected profit is the difference between the expected total prize and the expected total cost.We discuss the relevance of the problem and formulate it as a linear integer stochastic problem. We develop a branch-and-cut approach for the POP and several matheuristic methods, corresponding to different strategies to reduce the search space of the exact method. Extensive computational tests on instances with up to 100 nodes show the effectiveness of the exact method and the efficiency of the matheuristics in finding high quality solutions in a few minutes. Moreover, we provide an extended analysis on a subset of instances to show the value of explicitly modeling the stochastic information in the problem formulation.     

The network p-median problem with discrete probabilistic demand weights

We study the problem of locating p facilities to serve clients residing at the nodes of a network with discrete probabilistic demand weights. The objective is to maximize the probability that the total weighted distance from a client to the closest facility does not exceed a given threshold value. The problem is formulated as an integer program but can be solved only for very small instances because of the exponential number of decision variables and constraints. We analyze the problem and, using a normal approximation of the total weighted distance we develop branch and bound solution procedures for various cases of the problem. We also develop heuristics and meta-heuristics to solve the problem. Based on our computational experiments we make recommendations on which approach to use and when.     

The dynamic multiperiod vehicle routing problem with probabilistic information

This paper introduces the Dynamic Multiperiod Vehicle Routing Problem with Probabilistic Information, an extension of the Dynamic Multiperiod Vehicle Routing Problem in which, at each time period, the set of customers requiring a service in later time periods is unknown, but its probability distribution is available. Requests for service must be satisfied within a given time window that comprises several time periods of the planning horizon. We propose an adaptive service policy that aims at estimating the best time period to serve each request within its associated time window in order to reduce distribution costs. The effectiveness of this policy is compared with that of two alternative basic policies through a series of computational experiments.     

The stochastic -hub center problem with service-level constraints

Small package delivery companies offer services where packages are guaranteed to be delivered within a given time-frame. With variability in travel time, the configuration on the hub-and-spoke delivery network is vital in ensuring a high probability of meeting the service-level guarantee. We present the stochastic p-hub center problem with chance constraints, which we use to model the service-level guarantees. We discuss analytical results, propose solution heuristics, and present the results from computational experiments.     

The probabilistic gradual covering location problem on a network with discrete random demand weights

We study the gradual covering location problem on a network with uncertain demand. A single facility is to be located on the network. Two coverage radii are defined for each node. The demand originating from a node is considered fully covered if the shortest distance from the node to the facility does not exceed the smaller radius, and not covered at all if the shortest distance is beyond the larger radius. For a distance between these two radii, the coverage level is specified by a coverage decay function. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand weight is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance.     

The stochastic queue center problem

This paper considers the Stochastic Queue Center problem, which seeks to locate a single facility with a center-type objective in an M/G/1 queue operating environment. The objective function that we consider is to minimize a positive weighted linear function of the square of the average response time and the variance of the response time to a call. The Stochastic Queue Center problem is discussed on both a discrete and a network location topology. When potential facility locations are restricted to a finite set of discrete points, an efficient algorithm is developed to solve for the optimal facility location parametrically in the arrival rate. By exploiting convexity properties of the objective function, we develop an efficient finite-step algorithm to find the Stochastic Queue Center on a network. The major conclusion of this work is that incorporating the variance term in the objective function has a major impact on the choice of the optimal location. We illustrate the results with an example drawn from a potential application of the model for locating an emergency transport center serving different municipalities in Camden County, NJ.     

Tight complexity analysis of the relocation problem with arbitrary release dates

The paper considers makespan minimization on a single machine subject to release dates in the relocation problem, originated from a resource-constrained redevelopment project in Boston. Any job consumes a certain amount of resource from a common pool at the start of its processing and returns to the pool another amount of resource at its completion. In this sense, the type of our resource constraints extends the well-known constraints on resumable resources, where the above two amounts of resource are equal for each job. In this paper, we undertake the first complexity analysis of this problem in the case of arbitrary release dates. We develop an algorithm, based on a multi-parametric dynamic programming technique (when the number of parameters that undergo enumeration of their values in the DP-procedure can be arbitrarily large). It is shown that the algorithm runs in pseudo-polynomial time when the number m of distinct release dates is bounded by a constant. This result is shown to be tight: (1) it cannot be extended to the case when m is part of the input, since in this case the problem becomes strongly NP-hard, and (2) it cannot be strengthened up to designing a polynomial time algorithm for any constant m>1, since the problem remains NP-hard for m=2. A polynomial-time algorithm is designed for the special case where the overall contribution of each job to the resource pool is nonnegative. As a counterpart of this result, the case where the contributions of all jobs are negative is shown to be strongly NP-hard.     

Dual problem of sorptive barrier design with a multiobjective approach

Sorptive barrier technology is a recently developed tool to separate hazardous contaminants from friendly environment. The design of sorptive barrier refers to configuring different amendments with sorptive ability of organic pollutant, which is an integer programming problem and a relatively time consuming problem as well. In this paper, sorptive barrier design is newly modeled in a biobjective optimization approach, in which the dual problem of sorptive barrier design is deduced. The objectives are to minimize the financial cost and the amount of pollutant leaking through barriers. Then an opposition-based adaptive multiobjective differential evolution algorithm (MODEA-OA) is applied to handle the proposed model. The Pareto optimal front obtained by MODEA-OA spreads accurately and evenly in all three instances tested. To select extreme optimal solutions, the original and dual sorptive barrier design problems can be solved simultaneously. This study suggests that modeling barrier design as a multiobjective optimization problem is an effective approach.

     

The time-precision tradeoff problem on on-line probabilistic Turing machines

A probabilistic Turing machine (PTM) is a Turing machine that flips an unbiased coin to decide its next movement and solves a problem with some error probability. It is expected that PTMs need more time if a smaller error probability is required. This is a sort of time-precision tradeoff and is shown to occur actually on on-line probabilistic Turing machine acceptors (ONPTMs). That is, we show the existence of a set such that it is recognized by an ONPTM with $\text{1}\text{2}\text{-(}\text{log}\text{n)/}\text{8}\text{n}$ bounded error probability in O(n) time but for every $\text{ε, 0<ε<}\text{1}\text{2}$, it requires more than O((n/log n)²) time to recognize this set with bounded error probability by ONPTMs. Moreover our result is also shown to be an example of difference between nondeterministic computations and probabilistic ones.     

The r-interdiction median problem with probabilistic protection and its solution algorithm

This paper discusses the critical infrastructure protection problem in supply systems regarding potential intentional attacks. Considering that the protection of a facility cannot be always successful, we present the r-interdiction median problem with probabilistic protection. Defensive resources are allocated according to the degree of importance of service facilities. Computational experiments demonstrate the benefits brought by centralizing resources to a few critical sites, as well as the importance of introducing probabilistic factors. Furthermore, we discuss the problem in a scenario of multiple interdictors. It is found that the worst-case interdictions made by multiple interdictors may cause much more serious system impairment than a single interdictor. Such losses can sometimes be effectively alleviated by adjustment of fortification plans. To solve the problem, we propose an iterated greedy search method which produces good approximations to optimal fortification strategies rather fast, even for instances of considerable size.     

阴影衰落环境下无线传感网络的概率覆盖研究

信号传播过程中因障碍物阻挡产生的阴影衰落对无线传感器网络的覆盖产生较大的影响.针对阴影衰落环境下无线传感器网络的覆盖问题,分析了主要相关因素对网络覆盖性能产生的影响,提出了基于概率的协作感知模型,并推导出满足一定覆盖质量要求时相应的协作感知半径,进而得出所需的最少工作节点数目及其与阴影衰落强度、网络感知概率和覆盖精度之...     

The generalized center problem of resonant infinity for a polynomial differential system

This paper explores the problems of generalized center conditions and integrability of resonant infinity for a complex polynomial differential system. The method is based on converting resonant infinity into an elementary singular point by a homeomorphic transformation. The calculation of generalized singular point quantities is an effective way of finding necessary conditions for integrable systems. A new recursive algorithm for computing generalized singular point quantities at the origin of the transformed system is derived. At the same time, a necessary and sufficient condition for resonant infinity to be a generalized complex center is presented. As an application of the new recursive algorithm, the generalized center conditions for resonant infinity for a class of cubic systems are discussed. To the best of our knowledge, this is the first time that the generalized center problem has been considered for p:−q resonant infinity.     

不确定条件下配送回收中心选址配送问题研究

针对制造商、零售商、一个废弃处理中心和多个配送回收中心构成的闭环供应链,解决模糊随机环境下的配送回收中心选址配送问题。引用模糊随机理论处理产品回收率和可再利用率随机变量,以成本最低和碳排放最小为双重目标,以设施能力,设施间流量以及设施数量为约束,建立多目标闭环供应链配送回收中心选址配送模型。改进了全局-局部-邻域粒子群算法,设计了基于优先级的全局-局部-邻域粒子群算法方案,并用案例验证了模型及算法的有效性和先进性。     

A flexible heuristic for a multi-mode capital constrained project scheduling problem with probabilistic cash inflows

We consider housing projects where an initial capital covers activity expenditures in the starting phase of the project and then, customers who arrive randomly over the project span provide the necessary funds for continuation. The goal is to maximize financial returns, i.e., the project Net Present Value (NPV). Here, capital is considered as a limited nonrenewable resource which is reduced by activity expenditures and augmented by the sales of flats. Activities may be carried out in different operating modes with different durations. The total cost of an activity is fixed irrespective of its operating mode. Thus, the rate of activity expenditures differ from mode to mode. As the previous scheduling decisions are the only controllable factors affecting the available capital at any period, it is important to adjust the speed of expenditures, namely, to select the correct activity modes. The contractor, never sure of the timing of the cash inflows, has to schedule the activities in modes which do not lead to financial bottlenecks and at the same time he has to deliver the project on time. The contractor may also borrow capital from an external source. We propose a flexible heuristic algorithm for solving the capital constrained mode selection problem where there exist general precedence relationships among activities and the magnitude of precedence lags depend on the specific activity mode selected. The algorithm is flexible in the sense that different mode selection criteria are utilized at different decision times depending on the cumulative progress of the project and on some parameters controlled by the contractor. The proposed algorithm may be used as a simulation tool to adjust parameters before the project starts or it may be used as a scheduler during the progress of the project given the current financial situation and cumulative project work done. We test the algorithm by using a typical housing project with real data and also by using hypothetical test problems. The results indicate that the schedules generated are satisfactory with regard to meeting the target project due date and maximizing NPV.     

Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines

The probabilistic traveling salesman problem with deadlines (PTSPD) is an extension of the well-known probabilistic traveling salesman problem in which, in addition to stochastic presence, customers must also be visited before a known deadline. For realistically sized instances, the problem is impossible to solve exactly, and local-search methods struggle due to the time required to evaluate the objective function. Because computing the deadline violations is the most time consuming part of the objective, we focus on developing approximations for the computation of deadline violations. These approximations can be imbedded in a variety of local-search methods, and we perform experiments comparing their performance using a 1-shift neighborhood. These computational experiments show that the approximation methods lead to significant runtime improvements without loss in quality.     

Fast computation of smallest enclosing circle with center on a query line segment

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,pn} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765-776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).     

Variable neighborhood search for a planning problem with resource constraints in a health simulation center

Applied Intelligence - In this paper we propose the Variable Neighborhood Search (VNS) algorithm SimULS to solve a planning problem in the Health Simulation Center SimUSanté. This center...