Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective

Ida Gjergji; Lucas Kletzander; Hendrik Bierlee; Nysret Musliu; Peter J Stuckey

doi:10.1007/978-3-031-95976-9_1

Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective

Ida Gjergji, Lucas Kletzander, Hendrik Bierlee, Nysret Musliu, Peter J Stuckey

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

In this paper we focus on a challenging version of the aircraft maintenance routing problem (AMRP) with a maintenance distribution objective (AMRP-D). For the AMRP-D, the flight legs with predefined start and end times are assigned to aircraft. In addition to the assigned flight legs, each aircraft has to satisfy certain regulations regarding the maintenance services that are mandatory in the scheduling period, while the maintenance should also be distributed evenly. We propose a two stage approach, where first we use a decomposition method that is solved using constraint programming, to cover the flight legs. To optimize the distribution objective, we propose two metaheuristic techniques based on Large Neighborhood Search (LNS) and Simulated Annealing (SA). The LNS method consists of different destroy operators and as repairer we use a constraint programming (CP) solver. The SA approach includes a novel neighborhood to deal with the distribution objective. Our experimental results show that the decomposition method is able to solve more instances than the exact approach, while SA provides better quality solutions for the optimization stage compared to LNS.

Original language	English
Title of host publication	Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II
Editors	Guido Tack
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	1-17
Number of pages	17
ISBN (Electronic)	9783031959769
ISBN (Print)	9783031959752
DOIs	https://doi.org/10.1007/978-3-031-95976-9_1
Publication status	Published - 2025
Event	International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research 2025 - Melbourne, Australia Duration: 10 Nov 2025 → 13 Nov 2025 Conference number: 22nd https://sites.google.com/view/cpaior2025 (Website) https://link.springer.com/book/10.1007/978-3-031-95973-8 (Proceedings - part 1) https://link.springer.com/book/10.1007/978-3-031-95976-9 (Proceedings - Part 2)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	15763
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research 2025
Abbreviated title	CPAIOR 2025
Country/Territory	Australia
City	Melbourne
Period	10/11/25 → 13/11/25
Internet address	https://sites.google.com/view/cpaior2025 (Website) https://link.springer.com/book/10.1007/978-3-031-95973-8 (Proceedings - part 1) https://link.springer.com/book/10.1007/978-3-031-95976-9 (Proceedings - Part 2)

Keywords

Constraint programming
Metaheuristics
Scheduling

Access to Document

10.1007/978-3-031-95976-9_1

Cite this

