The mixed evacuation problem

A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sources and sinks. Then the goal of this problem is to find a minimum time limit such that we can send the right amount of flow from sources to sinks. In this paper, we introduce a variant of this problem called the mixed evacuation problem. This problem models an emergent situation in which people can evacuate on foot or by car. The goal is to organize such a mixed evacuation so that an efficient evacuation can be achieved. In this paper, we study this problem from the theoretical and practical viewpoints. In the first part, we prove the polynomial-time solvability of this problem in the case where the number of sources and sinks is not large, and also prove the polynomial-time solvability and computational hardness of its variants with integer constraints. In the second part, we apply our model to the case study of Minabe town in Wakayama prefecture, Japan.     

The three-dimensional matching problem in Kalmanson matrices

We investigate the computational complexity of several special cases of the three-dimensional matching problem where the costs are decomposable and determined by a so-called Kalmanson matrix. For the minimization version we develop an efficient polynomial time algorithm that is based on dynamic programming. For the maximization version, we show that there is a universally optimal matching (whose structure is independent of the particular Kalmanson matrix).     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.     

A spanning heuristic for the unordered and ordered matching identification problem

The matching identification problem (MIP) is a combinatoric search problem related to the fields of learning from examples, boolean functions, and knowledge acquisition. The MIP involves identifying a single “goal” item from a large set of items. Because there is commonly a cost associated with evaluating each guess, the goal item should be identified in as few guesses as possible. As in most search problems, the items have a similar structure, which allows an evaluation of each guessed item. In other words, each guessed item elicits partial information about the goal item, i.e. how similar the guess is to the goal. With this information the goal is more quickly identified.The unordered MIP has been studied by Mehrez and Steinberg (ORSA J. Comput. 7 (1995) 211) in which they proposed two different types of algorithms. The purpose of the present paper is to suggest an improved Spanning Heuristic algorithm. Its improvement increases as the problem size increases. Further results and comparisons are derived for the unordered and ordered cases.This research shows that when the search space is very large, it is better to inquire from items that are known not to be the goal (they have been ruled out by previous guesses), for the purpose of acquiring more information about the goal. As the search space is narrowed, it is better to guess items that have not been ruled out.     

An exponential (matching based) neighborhood for the vehicle routing problem

We introduce an exponential neighborhood for the Vehicle Routing Problem (vrp) with unit customers’ demands, and we show that it can be explored efficiently in polynomial time by reducing its exploration to a particular case of the Restricted Complete Matching (rcm) problem that we prove to be polynomial time solvable using flow techniques. Furthermore, we show that in the general case with non-unit customers’ demands the exploration of the neighborhood becomes an -hard problem.     

A mixed integer programming and heuristic algorithm for a warehouses location problem

A warehouses location problem is treated using a mixed integer programming and a heuristic algorithm. A simplification of freight rates schedules, based upon shipments consolidation and a linear regression of rates vs distances was made. Warehousing costs were divided according to fixed and variable and related to the throughput of the warehouses. Consideration was given in the analysis to the choice between owning and leasing each warehouse. In the case studied, the analysis demonstrated that a possible saving of approximately 22 per cent in annual distribution costs could be realized under the optimized warehouse location network.     

Stable matching problems with exchange restrictions

We study variants of classical stable matching problems in which there is an additional requirement for a stable matching, namely that there should not be two participants who would prefer to exchange partners. The problem is motivated by the experience of real-world medical matching schemes that use stable matchings, where cases have arisen in which two participants discovered that each of them would prefer the other’s allocation, a situation that is seen as unfair. Our main result is that the problem of deciding whether an instance of the classical stable marriage problem admits a stable matching, with the additional property that no two men would prefer to exchange partners, is NP-complete. This implies a similar result for more general problems, such as the hospitals/residents problem, the many-to-one extension of stable marriage. Unlike previous NP-hardness results for variants of stable marriage, the proof exploits the powerful algebraic structure underlying the set of all stable matchings. In practical matching schemes, however, applicants’ preference lists are typically of short fixed length, and we describe a linear time algorithm for the problem in the special case where all of the men’s preference lists are of length ≤3.     

An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

Congestion games with mixed objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.     

Online bottleneck matching

We consider the online bottleneck matching problem, where $k$ server-vertices lie in a metric space and $k$ request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its server. Because no algorithm can have a competitive ratio better than $O(k)$ for this problem, we use resource augmentation analysis to examine the performance of three algorithms: the naive Greedy algorithm, Permutation, and Balance. We show that while the competitive ratio of Greedy improves from exponential (when each server-vertex has one server) to linear (when each server-vertex has two servers), the competitive ratio of Permutation remains linear when an extra server is introduced at each server-vertex. The competitive ratio of Balance is also linear with an extra server at each server-vertex, even though it has been shown that an extra server makes it constant-competitive for the min-weight matching problem.     

The problem with knowledge ambiguity

