随机需求下的选址一库存配送系统集成规划模型及算法

研究了随机需求条件下由单供应商、候选分拨中心和分销点构成的选址-库存问题,分销点、分拨中心分别基于周期检查(R,s,Q)和连续检查(s,S)库存控制策略．综合考虑库存成本、运输成本和设施成本之间的均衡关系,建立了二级库存与无能力约束选址集成规划模型．给出了适合求解实际规模问题的拉格朗日松弛算法,提出了求解子问题的有效启发式方法,改进了次梯度优化方法．通过仿真试验验证了模型的正确性和算法的有效性．最后讨论了相对于传统规划方法,需求方差、服务水平、持有成本、提前期等关键库存控制参数对系统运营成本节约的影响规律．     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

On minimax-regret Huff location models

We address the following single-facility location problem: a firm is entering into a market by locating one facility in a region of the plane. The demand captured from each user by the facility will be proportional to the users buying power and inversely proportional to a function of the user-facility distance. Uncertainty exists on the buying power (weight) of the users. This is modeled by assuming that a set of scenarios exists, each scenario corresponding to a weight realization. The objective is to locate the facility following the Savage criterion, i.e., the minimax-regret location is sought. The problem is formulated as a global optimization problem with objective written as difference of two convex monotonic functions. The numerical results obtained show that a branch and bound using this new method for obtaining bounds clearly outperforms benchmark procedures.     

Primal–Dual Algorithms for Connected Facility Location Problems

We consider the Connected Facility Location problem. We are given a graph $G = (V,E)$ with costs $\{c_e\}$ on the edges, a set of facilities $\F \subseteq V$, and a set of clients $\D \subseteq V$. Facility $i$ has a facility opening cost $f_i$ and client $j$ has $d_j$ units of demand. We are also given a parameter $M\geq 1$. A solution opens some facilities, say $F$, assigns each client $j$ to an open facility $i(j)$, and connects the open facilities by a Steiner tree $T$. The total cost incurred is ${\sum}_{i\in F} f_i+ sum_{j\in\D} d_jc_{i(j)j}+M\sum_{e\in T}c_e$. We want a solution of minimum cost. A special case of this problem is when all opening costs are 0 and facilities may be opened anywhere, i.e., $\F=V$. If we know a facility $v$ that is open, then the problem becomes a special case of the single-sink buy-at-bulk problem with two cable types, also known as the rent-or-buy problem. We give the first primal–dual algorithms for these problems and achieve the best known approximation guarantees. We give an 8.55-approximation algorithm for the connected facility location problem and a 4.55-approximation algorithm for the rent-or-buy problem. Previously the best approximation factors for these problems were 10.66 and 9.001, respectively. Further, these results were not combinatorial—they were obtained by solving an exponential size linear rogramming relaxation. Our algorithm integrates the primal–dual approaches for the facility location problem and the Steiner tree problem. We also consider the connected $k$-median problem and give a constant-factor approximation by using our primal–dual algorithm for connected facility location. We generalize our results to an edge capacitated variant of these problems and give a constant-factor approximation for these variants.     

工厂地址集中的k-种产品选址问题的近似算法

k-种产品工厂选址问题是：给定一个客户集合和一个可以建立工厂的地址集合,每个客户需要k-种产品,一个工厂只能为客户提供一种产品。考虑的工厂假设相对集中,即假设任何工厂之间的距离都不大于工厂与客户之间的距离。对于没有建厂费用的问题,当k=2时证明了它是一个NP完全问题,对任意的k给出了一个最坏性能比不大于2-1/k的近似算法。对于有建厂费用的问题,给出了一个最坏性能比不大于2的近似算法。     

Moving object detection and tracking by using annealed background subtraction method in videos: Performance optimization

In computer vision, moving object detection and tracking methods are the most important preliminary steps for higher-level video analysis applications. In this frame, background subtraction (BS) method is a well-known method in video processing and it is based on frame differencing. The basic idea is to subtract the current frame from a background image and to classify each pixel either as foreground or background by comparing the difference with a threshold. Therefore, the moving object is detected and tracked by using frame differencing and by learning an updated background model. In addition, simulated annealing (SA) is an optimization technique for soft computing in the artificial intelligence area. The p-median problem is a basic model of discrete location theory of operational research (OR) area. It is a NP-hard combinatorial optimization problem. The main aim in the p-median problem is to find p number facility locations, minimize the total weighted distance between demand points (nodes) and the closest facilities to demand points. The SA method is used to solve the p-median problem as a probabilistic metaheuristic. In this paper, an SA-based hybrid method called entropy-based SA (EbSA) is developed for performance optimization of BS, which is used to detect and track object(s) in videos. The SA modification to the BS method (SA-BS) is proposed in this study to determine the optimal threshold for the foreground-background (i.e., bi-level) segmentation and to learn background model for object detection. At these segmentation and learning stages, all of the optimization problems considered in this study are taken as p-median problems. Performances of SA-BS and regular BS methods are measured using four videoclips. Therefore, these results are evaluated quantitatively as the overall results of the given method. The obtained performance results and statistical analysis (i.e., Wilcoxon median test) show that our proposed method is more preferable than regular BS method. Meanwhile, the contribution of this study is discussed.     