Gjergji, I., Kletzander, L., Bierlee, H., Musliu, N., & Stuckey, PJ. (2025). Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective. In G. Tack (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II (pp. 1-17). (Lecture Notes in Computer Science; Vol. 15763). Springer. https://doi.org/10.1007/978-3-031-95976-9_1

Gjergji, Ida ; Kletzander, Lucas ; Bierlee, Hendrik et al. / Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective. Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II. editor / Guido Tack. Cham Switzerland : Springer, 2025. pp. 1-17 (Lecture Notes in Computer Science).

@inproceedings{e7cc706c2711487ab7237252ded2b565,

title = "Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective",

abstract = "In this paper we focus on a challenging version of the aircraft maintenance routing problem (AMRP) with a maintenance distribution objective (AMRP-D). For the AMRP-D, the flight legs with predefined start and end times are assigned to aircraft. In addition to the assigned flight legs, each aircraft has to satisfy certain regulations regarding the maintenance services that are mandatory in the scheduling period, while the maintenance should also be distributed evenly. We propose a two stage approach, where first we use a decomposition method that is solved using constraint programming, to cover the flight legs. To optimize the distribution objective, we propose two metaheuristic techniques based on Large Neighborhood Search (LNS) and Simulated Annealing (SA). The LNS method consists of different destroy operators and as repairer we use a constraint programming (CP) solver. The SA approach includes a novel neighborhood to deal with the distribution objective. Our experimental results show that the decomposition method is able to solve more instances than the exact approach, while SA provides better quality solutions for the optimization stage compared to LNS.",

keywords = "Constraint programming, Metaheuristics, Scheduling",

author = "Ida Gjergji and Lucas Kletzander and Hendrik Bierlee and Nysret Musliu and Peter J Stuckey",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research 2025, CPAIOR 2025 ; Conference date: 10-11-2025 Through 13-11-2025",

year = "2025",

doi = "10.1007/978-3-031-95976-9\_1",

language = "English",

isbn = "9783031959752",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--17",

editor = "Guido Tack",

booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II",

address = "Switzerland",

url = "https://sites.google.com/view/cpaior2025, https://link.springer.com/book/10.1007/978-3-031-95973-8, https://link.springer.com/book/10.1007/978-3-031-95976-9",

}

Gjergji, I, Kletzander, L, Bierlee, H, Musliu, N & Stuckey, PJ 2025, Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective. in G Tack (ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II. Lecture Notes in Computer Science, vol. 15763, Springer, Cham Switzerland, pp. 1-17, International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research 2025, Melbourne, Victoria, Australia, 10/11/25. https://doi.org/10.1007/978-3-031-95976-9_1

Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective. / Gjergji, Ida; Kletzander, Lucas; Bierlee, Hendrik et al.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II. ed. / Guido Tack. Cham Switzerland: Springer, 2025. p. 1-17 (Lecture Notes in Computer Science; Vol. 15763).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective

AU - Gjergji, Ida

AU - Kletzander, Lucas

AU - Bierlee, Hendrik

AU - Musliu, Nysret

AU - Stuckey, Peter J

N1 - Conference code: 22nd

PY - 2025

Y1 - 2025

N2 - In this paper we focus on a challenging version of the aircraft maintenance routing problem (AMRP) with a maintenance distribution objective (AMRP-D). For the AMRP-D, the flight legs with predefined start and end times are assigned to aircraft. In addition to the assigned flight legs, each aircraft has to satisfy certain regulations regarding the maintenance services that are mandatory in the scheduling period, while the maintenance should also be distributed evenly. We propose a two stage approach, where first we use a decomposition method that is solved using constraint programming, to cover the flight legs. To optimize the distribution objective, we propose two metaheuristic techniques based on Large Neighborhood Search (LNS) and Simulated Annealing (SA). The LNS method consists of different destroy operators and as repairer we use a constraint programming (CP) solver. The SA approach includes a novel neighborhood to deal with the distribution objective. Our experimental results show that the decomposition method is able to solve more instances than the exact approach, while SA provides better quality solutions for the optimization stage compared to LNS.

AB - In this paper we focus on a challenging version of the aircraft maintenance routing problem (AMRP) with a maintenance distribution objective (AMRP-D). For the AMRP-D, the flight legs with predefined start and end times are assigned to aircraft. In addition to the assigned flight legs, each aircraft has to satisfy certain regulations regarding the maintenance services that are mandatory in the scheduling period, while the maintenance should also be distributed evenly. We propose a two stage approach, where first we use a decomposition method that is solved using constraint programming, to cover the flight legs. To optimize the distribution objective, we propose two metaheuristic techniques based on Large Neighborhood Search (LNS) and Simulated Annealing (SA). The LNS method consists of different destroy operators and as repairer we use a constraint programming (CP) solver. The SA approach includes a novel neighborhood to deal with the distribution objective. Our experimental results show that the decomposition method is able to solve more instances than the exact approach, while SA provides better quality solutions for the optimization stage compared to LNS.

KW - Constraint programming

KW - Metaheuristics

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=105010228793&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-95976-9_1

DO - 10.1007/978-3-031-95976-9_1

M3 - Conference Paper

AN - SCOPUS:105010228793

SN - 9783031959752

T3 - Lecture Notes in Computer Science

SP - 1

EP - 17

BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II

A2 - Tack, Guido

PB - Springer

CY - Cham Switzerland

T2 - International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research 2025

Y2 - 10 November 2025 through 13 November 2025

ER -

Gjergji I, Kletzander L, Bierlee H, Musliu N, Stuckey PJ. Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective. In Tack G, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 22nd International Conference, CPAIOR 2025 Melbourne, VIC, Australia, November 10–13, 2025 Proceedings, Part II. Cham Switzerland: Springer. 2025. p. 1-17. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-95976-9_1

Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)

Cite this

Combining Constraint Programming and Metaheuristics for Aircraft Maintenance Routing with a Distribution Objective

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Projects

ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)

Cite this