This paper proposes a new conceptualisation of the construct of knowledge ambiguity. This new conceptualisation is essential because (1) past researchers have tended to narrowly define and operationalise knowledge ambiguity in terms of causal ambiguity or tacitness and (2) the prevalent non-comprehensive conceptualisation constrains our ability to overcome the problem of knowledge ambiguity. Knowledge ambiguity has been identified as a major obstacle to effective knowledge transfer and to the implementation of overall knowledge management systems. The new conceptualisation proposes that knowledge ambiguity is composed of two types of ambiguity: component ambiguity and causal ambiguity. Component ambiguity is uncertainty about knowledge content, whereas causal ambiguity is uncertainty about how to use the knowledge. This re-conceptualisation is supported by previous studies on knowledge characteristics, absorptive capacity and cognitive learning. In this paper, theoretical propositions are developed to demonstrate the compatibility of the new conceptualisation with the current understanding of these concepts. The present paper not only advances our understanding of knowledge ambiguity, it also points towards solutions for overcoming the problems associated with knowledge ambiguity. Different measures are required to overcome problems created by component ambiguity vs. causal ambiguity. This paper’s re-conceptualisation of knowledge ambiguity makes it easier to theorise about and operationalise the concept. It aligns the definition of knowledge ambiguity with current definitions of related constructs such as absorptive ambiguity and cognitive learning that are used in the broader knowledge transfer and knowledge management literatures.     

Conservative linear programming with mixed multiple objectives

In an ordinary linear program a single objective vector is constructed and one attempts to choose a decision vector to optimize this objective. Often multiple criteria exist or exact estimates for the components of a single objective vector are not entirely clear. For these cases a conservative decision-maker may want to choose an alternative that maximizes the objective value under the worst foreseeable circumstances. Herein we develop a unified framework for applying the maximin criterion to problems with various degrees of uncertainty attached to the objective vector. Three cases are solved via linear programming: (1) Complete Information, (2) Partial Information, and (3) Total Ignorance. It is shown that the functional value of the maximin solution decreases in a convex manner with increasing uncertainty. In addition certain relationships between maximin and efficient solutions are provided. Finally, an extension to integer constrained decision variables is presented.     

A computational approach to the multi-period many-to-one matching with ties

The many-to-one matching problem is commonly referred as the hospitals/residents problem which assigns each resident a hospital in an efficient and fair way. This paper considers a multi-period hospitals/residents problem that consists of assigning positions to overlapping generations of residents. From one period to another, residents can either retain their current positions or can choose a more preferred one. In this situation, a fairness criterion is introduced with the condition of the individual rationality for the matching. Moreover, it has been proven that the matching satisfying such criterion always exists and can be obtained by iteratively eliminating Pareto improvement cycles and unjustified claim cycles from any acceptable matching. This paper presents a novel algorithm to compute a matching with minimal unjustified claims under the premise of satisfying the individual rationality and the Pareto efficiency. The complexity of the proposed algorithm is bounded by \(O(Q^{3}n^{3})\) in each period, where n and Q are the number of the residents and the total number of positions of the hospitals in the corresponding period, respectively.     

Tight bound for matching

Let M be the number of edges in a maximum matching in graphs with m edges, maximum vertex degree k and shortest simple odd-length cycle length L. We show that

The newsvendor problem with barter exchange

Barter exchange, as an alternative to move distressed inventory, has become increasingly popular in business. Many companies barter their unsold product for the product they need via barter exchange platforms at full prices. In this paper we consider the newsvendor problem with the barter exchange option. A retailer (the newsvendor) facing stochastic demand not only sells its product, but also buys other product that it needs from the market. It either trades its unsold product for the product it needs on a barter platform or disposes of its unsold product at discounted prices at the end of the selling season like in the classical newsvendor model. We derive the retailer’s optimal order quantity, then analytically and numerically examine the impacts of barter on the retailer’s inventory decisions and profit. We find that barter exchange can help the retailer to manage demand uncertainty and improve profit. The optimal order quantity decreases with barter commission and barter uncertainty, while increases with demand uncertainty and the value of the product that the retailer needs. Barter is more advantageous with lower barter commission, larger demand uncertainty, lower barter uncertainty, and higher value of the product it needs.     

带货物权重的车辆路径问题及遗传算法

考虑一个分销中心、多个零售商组成的分销网络系统中具有柔性车辆能力的带货物权重的车辆路径问题.并根据车辆的满载情况采用了不同的运输策略,即单点运输和多点运输方式.在多点运输方式下,与以往诸多研究不同的是,文章建立了一种基于货物权重的VRP模型——WVRP,即在安排车辆线路时每个零售商的货物需求量也作为一个因素考虑,尽可能使车辆优先供货需求量较大的零售商.最后,针对问题的性质,开发了一种基于划分的遗传算法PB-GA对问题进行求解,并与一般遗传算法及常用的启发式算法进行了分析比较.     

Fractional matching preclusion of graphs

Let F be an edge subset and \(F^{\prime }\) a subset of edges and vertices of a graph G. If \(G-F\) and \(G-F^{\prime }\) have no fractional perfect matchings, then F is a fractional matching preclusion (FMP) set and \(F^{\prime }\) is a fractional strong MP (FSMP) set of G. The FMP (FSMP) number of G is the minimum size of FMP (FSMP) sets of G. In this paper, the FMP number and the FSMP number of Petersen graph, complete graphs and twisted cubes are obtained, respectively.     

规模不经济下互惠偏好对闭环供应链的影响研究

本文考虑闭环供应链成员的互惠偏好行为,在生产规模不经济下分析互惠偏好行为对闭环供应链的影响,构建了包含供应商和规模不经济生产商的闭环供应链模型,分别探讨了无互惠偏好情形以及双向互惠偏好情形。研究发现,规模不经济会降低回收率和系统利润;系统成员的互惠偏好行为总会提高对方的利润,而降低自身的利润;供应商的互惠偏好总会提高系统利润,渠道效率和消费者剩余,而生产商互惠偏好产生的影响还取决于供应商的互惠态度;仅生产商具互惠偏好时,系统总利润不变;一定条件下,互惠偏好行为会对环境造成影响,但是,该行为能够有效提高整个社会的总福利。