1. A customized genetic algorithm for bi-objective routing in a dynamic network
- Author
-
Alaleh Maskooki, Kalyanmoy Deb, Markku Kallio, University of Turku, Michigan State University, Department of Information and Service Management, Aalto-yliopisto, and Aalto University
- Subjects
050210 logistics & transportation ,Mathematical optimization ,Dynamic network ,021103 operations research ,Information Systems and Management ,Dynamic network analysis ,General Computer Science ,Computer science ,05 social sciences ,0211 other engineering and technologies ,Evolutionary algorithm ,Moving-target traveling salesman problem ,02 engineering and technology ,Genetic algorithms ,Management Science and Operations Research ,Solver ,Dynamic programming ,Industrial and Manufacturing Engineering ,Modeling and Simulation ,0502 economics and business ,Genetic algorithm ,Convergence (routing) ,Routing (electronic design automation) ,Integer programming - Abstract
The article presents a proposed customized genetic algorithm (CGA) to find the Pareto frontier for a bi-objective 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.
- Published
- 2022