China
Africa
Explore chapters and articles related to this topic
Heuristic and metaheuristic algorithms
Published in Dušan Teodorović, Miloš Nikolić, Quantitative Methods in Transportation, 2020
Dušan Teodorović, Miloš Nikolić
A large number of real-world transportation problems have been formulated and solved by integer programming, dynamic programming, and graph theory techniques over the past five decades. It is essential to note, however, that the majority of the real-world problems solved by some of the optimization techniques were low dimensional in nature. A lot of engineering and control problems are combinatorial by their very nature. The majority of the combinatorial optimization problems are hard to solve, either because of their high dimensionality or because it is not easy to break them down into smaller sub-problems. Representatives of this type of problem are vehicle fleet planning, vehicle routing and scheduling, crew scheduling, transportation network design, location problems, and optimizing alignments for highways and public transportation routes through complex geographic spaces, etc.
Miscellaneous
Published in Dan Zwillinger, CRC Standard Mathematical Tables and Formulas, 2018
Heuristic search techniques are commonly used for combinatorial optimization problems. A method starts with an initial vector x0 and attempts to find improved solutions. Define x to be the current solution vector, f(x) to be its objective value and N(x) to be its neighborhood. For the remainder of this section, assume that we seek the minimum value of f(x) . In each iteration of a neighborhood search algorithm, we generate a number of solutions x’ ∊ N(x) , and compare f(x) with each f(x’) . If f(x’) is a better value than f(x) , then we update the current solution to x’ (termed accepting x’) and we iterate again searching from x’. The process continues until none of the generated neighbors of the current solution yield lower solutions. Common improvement procedures such as pairwise interchange and k‐opt,” are specific instances of neighborhood search methods. Note that at each iteration, we move to a better solution or we terminate with the best solution seen so far.
Gravitational Search Algorithm
Published in Nazmul Siddique, Hojjat Adeli, Nature-Inspired Computing, 2017
A combinatorial optimization problem is the problem of finding the best possible grouping, ordering, or assignment of a finite set of objects satisfying certain conditions or constraints. Combinatorial optimization problems are very common in many areas of computer science and other disciplines such as applied mathematics, artificial intelligence, operations research, bioinformatics, electronic commerce, engineering, and industry where an exhaustive search is not feasible. Very often the set of feasible solutions is discrete or can be reduced to be discrete. In all cases, the goal is to find the best possible solution. There are combinatorial optimization problems which are NP-hard and there are no algorithms that can solve them in polynomial time. Such combinatorial optimization problems are very common in engineering and industry, which need novel solutions using new meta-heuristic algorithms. In the following sections, application of the GSA and its variants to some engineering- and industry-type problems is discussed.
Analytics and machine learning in vehicle routing research
Published in International Journal of Production Research, 2023
Ruibin Bai, Xinan Chen, Zhi-Long Chen, Tianxiang Cui, Shuhui Gong, Wentao He, Xiaoping Jiang, Huan Jin, Jiahuan Jin, Graham Kendall, Jiawei Li, Zheng Lu, Jianfeng Ren, Paul Weng, Ning Xue, Huayan Zhang
VRP research is traditionally limited to the Operations Research (OR) community. However, with the advances in machine learning methodologies, researchers in the machine learning community have recently made attempts to tackle combinatorial optimisation problems (including VRPs) solely using machine learning methods (i.e. without explicitly exploiting the structures of the mathematical models). These methods often, despite some progress, suffer from issues such as the lack of generalisation across different scenarios, inefficiency in data use, and the inability to discover insights and interpret solution structures. There seems to be very little interaction between the two communities. Related papers are scattered in journals of both research communities and cross-community paper citations are fewer than you would expect. This leads to the lagged acknowledgement of progress made across research communities. Furthermore, each community uses its own set of terminologies such that similar ideas are defined with different terms. This often causes considerable confusion for researchers and practitioners. We believe that a thorough review of the VRP research that uses tools from these two research communities would be useful to both communities.
Data mining-based algorithm for assortment planning
Published in Journal of Management Analytics, 2020
Praveen Ranjan Srivastava, Satyendra Sharma, Simran Kaur
The knapsack problem is a classic and widely studied computational problem in combinatorial optimization which focuses on optimal assortment of objects (weights) such that the total weight of objects within a pack of specific weight (constraint) is maximized. The applications of this concept are used to solve various optimization problems in many fields. For example, in economics, the knapsack problem is analogous to optimization such as simple consumption model given a budget constraint. Similarly, an assortment problem with space and other constraints can also be mapped to the knapsack problem. Essentially, we maximize some feature by keeping in consideration the constraints. Knapsack produces not only the maximum profit but also selects the items for each cluster which would produce maximum profit for the retailer.
Toolpath planning for multi-gantry additive manufacturing
Published in IISE Transactions, 2021
Hieu Bui, Harry A. Pierson, Sarah Nurre Pinkley, Kelly M. Sullivan
The Traveling Salesman Problem (TSP) is one of the most widely study combinatorial optimization problems. Given a set of cities and the cost of travel between each pair of cities, the TSP tries to find the cheapest route to visit all the cities exactly once and return to the starting point. The routing of the tool can be formulated as the TSP (Castelino et al., 2003; Oysu and Bingul, 2007; Volpato et al., 2014; Lin et al., 2015; Ganganath et al., 2016).