Parallel island based Memetic Algorithm with Lin–Kernighan local search for a real-life Two-Echelon Heterogeneous Vehicle Routing Problem based on Brazilian wholesale companies

This paper deals with a Two-Echelon Fixed Fleet Heterogeneous Vehicle Routing Problem (2E-HVRP) faced by Brazilian wholesale companies. Vehicle routing problems with more than one phase are known as Multi-Echelon VRP and consider situations in which freight is moved through some intermediate facilities (e.g., cross-docks or distribution centers) before reaching its destination. The first phase of the problem dealt here is to choose a first-level vehicle, from an heterogeneous set, that will leave a depot and reach an intermediate uncapacitated facility (satellite) to serve a set of second-level vehicles. After that, it is necessary to define routes for smaller vehicles, also from an heterogeneous set, that will visit a set of customers departing from and returning to a satellite. The solution proposed here is an efficient island based memetic algorithm with a local search procedure based on Lin–Kernighan heuristic (IBMA-LK). In order to attest the algorithm’s efficiency, first it was tested in single echelon HVRP benchmark instances. After that the instances were adapted for two-echelon context and used for 2E-HVRP validation and, finally, it was tested on 2E-HVRP instances created using real world normalized data. Localsolver tool was also executed for comparison purposes. Promising results (which corroborate results obtained on the real problem) and future works are presented and discussed.     

A global approach for designing reliable WDM networks and grooming the traffic

In this paper, we address the global problem of designing reliable wavelength division multiplexing (WDM) networks including the traffic grooming. This global problem consists in finding the number of optical fibers between each pair of optical nodes, finding the configuration of each node with respect to transponders, finding the virtual topology (i.e., the set of lightpaths), routing the lightpaths, grooming the traffic (i.e, grouping the connections and routing them over the lightpaths) and, finally, assigning wavelengths to the lightpaths. Instead of partitioning the problem into subproblems and solving them successively, we propose a mathematical programming model that addresses it as a whole. Numerical results are presented and analyzed.     

Computational comparison of two formulations for dynamic supply chain reconfiguration with capacity expansion and contraction

The strategic dynamic supply chain reconfiguration (DSCR) problem is to prescribe the location and capacity of each facility, select links used for transportation, and plan material flows through the supply chain, including production, inventory, backorder, and outsourcing levels. The objective is to minimize total cost. The network must be dynamically reconfigured (i.e., by opening facilities, expanding and/or contracting their capacities, and closing facilities) over time to accommodate changing trends in demand and/or costs. The problem involves a multi-period, multi-product, multi-echelon supply chain. Research objectives of this paper are a traditional formulation and a network-based model of the DSCR problem; tests to promote intuitive interpretation of our models; tests to identify computational characteristics of each model to determine if one offers superior solvability; and tests to identify sensitivity of run time relative to primary parameters.     

New designing of cryptosystems based on quadratic fields

This paper proposes a method to construct new kind of non-maximal imaginary quadratic order （NIQO＊） by combining the technique of Diophantine equation and the characters of non-maximal imaginary quadratic order. It is proved that in the class group of this new kind of NIQO＊, it is very easy to design provable secure cryptosystems based on quadratic field （QF）. With the purpose to prove that this new kind of QF-based cryptosystems are easy to implement, two concrete schemes are presented, i.e., a Schnorr-like signature and an EIGamel-like encryption, by using the proposed NIQO＊. In the random oracle model, it is proved that： （1） under the assumption that the discrete logarithm problem over class groups （CL-DLP） of this new kind of NIQO＊ is intractable, the proposed signature scheme is secure against adaptive chosen-message attacks, i.e., achieving UF-CMA security; （2） under the assumption that the decisional Diffie-Hellman problem over class groups （CL-DDH） of this new kind of NIQO＊ is intractable, the enhanced encryption in this paper is secure against adaptive chosen-ciphertext attacks, i.e., reaching IND-CCA2 security.     

随机需求下的选址－库存配送系统集成规划模型及算法

研究了随机需求条件下由单供应商、候选分拨中心和分销点构成的选址－库存问题, 分销点、分拨中心分别基于周期检查(R, s,Q)和连续检查(s, S)库存控制策略. 综合考虑库存成本、运输成本和设施成本之间的均衡关系, 建立了二级库存与无能力约束选址集成规划模型. 给出了适合求解实际规模问题的拉格朗日松弛算法, 提出了求解子问题的有效启发式方法, 改进了次梯度优化方法. 通过仿真试验验证了模型的正确性和算法的有效性. 最后讨论了相对于传统规划方法, 需求方差、服务水平、持有成本、提前期等关键库存控制参数对系统运营成本节约的影响规律.     

A Simple Optimal Solution for the Temporal Precedence Problem on Pure Pointer Machines

In this paper we propose an optimal solution to the Temporal Precedence problem—i.e., the problem of managing the dynamic insertion of elements in a collection and the ability to determine, given two elements, which one has been inserted first. The problem is studied on pure pointer machines, i.e., pointer machines with no arithmetic capabilities. We provide an optimal solution (i.e., O(lg lg n) worst case time per operation, if n is the number of insertions) for this problem that is considerably simpler than the solutions previously presented in the literature. We also show how the solution can be improved to allow worst case O(1) insertions and linear space complexity.     

