Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP
The increasing use of drones to perform various tasks has motivated an exponential growth of research aimed at optimizing the use of these means, benefiting both military and civilian applications, including logistics delivery. In this sense, the combined use of trucks and drones has been explored with great interest by Operations Research. This work presents mathematical formulations in Mixed Integer Linear Programming and proposes a hybrid Genetic Algorithm (HGenFS) for optimizing a variation of the Traveling Salesman Problem (TSP) called Flying Sidekick TSP (FSTSP), in which truck and drone cooperate. The results obtained confirmed that the adopted formulation for the exact solution is suitable for solving problems up to ten customers, and the HGenFS proved to be capable of finding optimal solutions for the FSTSP in a few seconds by incorporating specific heuristics and a local search phase.
Code (0)
등록된 구현이 없습니다.
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
Symbolic Regression using Mixed-Integer Nonlinear Optimization
The Symbolic Regression (SR) problem, where the goal is to find a regression function that does not have a pre-specified form but is any function that can be composed of a list of operators, is a hard problem in machine …
regressionSymbolic RegressionSharp Hybrid Zonotopes: Set Operations and the Reformulation-linearization Technique
Mixed integer set representations, and specifically hybrid zonotopes, have enabled new techniques for reachability and verification of nonlinear and hybrid systems. Mixed-integer sets which have the property that their c…
Fast Non-Parametric Learning to Accelerate Mixed-Integer Programming for Online Hybrid Model Predictive Control
Today's fast linear algebra and numerical optimization tools have pushed the frontier of model predictive control (MPC) forward, to the efficient control of highly nonlinear and hybrid systems. The field of hybrid MPC ha…
Model Predictive ControlParallel Domain-Decomposition Algorithms for Complexity Certification of Branch-and-Bound Algorithms for Mixed-Integer Linear and Quadratic Programming
When implementing model predictive control (MPC) for hybrid systems with a linear or a quadratic performance measure, a mixed-integer linear program (MILP) or a mixed-integer quadratic program (MIQP) needs to be solved, …
Model Predictive ControlLearning the cost-to-go for mixed-integer nonlinear model predictive control
Application of nonlinear model predictive control (NMPC) to problems with hybrid dynamical systems, disjoint constraints, or discrete controls often results in mixed-integer formulations with both continuous and discrete…
Model Predictive ControlPrediction