China
Africa
Explore chapters and articles related to this topic
Orienteering and Coverage
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
Differently from ground vehicles, the UAV has to fly along the road only to cover a certain edge that is not connected. This modified search problem can be formulated as a multi-choice multidimensional knapsack problem, which is to find an optimal solution minimizing flight time. Classical multi-dimensional knapsack problem is to pick up items for knapsacks for maximum total values so that the total resource required does not exceed the resource constraint of knapsacks. For applying multi-dimensional knapsack problem to the road network search, UAVs are assumed as the knapsacks, the roads to be searched are resources and limited flight time or energy of each UAV is the capacity of knapsacks. Multi-dimensional knapsack problem formulation allows to consider the limitations of each UAV flight time and different types of roads, vehicles and minimum turning radius and get the sub-optimal solution of the coordinated road search assignment. Moreover, for fixed-wing UAVs, the Dubins path planning produces the shortest and flyable paths taking into consideration their dynamical constraints; thus, the Dubins path is used to calculate the cost function of the modified search problem [13].
Orienteering and Coverage
Published in Yasmina Bestaoui Sebbane, Intelligent Autonomy of Uavs, 2018
Differently from ground vehicles, the UAV has to fly along the road only to cover a certain edge which is not connected. This modified search problem can be formulated as a multi-choice multi-dimensional knapsack problem which is to find an optimal solution minimizing flight time. Classical multidimensional knapsack problem is to pick up items for knapsacks for maximum total values so that the total resource required does not exceed the resource constraint of knapsacks. For applying multi-dimensional knapsack problem to the road network search, UAVs are assumed as the knapsacks, the roads to be searched are resources and limited flight time or energy of each UAV is capacity of knapsacks. Multi-dimensional knapsack problem formulation allows to consider the limitations of each UAV flight time and different types of roads, vehicles and minimum turning radius and get the sub-optimal solution of the coordinated road search assignment. Moreover, for fixed-wing UAVs, the Dubins path planning produces the shortest and flyable paths taking into consideration their dynamical constraints, thus the Dubins path is used to calculate the cost function of the modified search problem [6].
Evolutionary Learning
Published in Stephen Marsland, Machine Learning, 2014
These items are all described in the following sections, and the basic algorithm is described. We are going to use an example to describe the methods, which is an NP-complete problem (if you are not familiar with the term NP-complete, its practical implication is that the problem runs in exponential time or worse in the number of inputs) known as the knapsack problem (a knapsack is a rather old name for a rucksack or bag). Sections 10.3.1 and 10.3.4 provide other examples. The knapsack problem is easy to describe, but difficult to solve in general. Here is the version of it that we will use:
The min–max order picking problem in synchronised dynamic zone-picking systems
Published in International Journal of Production Research, 2023
Serhat Saylam, Melih Çelik, Haldun Süral
The objective for the knapsack problem is to select a subset of items to maximise the total value while satisfying the capacity constraint. value function stated as the following recursive formula refers to the knapsack DP algorithm: where the base cases are for and for . Since we would like to reach as close as possible to half of the knapsack capacity,, we aim to choose a subset of connection type 3 intra-aisle movements from first aisles, take it from picker 1 and give it to picker 2 to minimise the difference between two pickers. To solve this problem, we use another value function storing the actual difference. Such values can be stored at value function as:
High-Dimensional Cost-constrained Regression Via Nonconvex Optimization
Published in Technometrics, 2022
The 0-1 knapsack problem is a famous problem in combinatorial optimization, and has been extensively studied (see, e.g., chapter 8 in the book of Paschos (2013) and the references therein) in the operations research community. It is the problem of choosing a subset of p items such that the corresponding profit sum is maximized without having the weight sum to exceed a prespecified capacity C. Although this problem is NP-hard, algorithmic advances and hardware improvements enable us to solve it efficiently. For example, dynamic programming (Bellman 1966) is a popular algorithm to exactly solve the 0-1 knapsack problem. Theoretically, it is a pseudo-polynomial time algorithm and the complexity is O(pC). Numerically, as shown in Martello, Pisinger, and Toth (1999), the hybrid algorithm combining dynamic programming and the branch-and-bound approach (Nauss 1976) is able to solve many test datasets, with up to 10,000 variables, in less than 0.2 s.
An efficient algorithm for the precedence constraint knapsack problem with reference to large-scale open-pit mining pushback design
Published in Mining Technology, 2021
Nayan Maiti, Pranjal Pathak, Biswajit Samanta
Typically in a Knapsack problem, a subset of given items are selected in the Knapsack such that the profit sum of the selected items is maximized. Let be the set of items that are included in a knapsack with capacity . Each item is associated with a positive weight and a numerical profit and a set of precedence among the items. Item implies that item can be chosen only when has been included in the selection. Without loss of generality, let assume that . Let be a decision variable such that