Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
9
result(s) for
"[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]"
Sort by:
Metaphor-based metaheuristics, a call for action: the elephant in the room
Taking inspiration from natural behaviors to devise new optimization algorithms has played an important role in the history of the field of metaheuristics (Sörensen et al. 2017). Unfortunately, in the last two decades we have been witnessing a new trend by which dozens of metaphor-based metaheuristics based on the most diverse possible set of natural, artificial, social, and sometimes even supernatural phenomena and behaviors are proposed, without a clear motivation beyond the desire of their authors to publish their papers.
Journal Article
A Multi-commodity Network Flow Model for Sustainable Performance Evaluation in City Logistics: Application to the Distribution of Multi-tenant Buildings in Tokyo
The distribution of goods in crowded city centers is a major challenge. In this paper, we propose a methodology for evaluating the performance of a parcel distribution network in city logistics. This methodology encompasses the main entities of a two-tier distribution system made up of carriers, huge shopping centers (multi-tenant buildings) and intermediate depots (urban consolidation centers), as well as the parcel flows between them. This methodology aims to optimize the transport flows (distance traveled) of a given distribution network while also quantifying the impact in terms of sustainable development by measuring gas emissions. Two different states of the network with different connectivity degrees are evaluated and compared: the current state of the network as well as its future state. The transport network modeling is based on a network flow, which is expressed in linear programming and implemented with an optimization solver. The validation of this methodology is based on the parcel distribution of the Multi-tenant Buildings of the city of Tokyo. The findings are that the network with greater connectivity between the entities brings significant traveled distance reduction as well as a reduction of emissions of CO2. Another finding is that the grouping of the parcels (i.e., pooling) brings a reduction of the distance traveled compared to the transport organization without grouping and contributes to a reduction in the number of trucks.
Journal Article
Understanding Population Dynamics in Multi- and Many-Objective Evolutionary Algorithms for High-Resolution Approximations
Achieving a high-resolution approximation and hitting the Pareto optimal set with some if not all members of the population is the goal for multi- and many-objective optimization problems, and more so in real-world applications where there is also the desire to extract knowledge about the problem from this set. The task requires not only to reach the Pareto optimal set but also to be able to continue discovering new solutions, even if the population is filled with them. Particularly in many-objective problems where the population may not be able to accommodate the full Pareto optimal set. In this work, our goal is to investigate some tools to understand the behavior of algorithms once they converge and how their population size and particularities of their selection mechanism aid or hinder their ability to keep finding optimal solutions. Through the use of features that look into the population composition during the search process, we will look into the algorithm’s behavior and dynamics and extract some insights. Features are defined in terms of dominance status, membership to the Pareto optimal set, recentness of discovery, and replacement of optimal solutions. Complementing the study with features, we also look at the approximation through the accumulated number of Pareto optimal solutions found and its relationship to a common metric, the hypervolume. To generate the data for analysis, the chosen problem is MNK-landscapes with settings that make it easy to converge, enumerable for instances with 3 to 6 objectives. Studied algorithms were selected from representative multi- and many-objective optimization approaches such as Pareto dominance, relaxation of Pareto dominance, indicator-based, and decomposition.
Journal Article
Unified Polynomial Dynamic Programming Algorithms for P-Center Variants in a 2D Pareto Front
With many efficient solutions for a multi-objective optimization problem, this paper aims to cluster the Pareto Front in a given number of clusters K and to detect isolated points. K-center problems and variants are investigated with a unified formulation considering the discrete and continuous versions, partial K-center problems, and their min-sum-K-radii variants. In dimension three (or upper), this induces NP-hard complexities. In the planar case, common optimality property is proven: non-nested optimal solutions exist. This induces a common dynamic programming algorithm running in polynomial time. Specific improvements hold for some variants, such as K-center problems and min-sum K-radii on a line. When applied to N points and allowing to uncover M
Journal Article
Cops and Robbers on Dynamic Graphs: Offline and Online Case
We examine the classic game of Cops and Robbers played on models of dynamic graphs, that is, graphs evolving over discrete time steps. At each time step, a graph instance is generated as a subgraph of the underlying graph of the model. The cops and the robber take their turns on the current graph instance. The cops win if they can capture the robber at some point in time. Otherwise, the robber wins. In the offline case, the players are fully aware of the evolution sequence, up to some finite time horizon T. We provide a O(n 2k+1 T) algorithm to decide whether a given evolution sequence for an underlying graph with n vertices is k-cop-win via a reduction to a reachability game. In the online case, there is no knowledge of the evolution sequence, and the game might go on forever. Also, each generated instance is required to be connected. We provide a nearly tight characterization for sparse underlying graphs, i.e., with at most linear number of edges. We prove λ + 1 cops suffice to capture the robber in any underlying graph with n − 1 + λ edges. Further, we define a family of underlying graphs with n−1+λ edges where λ−1 cops are necessary (and sufficient) for capture.
Journal Article
A GRASP-based approach for technicians and interventions scheduling for telecommunications
The Technicians and Interventions Scheduling Problem for Telecommunications embeds the scheduling of interventions, the assignment of teams to interventions and the assignment of technicians to teams. Every intervention is characterized, among other attributes, by a priority. The objective of this problem is to schedule interventions such that the interventions with the highest priority are scheduled at the earliest time possible while satisfying a set of constraints like the precedence between some interventions and the minimum number of technicians needed with the required skill levels for the intervention. We present a Greedy Randomized Adaptive Search Procedure (GRASP) for solving this problem. In the proposed implementation, we integrate learning to the GRASP framework in order to generate good-quality solutions using information brought by previous ones. We also compute lower bounds and present experimental results that validate the effectiveness of this approach.
Journal Article
Vertex order with optimal number of adjacent predecessors
In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥ K + 1 and U ≥ 2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete.
Journal Article
Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts
Total dominating set, connected vertex cover and Steiner tree are well-known graph problems. Despite the fact that they are NP-complete to optimize, it is easy (even trivial) to find solutions, regardless of their size. In this paper, we study a variant of these problems by adding conflicts, that are pairs of vertices that cannot be both in a solution. This new constraint leads to situations where it is NP-complete to decide if there exists a solution avoiding conflicts. This paper proposes NP-completeness proofs of the existence of a solution for different restricted classes of graphs and conflicts, improving recent results. We also propose polynomial time constructions in several restricted cases and we introduce a new parameter, the stretch, to capture the locality of the conflicts.
Journal Article