Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 297, Issue 2, Pages 615-629Publisher
ELSEVIER
DOI: 10.1016/j.ejor.2021.05.018
Keywords
Genetic algorithms; Moving-target traveling salesman problem; Dynamic network; Dynamic programming
Funding
- University of Turku Graduate School's MATTI doctoral program
Ask authors/readers for more resources
The article proposes a customized genetic algorithm to find the Pareto frontier for a biobjective integer linear programming model in a dynamic network. By combining genetic algorithm with dynamic programming, the algorithm provides a fast alternative for efficient solutions. Performance evaluation using real data and comparison with ILP solutions demonstrate convergence to the efficient frontier with improved computation speed.
The article presents a proposed customized genetic algorithm (CGA) to find the Pareto frontier for a biobjective integer linear programming (ILP) model of routing in a dynamic network, where the number of nodes and edge weights vary over time. Utilizing a hybrid method, the CGA combines a genetic algorithm with dynamic programming (DP); it is a fast alternative to an ILP solver for finding efficient solutions, particularly for large dimensions. A non-dominated sorting genetic algorithm (NSGA-II) is used as a base multi-objective evolutionary algorithm. Real data are used for target trajectories, from a case study of application of a surveillance boat to measure greenhouse-gas emissions of ships on the Baltic sea. The CGA's performance is evaluated in comparison to ILP solutions in terms of accuracy and computation efficiency. Results over multiple runs indicate convergence to the efficient frontier, with a considerable computation speed-up relative to the ILP solver. The study stays as a model for hybridizing evolutionary optimization and DP methods together in solving complex real-world problems. (c) 2021 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available