A customized genetic algorithm for bi-objective routing in a dynamic network

Alaleh Maskooki, Kalyanmoy Deb and Markku Kallio

European Journal of Operational Research, 2022, vol. 297, issue 2, 615-629

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.

Keywords: Genetic algorithms; Moving-target traveling salesman problem; Dynamic network; Dynamic programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172100432X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:297:y:2022:i:2:p:615-629

DOI: 10.1016/j.ejor.2021.05.018

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().