The　Aircraft　Sequencing　Problem　(ASP)　is　a　problem　that　seeks　to　minimize　adverse　impacts　such　as　flight　delays　by　adjusting　flight　sequencing　schemes.　With　the　increase　in　aviation　demand,　ASP　has　been　garnered　more　attention　in　recent　years.　However,　existing　ASPs　typically　assume　that　the　relationships　between　runways　are　either　entirely　independent　or　entirely　interdependent,　without　considering　the　complex　scenarios　where　runways　have　both　dependent　and　independent　relationships.　Moreover,　existing　ASP　research　focusing　on　multi-objective　aspects　is　relatively　scarce,　while　it　is　essential　to　consider　multifaceted　needs　in　reality.　Therefore,　we　have　established　a　multi-objective　mathematical　model　for　the　Aircraft　Sequencing　Problem　with　Complex　Interdependent　Runways　(ASP-CIR),　aiming　to　minimize　the　total　delays　and　makespan.　Different　from　the　common　lack　of　problem-specific　structural　design　in　existing　ASP　algorithms,　or　the　need　to　improve　structural　strategies,　we　propose　an　Improved　Multi-Objective　Restart　Variable　Neighborhood　Search　(IMORVNS)　algorithm　based　on　the　characteristic　of　the　studied　ASP-CIR.　In　the　IMORVNS,　we　have　designed　several　problem-specific　structures　guided　by　constraints,　such　as　initialization　and　neighborhood　search.　We　tested　our　new　method　on　30　different　problem　instances　of　three　sizes　and　found　it　worked　better　than　other　recent　algorithms.　Moreover,　a　sensitivity　analysis　on　the　scenario　featuring　both　interdependent　and　independent　runway　relationships　was　conducted,　reaffirming　the　importance　of　considering　the　ASP-CIR　scenario.　©　2025　Elsevier　Ltd