This paper presents an approach to optimal routing with resource assignment for traveling among scattered farm fields. To this end, a road network among farm fields is created, which has data on shortest paths of all ...
详细信息
This paper presents an approach to optimal routing with resource assignment for traveling among scattered farm fields. To this end, a road network among farm fields is created, which has data on shortest paths of all pairs of fields and its distances. Two types of multiple traveling salesman problem (mTSP) formulations solved by an exact algorithm are presented to perform optimal routing. The proposed approach is demonstrated through a numerical experiment using data from an agricultural corporation considered in this paper. The results show features of the mTSP formulations and the proposed approach can yield the optimal routes within 2.4 seconds. Hence the proposed approach is feasible for use in actual daily work.
In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of n points in the plane. A double-strip is a closed region in the plane whose boundary ...
详细信息
In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of n points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are O(n(2)) and O(n(3) log n)-time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen. (c) 2020 Elsevier B.V. All rights reserved.
We propose in this paper a new formulation for the stability of the Traveling Salesman Problem (TSP) compared with its probabilistic version, the Probabilistic Traveling Salesman Problem (PTSP). It is a real extension...
详细信息
We propose in this paper a new formulation for the stability of the Traveling Salesman Problem (TSP) compared with its probabilistic version, the Probabilistic Traveling Salesman Problem (PTSP). It is a real extension of the TSP, where the number of customers to be served each time is a random variable. That is only a subset of customers will need its services, moreover this subset varies from day to day. From the literature, several methods of resolution of the TSP have been proposed. In order to use these methods as they are for the PTSP came the idea of the study of stability. It is interested in finding cases where the solution for the TSP is also for the PTSP. First we survey and comment a number of easy TSPs. We also present via the notion of & x201C;Master tour& x201D;the stable problems in the TSP-PTSP context. An exact Branch and Bound is used for recognizing the TSPs that are not stable. Finally, we propose a new modification method, -different from the usual method of PTSP-, called the method of Taxi Driver, it takes the structure of the tour into consideration.
In the classical Euclidean Steiner minimum tree (SMT) problem, we are given a set of points in the Euclidean plane and we are supposed to find the minimum length tree that connects all these points, allowing the addit...
详细信息
In the classical Euclidean Steiner minimum tree (SMT) problem, we are given a set of points in the Euclidean plane and we are supposed to find the minimum length tree that connects all these points, allowing the addition of arbitrary additional points. We investigate the variant of the problem where the input is a set of line segments. We allow these segments to have length 0, i.e., they are points and hence we generalize the classical problem. Furthermore, they are allowed to intersect such that we can model polygonal input. As in the GeoSteiner approach of Juhl et al. (Math Program Comput 10(2):487-532, 2018) for the classical case, we use a two-phase approach where we construct a superset of so-called full components of an SMT in the first phase. We prove a structural theorem for these full components, which allows us to use almost the same GeoSteiner algorithm as in the classical SMT problem. The second phase, the selection of a minimal cost subset of constructed full components, is exactly the same as in GeoSteiner approach. Finally, we report some experimental results that show that our approach is more efficient than the approximate solution that is obtained by sampling the segments.
Background and Objective: In the last two decades there can be observed a rapid development of systems biology. The basis of systems methods is a formal model of an analyzed system. It can be created in a language of ...
详细信息
Background and Objective: In the last two decades there can be observed a rapid development of systems biology. The basis of systems methods is a formal model of an analyzed system. It can be created in a language of some branch of mathematics and recently Petri net-based biological models seem to be especially promising since they have a great expressive power. One of the methods of analysis of such models is based on transition invariants. They correspond to some subprocesses which do not change a state of the modeled biological system. During such analysis, a need arose to study the subsets of transitions, what leads to interesting combinatorial problems - which have been considered in theory and *** & Results: Two problems of anti-occurrence were considered. These problems concern a set of transitions which is not a subset of any of t-invariant supports or is not a subset of t-invariant supports from some collection of such supports. They are defined in a formal way, their computational complexity is analyzed and an exact algorithm is provided for one of ***: A comprehensive analysis of complex biological phenomena is challenging. Finding elementary processes that do not affect subprocesses belonging to the entire studied biological system may be necessary for a complete understanding of such a model and it is possible thanks to the proposed algorithm.
The two-dimensional vector packing problem is a well-known generalization of the classical bin packing problem. It considers two attributes for each item and bin. Two capacity constraints must be satisfied in a feasib...
详细信息
The two-dimensional vector packing problem is a well-known generalization of the classical bin packing problem. It considers two attributes for each item and bin. Two capacity constraints must be satisfied in a feasible packing solution for each bin. The objective is to minimize the number of bins used. To compute optimal solutions for the problem, we propose a new branch-and-price algorithm. A goal cut that sets a lower bound to the objective is used. It is effective in speeding up column generation by reducing the number of iterations. To efficiently solve the pricing problem, we develop a branch-and-bound method with dynamic programming, which first eliminates conflicts between two items through branching, and then solves the two-constraint knapsack problem at leaf nodes through dynamic programming. Extensive computational experiments were conducted based on 400 test instances from existing literature. Our algorithm significantly outperformed the existing branch-and-price algorithms. Most of the test instances were solved within just a few seconds. (C) 2019 Elsevier B.V. All rights reserved.
The use of unmanned aerial vehicles (UAVs) has recently increased both in civilian and military operations, and the planning of their routes is critical. This research investigates a routing problem in which a UAV net...
详细信息
The use of unmanned aerial vehicles (UAVs) has recently increased both in civilian and military operations, and the planning of their routes is critical. This research investigates a routing problem in which a UAV network, equipped with sensors, covers a given area and maintains connectivity with its neighbouring UAVs and the base station, while respecting to the UAVs lifetime. To cover the area, two integer linear programming models are formulated to solve two problems optimally. In the first one, covering means that all positions should be visited. However, in the second one, covering means that every position should be covered at least by one UAV. Due to the limited communication radius of the UAVs, connectivity then has to find inter-UAVs routing paths to satisfy the communication between UAVs and the base. We verify by experiments that the models, using Cplex, can provide an optimal solution of different area dimensions.
This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unman...
详细信息
This study investigates a clustered coverage orienteering problem (CCOP), which is a generalization of the classical orienteering problem. The problem is widely motivated by the emerging unmanned techniques (eg, unmanned surface vehicles and drones) applied to environmental monitoring. Specifically, the unmanned surface vehicles (USVs) are used to monitor reservoir water quality by collecting samples. In the CCOP, the water sampling sites (ie, the nodes) are grouped into clusters, and a minimum number of nodes must be visited in each cluster. With each node representing a certain coverage area of the water, the objective of the CCOP is to monitor as much as possible the total coverage area in one tour of the USV, considering that overlapping areas provide no additional information. An integer programming model is first formulated through a linearization procedure that captures the overlapping feature. A two-stage exact algorithm is proposed to obtain an optimal solution to the problem. The efficiency and effectiveness of the two-stage exact algorithm are demonstrated through experiments on randomly generated instances. The algorithm can effectively solve instances with up to 60 sampling sites.
In this paper, parallelization techniques are proposed for the branch-and-bound algorithm OTClique for the maximum weight clique problem. OTClique consists of the precomputation phase and the branch-and-bound phase. T...
详细信息
In this paper, parallelization techniques are proposed for the branch-and-bound algorithm OTClique for the maximum weight clique problem. OTClique consists of the precomputation phase and the branch-and-bound phase. The proposed algorithm parallelizes both of them. In the precomputation phase, the construction of optimal tables is parallelized. In the branch-and-bound phase, the proposed algorithm generates small subproblems and assigns them to threads. A technique to share lower and upper bounds is also proposed. Experiments using some benchmarks show that the proposed parallelization techniques improve the performance of OTClique. With an 8-core CPU, the computation time of OTClique becomes 6.91 times shorter on random graphs and 5.38 times on DIMACS benchmarks on average. (C) 2021 Elsevier B.V. All rights reserved.
In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three ...
详细信息
In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time. (C) 2013 Elsevier Ltd. All rights reserved.
暂无评论