Edge detection and curvature calculation in the visual system

A new model of edge detection in a visual system is presented, where the edge locations are assumed to be at the place of negative peaks of ▿²G * I. Related schemes of detecting edges and calculating the curvature of the edge locus are also presented. It is assumed that the locations of receptive field centers of geniculate cells move with an input image. The arrangement of the receptive fields is given as a solution of an optimization problem. An edge detection algorithm based on the arrangement is presented. The edge detection algorithms are applied to three examples, i.e., Helmholtz irradiation, a face image, and a circular one.This work was presented, in part, at the 9th International Symposium on Artificial Life and Robotics, Oita, Japan, January 28–30, 2004     

A fuzzy clustering-based hybrid method for a multi-facility location problem

A fuzzy clustering-based hybrid method for a multi-facility location problem is presented in this study. It is assumed that capacity of each facility is unlimited. The method uses different approaches sequentially. Initially, customers are grouped by spherical and elliptical fuzzy cluster analysis methods in respect to their geographical locations. Different numbers of clusters are experimented. Then facilities are located at the proposed cluster centers. Finally each cluster is solved as a single facility location problem. The center of gravity method, which optimizes transportation costs is employed to fine tune the facility location. In order to compare logistical performance of the method, a real world data is gathered. Results of existing and proposed locations are reported.     

Methods for computing Nash equilibria of a location–quantity game

A two-stage model is described where firms take decisions on where to locate their facility and on how much to supply to which market. In such models in literature, typically the market price reacts linearly on supply. Often two competing suppliers are assumed or several that are homogeneous, i.e., their cost structure is assumed to be identical. The focus of this paper is on developing methods to compute equilibria of the model where more than two suppliers are competing that each have their own cost structure, i.e., they are heterogeneous. Analytical results are presented with respect to optimality conditions for the Nash equilibria in the two stages. Based on these analytical results, an enumeration algorithm and a local search algorithm are developed to find equilibria. Numerical cases are used to illustrate the results and the viability of the algorithms. The methods find an improvement of a result reported in literature.     

Can DSS evolve without changing our view of the concept of ‘problem’?

DSS have almost exclusively been presented in the context of problem solving. But the term ‘problem’ is never defined. It is unfortunately a fairly ambiguous term whose meaning oscillates from the observation of an unsatisfactory, objective reality which must be corrected, to the subjective representation of one or more actors faced with a reality which he or they perceived as unsatisfactory. The first of these interpretations (i.e., a problem as an unsatisfactory objective reality) implicitly dominates the DSS literature and design methods, which does not avoid the hidden major stumbling block of ‘problem definition’. We believe that the adoption of the second interpretation (i.e., a problem as a subjective representation) is a better guarantee of the effectiveness of DSS and leads to different design methods (we propose one based on a systemic method oriented towards ‘soft problems’) and opens new horizons for potential application to DSS.     

考虑拥挤情景的小城镇已有应急公共服务设施功能优化问题——以山东省滕州市为例

针对在小城镇应急医疗服务中心功能优化问题的研究中没有考虑拥挤情景的现实, 构建了新的更能反映现实问题本质的考虑拥挤情景的小城镇已有应急公共服务设施功能优化模型; 并设计启发式算法求解, 以山东省滕州市已有应急医疗中心功能优化为例进行实证。最后, 提出所建模型可在考虑新建、多因素、等级等方面作进一步拓展研究。     

Fusion of preferences from different perspectives in a decision-making context

Solving a decision-making problem about a brand-new product might include preferences from a high number of potential customers (e.g., followers of a company on social media) and managerial constraints (or preferences) given by corporate managers with regard to different aspects (i.e., economical, technical, environmental, etc.) over multiple criteria (e.g., weight, capacity, color, or usefulness of a product). These give us some new insights on fusing preferences given by persons having different perspectives (e.g., economical, technical, environmental, etc.), including decision-makers, and aimed to be suitable for different organizational structures (e.g., multilevel structures). Herein, a proper representation is needed to merge preferences from each perspective, enabling their propagation, throughout an organizational structure until the level in which a decision is made. This representation is presented as a decision-making unit (DMU), and is used as the primary component of our decision-making model. In this paper, we propose a novel decision-making model that recursively merges the preferred criteria from different DMUs using the logic scoring of preference (LSP) method. An illustrative example demonstrating the applicability of the proposed model, in the context of a new product design, is included in the paper.     

集成整车物流系统的网络规划问题研究

综合考虑运输、库存、设施、服务质量等决策因素，建立了整车物流网络规划集成优化模型，针对由工厂、集货中心和分销中心构成的基本物流网络，提出了用于运输路径优化的流预测算法，并嵌入到遗传算法，解决了适应值的计算难点，给出了基于流预测的遗传算法求解框架．通过实例分析了运输规模效应、库存控制策略、服务质量指标等因素对物流网络结构设计方案的影响。