assignment problem variable

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

• Google OR-Tools
• Español – América Latina
• Português – Brasil
• Tiếng Việt

Solving an Assignment Problem

This section presents an example that shows how to solve an assignment problem using both the MIP solver and the CP-SAT solver.

In the example there are five workers (numbered 0-4) and four tasks (numbered 0-3). Note that there is one more worker than in the example in the Overview .

The costs of assigning workers to tasks are shown in the following table.

The problem is to assign each worker to at most one task, with no two workers performing the same task, while minimizing the total cost. Since there are more workers than tasks, one worker will not be assigned a task.

MIP solution

The following sections describe how to solve the problem using the MPSolver wrapper .

Import the libraries

The following code imports the required libraries.

Create the data

The following code creates the data for the problem.

The costs array corresponds to the table of costs for assigning workers to tasks, shown above.

Declare the MIP solver

The following code declares the MIP solver.

Create the variables

The following code creates binary integer variables for the problem.

Create the constraints

Create the objective function.

The following code creates the objective function for the problem.

The value of the objective function is the total cost over all variables that are assigned the value 1 by the solver.

Invoke the solver

The following code invokes the solver.

Print the solution

The following code prints the solution to the problem.

Here is the output of the program.

Complete programs

Here are the complete programs for the MIP solution.

CP SAT solution

The following sections describe how to solve the problem using the CP-SAT solver.

Declare the model

The following code declares the CP-SAT model.

The following code sets up the data for the problem.

The following code creates the constraints for the problem.

Here are the complete programs for the CP-SAT solution.

Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License , and code samples are licensed under the Apache 2.0 License . For details, see the Google Developers Site Policies . Java is a registered trademark of Oracle and/or its affiliates.

Last updated 2023-01-02 UTC.

How to Solve the Assignment Problem: A Complete Guide

Table of Contents

Assignment problem is a special type of linear programming problem that deals with assigning a number of resources to an equal number of tasks in the most efficient way. The goal is to minimize the total cost of assignments while ensuring that each task is assigned to only one resource and each resource is assigned to only one task. In this blog, we will discuss the solution of the assignment problem using the Hungarian method, which is a popular algorithm for solving the problem.

Understanding the Assignment Problem

Before we dive into the solution, it is important to understand the problem itself. In the assignment problem, we have a matrix of costs, where each row represents a resource and each column represents a task. The objective is to assign each resource to a task in such a way that the total cost of assignments is minimized. However, there are certain constraints that need to be satisfied – each resource can be assigned to only one task and each task can be assigned to only one resource.

Solving the Assignment Problem

There are various methods for solving the assignment problem, including the Hungarian method, the brute force method, and the auction algorithm. Here, we will focus on the steps involved in solving the assignment problem using the Hungarian method, which is the most commonly used and efficient method.

Step 1: Set up the cost matrix

The first step in solving the assignment problem is to set up the cost matrix, which represents the cost of assigning a task to an agent. The matrix should be square and have the same number of rows and columns as the number of tasks and agents, respectively.

Step 2: Subtract the smallest element from each row and column

To simplify the calculations, we need to reduce the size of the cost matrix by subtracting the smallest element from each row and column. This step is called matrix reduction.

Step 3: Cover all zeros with the minimum number of lines

The next step is to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This step is called matrix covering.

Step 4: Test for optimality and adjust the matrix

To test for optimality, we need to calculate the minimum number of lines required to cover all zeros in the matrix. If the number of lines equals the number of rows or columns, the solution is optimal. If not, we need to adjust the matrix and repeat steps 3 and 4 until we get an optimal solution.

Step 5: Assign the tasks to the agents

The final step is to assign the tasks to the agents based on the optimal solution obtained in step 4. This will give us the most cost-effective or profit-maximizing assignment.

Solution of the Assignment Problem using the Hungarian Method

The Hungarian method is an algorithm that uses a step-by-step approach to find the optimal assignment. The algorithm consists of the following steps:

• Subtract the smallest entry in each row from all the entries of the row.
• Subtract the smallest entry in each column from all the entries of the column.
• Draw the minimum number of lines to cover all zeros in the matrix. If the number of lines drawn is equal to the number of rows, we have an optimal solution. If not, go to step 4.
• Determine the smallest entry not covered by any line. Subtract it from all uncovered entries and add it to all entries covered by two lines. Go to step 3.

The above steps are repeated until an optimal solution is obtained. The optimal solution will have all zeros covered by the minimum number of lines. The assignments can be made by selecting the rows and columns with a single zero in the final matrix.

Applications of the Assignment Problem

The assignment problem has various applications in different fields, including computer science, economics, logistics, and management. In this section, we will provide some examples of how the assignment problem is used in real-life situations.

Applications in Computer Science

The assignment problem can be used in computer science to allocate resources to different tasks, such as allocating memory to processes or assigning threads to processors.

Applications in Economics

The assignment problem can be used in economics to allocate resources to different agents, such as allocating workers to jobs or assigning projects to contractors.

Applications in Logistics

The assignment problem can be used in logistics to allocate resources to different activities, such as allocating vehicles to routes or assigning warehouses to customers.

Applications in Management

The assignment problem can be used in management to allocate resources to different projects, such as allocating employees to tasks or assigning budgets to departments.

Let’s consider the following scenario: a manager needs to assign three employees to three different tasks. Each employee has different skills, and each task requires specific skills. The manager wants to minimize the total time it takes to complete all the tasks. The skills and the time required for each task are given in the table below:

The assignment problem is to determine which employee should be assigned to which task to minimize the total time required. To solve this problem, we can use the Hungarian method, which we discussed in the previous blog.

Using the Hungarian method, we first subtract the smallest entry in each row from all the entries of the row:

Next, we subtract the smallest entry in each column from all the entries of the column:

We draw the minimum number of lines to cover all the zeros in the matrix, which in this case is three:

Since the number of lines is equal to the number of rows, we have an optimal solution. The assignments can be made by selecting the rows and columns with a single zero in the final matrix. In this case, the optimal assignments are:

• Emp 1 to Task 3
• Emp 2 to Task 2
• Emp 3 to Task 1

This assignment results in a total time of 9 units.

I hope this example helps you better understand the assignment problem and how to solve it using the Hungarian method.

Solving the assignment problem may seem daunting, but with the right approach, it can be a straightforward process. By following the steps outlined in this guide, you can confidently tackle any assignment problem that comes your way.

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you! 😔

Let us improve this post!

Tell us how we can improve this post?

Operations Research

1 Operations Research-An Overview

• History of O.R.
• Approach, Techniques and Tools
• Phases and Processes of O.R. Study
• Typical Applications of O.R
• Limitations of Operations Research
• Models in Operations Research
• O.R. in real world

2 Linear Programming: Formulation and Graphical Method

• General formulation of Linear Programming Problem
• Optimisation Models
• Basics of Graphic Method
• Important steps to draw graph
• Multiple, Unbounded Solution and Infeasible Problems
• Solving Linear Programming Graphically Using Computer
• Application of Linear Programming in Business and Industry

3 Linear Programming-Simplex Method

• Principle of Simplex Method
• Computational aspect of Simplex Method
• Simplex Method with several Decision Variables
• Two Phase and M-method
• Multiple Solution, Unbounded Solution and Infeasible Problem
• Sensitivity Analysis
• Dual Linear Programming Problem

4 Transportation Problem

• Basic Feasible Solution of a Transportation Problem
• Modified Distribution Method
• Stepping Stone Method
• Unbalanced Transportation Problem
• Degenerate Transportation Problem
• Transhipment Problem
• Maximisation in a Transportation Problem

5 Assignment Problem

• Solution of the Assignment Problem
• Unbalanced Assignment Problem
• Problem with some Infeasible Assignments
• Maximisation in an Assignment Problem
• Crew Assignment Problem

6 Application of Excel Solver to Solve LPP

• Building Excel model for solving LP: An Illustrative Example

7 Goal Programming

• Concepts of goal programming
• Goal programming model formulation
• Graphical method of goal programming
• The simplex method of goal programming
• Using Excel Solver to Solve Goal Programming Models
• Application areas of goal programming

8 Integer Programming

• Some Integer Programming Formulation Techniques
• Binary Representation of General Integer Variables
• Unimodularity
• Cutting Plane Method
• Branch and Bound Method
• Solver Solution

9 Dynamic Programming

• Dynamic Programming Methodology: An Example
• Definitions and Notations
• Dynamic Programming Applications

10 Non-Linear Programming

• Solution of a Non-linear Programming Problem
• Convex and Concave Functions
• Kuhn-Tucker Conditions for Constrained Optimisation
• Quadratic Programming
• Separable Programming
• NLP Models with Solver

11 Introduction to game theory and its Applications

• Important terms in Game Theory
• Saddle points
• Mixed strategies: Games without saddle points
• 2 x n games
• Exploiting an opponent’s mistakes

12 Monte Carlo Simulation

• Reasons for using simulation
• Monte Carlo simulation
• Limitations of simulation
• Steps in the simulation process
• Some practical applications of simulation
• Two typical examples of hand-computed simulation
• Computer simulation

13 Queueing Models

• Characteristics of a queueing model
• Notations and Symbols
• Statistical methods in queueing
• The M/M/I System
• The M/M/C System
• The M/Ek/I System
• Decision problems in queueing

• MapReduce Algorithm
• Linear Programming using Pyomo
• Networking and Professional Development for Machine Learning Careers in the USA
• Predicting Employee Churn in Python
• Airflow Operators

Solving Assignment Problem using Linear Programming in Python

Learn how to use Python PuLP to solve Assignment problems using Linear Programming.

In earlier articles, we have seen various applications of Linear programming such as transportation, transshipment problem, Cargo Loading problem, and shift-scheduling problem. Now In this tutorial, we will focus on another model that comes under the class of linear programming model known as the Assignment problem. Its objective function is similar to transportation problems. Here we minimize the objective function time or cost of manufacturing the products by allocating one job to one machine.

If we want to solve the maximization problem assignment problem then we subtract all the elements of the matrix from the highest element in the matrix or multiply the entire matrix by –1 and continue with the procedure. For solving the assignment problem, we use the Assignment technique or Hungarian method, or Flood’s technique.

The transportation problem is a special case of the linear programming model and the assignment problem is a special case of transportation problem, therefore it is also a special case of the linear programming problem.

In this tutorial, we are going to cover the following topics:

Assignment Problem

A problem that requires pairing two sets of items given a set of paired costs or profit in such a way that the total cost of the pairings is minimized or maximized. The assignment problem is a special case of linear programming.

For example, an operation manager needs to assign four jobs to four machines. The project manager needs to assign four projects to four staff members. Similarly, the marketing manager needs to assign the 4 salespersons to 4 territories. The manager’s goal is to minimize the total time or cost.

Problem Formulation

A manager has prepared a table that shows the cost of performing each of four jobs by each of four employees. The manager has stated his goal is to develop a set of job assignments that will minimize the total cost of getting all 4 jobs.  

Initialize LP Model

In this step, we will import all the classes and functions of pulp module and create a Minimization LP problem using LpProblem class.

Define Decision Variable

In this step, we will define the decision variables. In our problem, we have two variable lists: workers and jobs. Let’s create them using  LpVariable.dicts()  class.  LpVariable.dicts()  used with Python’s list comprehension.  LpVariable.dicts()  will take the following four values:

• First, prefix name of what this variable represents.
• Second is the list of all the variables.
• Third is the lower bound on this variable.
• Fourth variable is the upper bound.
• Fourth is essentially the type of data (discrete or continuous). The options for the fourth parameter are  LpContinuous  or  LpInteger .

Let’s first create a list route for the route between warehouse and project site and create the decision variables using LpVariable.dicts() the method.

Define Objective Function

In this step, we will define the minimum objective function by adding it to the LpProblem  object. lpSum(vector)is used here to define multiple linear expressions. It also used list comprehension to add multiple variables.

Define the Constraints

Here, we are adding two types of constraints: Each job can be assigned to only one employee constraint and Each employee can be assigned to only one job. We have added the 2 constraints defined in the problem by adding them to the LpProblem  object.

Solve Model

In this step, we will solve the LP problem by calling solve() method. We can print the final value by using the following for loop.

From the above results, we can infer that Worker-1 will be assigned to Job-1, Worker-2 will be assigned to job-3, Worker-3 will be assigned to Job-2, and Worker-4 will assign with job-4.

In this article, we have learned about Assignment problems, Problem Formulation, and implementation using the python PuLp library. We have solved the Assignment problem using a Linear programming problem in Python. Of course, this is just a simple case study, we can add more constraints to it and make it more complicated. You can also run other case studies on Cargo Loading problems , Staff scheduling problems . In upcoming articles, we will write more on different optimization problems such as transshipment problem, balanced diet problem. You can revise the basics of mathematical concepts in  this article  and learn about Linear Programming  in this article .

• Solving Blending Problem in Python using Gurobi
• Transshipment Problem in Python Using PuLP

You May Also Like

Solving Transportation Problem using Linear Programming in Python

Decision Tree Classification in Python

Keras Tutorial for Beginners

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 1 (Introduction)

• Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)
• Introduction to Exact Cover Problem and Algorithm X
• Greedy Approximate Algorithm for Set Cover Problem
• Job Assignment Problem using Branch And Bound
• Implementation of Exhaustive Search Algorithm for Set Packing
• Channel Assignment Problem
• Chocolate Distribution Problem | Set 2
• Transportation Problem | Set 1 (Introduction)
• OLA Interview Experience | Set 11 ( For Internship)
• Top 20 Greedy Algorithms Interview Questions
• Job Sequencing Problem - Loss Minimization
• Prim's Algorithm (Simple Implementation for Adjacency Matrix Representation)
• Data Structures and Algorithms | Set 21
• Adobe Interview Experience | Set 55 (On-Campus Full Time for MTS profile)
• Amazon Interview Experience | Set 211 (On-Campus for Internship)
• OYO Rooms Interview Experience | Set 3 (For SDE-II, Gurgaon)
• C# Program for Dijkstra's shortest path algorithm | Greedy Algo-7
• Algorithms | Dynamic Programming | Question 7
• Amazon Interview | Set 46 (On-campus for Internship)
• Merge Sort - Data Structure and Algorithms Tutorials
• Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, ...
• QuickSort - Data Structure and Algorithm Tutorials
• Bubble Sort - Data Structure and Algorithm Tutorials
• Tree Traversal Techniques - Data Structure and Algorithm Tutorials
• Binary Search - Data Structure and Algorithm Tutorials
• Insertion Sort - Data Structure and Algorithm Tutorials
• Selection Sort – Data Structure and Algorithm Tutorials
• Understanding the basics of Linked List
• Breadth First Search or BFS for a Graph

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Do the same (as step 1) for all columns.
• Cover all zeros in the matrix using minimum number of horizontal and vertical lines.
• Test for Optimality: If the minimum number of covering lines is n, an optimal assignment is possible and we are finished. Else if lines are lesser than n, we haven’t found the optimal assignment, and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Try it before moving to see the solution

Explanation for above simple example:

  An example that doesn’t lead to optimal value in first attempt: In the above example, the first check for optimality did give us solution. What if we the number covering lines is less than n.

Time complexity : O(n^3), where n is the number of workers and jobs. This is because the algorithm implements the Hungarian algorithm, which is known to have a time complexity of O(n^3).

Space complexity :   O(n^2), where n is the number of workers and jobs. This is because the algorithm uses a 2D cost matrix of size n x n to store the costs of assigning each worker to a job, and additional arrays of size n to store the labels, matches, and auxiliary information needed for the algorithm.

In the next post, we will be discussing implementation of the above algorithm. The implementation requires more steps as we need to find minimum number of lines to cover all 0’s using a program. References: http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf https://www.youtube.com/watch?v=dQDZNHwuuOY

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Python Numerical Methods

This notebook contains an excerpt from the Python Programming and Numerical Methods - A Guide for Engineers and Scientists , the content is also available at Berkeley Python Numerical Methods .

The copyright of the book belongs to Elsevier. We also have this interactive book online for a better learning experience. The code is released under the MIT license . If you find this content useful, please consider supporting the work on Elsevier or Amazon !

< 2.0 Variables and Basic Data Structures | Contents | 2.2 Data Structure - Strings >

Variables and Assignment ¶

When programming, it is useful to be able to store information in variables. A variable is a string of characters and numbers associated with a piece of information. The assignment operator , denoted by the “=” symbol, is the operator that is used to assign values to variables in Python. The line x=1 takes the known value, 1, and assigns that value to the variable with name “x”. After executing this line, this number will be stored into this variable. Until the value is changed or the variable deleted, the character x behaves like the value 1.

TRY IT! Assign the value 2 to the variable y. Multiply y by 3 to show that it behaves like the value 2.

A variable is more like a container to store the data in the computer’s memory, the name of the variable tells the computer where to find this value in the memory. For now, it is sufficient to know that the notebook has its own memory space to store all the variables in the notebook. As a result of the previous example, you will see the variable “x” and “y” in the memory. You can view a list of all the variables in the notebook using the magic command %whos .

TRY IT! List all the variables in this notebook

Note that the equal sign in programming is not the same as a truth statement in mathematics. In math, the statement x = 2 declares the universal truth within the given framework, x is 2 . In programming, the statement x=2 means a known value is being associated with a variable name, store 2 in x. Although it is perfectly valid to say 1 = x in mathematics, assignments in Python always go left : meaning the value to the right of the equal sign is assigned to the variable on the left of the equal sign. Therefore, 1=x will generate an error in Python. The assignment operator is always last in the order of operations relative to mathematical, logical, and comparison operators.

TRY IT! The mathematical statement x=x+1 has no solution for any value of x . In programming, if we initialize the value of x to be 1, then the statement makes perfect sense. It means, “Add x and 1, which is 2, then assign that value to the variable x”. Note that this operation overwrites the previous value stored in x .

There are some restrictions on the names variables can take. Variables can only contain alphanumeric characters (letters and numbers) as well as underscores. However, the first character of a variable name must be a letter or underscores. Spaces within a variable name are not permitted, and the variable names are case-sensitive (e.g., x and X will be considered different variables).

TIP! Unlike in pure mathematics, variables in programming almost always represent something tangible. It may be the distance between two points in space or the number of rabbits in a population. Therefore, as your code becomes increasingly complicated, it is very important that your variables carry a name that can easily be associated with what they represent. For example, the distance between two points in space is better represented by the variable dist than x , and the number of rabbits in a population is better represented by nRabbits than y .

Note that when a variable is assigned, it has no memory of how it was assigned. That is, if the value of a variable, y , is constructed from other variables, like x , reassigning the value of x will not change the value of y .

EXAMPLE: What value will y have after the following lines of code are executed?

WARNING! You can overwrite variables or functions that have been stored in Python. For example, the command help = 2 will store the value 2 in the variable with name help . After this assignment help will behave like the value 2 instead of the function help . Therefore, you should always be careful not to give your variables the same name as built-in functions or values.

TIP! Now that you know how to assign variables, it is important that you learn to never leave unassigned commands. An unassigned command is an operation that has a result, but that result is not assigned to a variable. For example, you should never use 2+2 . You should instead assign it to some variable x=2+2 . This allows you to “hold on” to the results of previous commands and will make your interaction with Python must less confusing.

You can clear a variable from the notebook using the del function. Typing del x will clear the variable x from the workspace. If you want to remove all the variables in the notebook, you can use the magic command %reset .

In mathematics, variables are usually associated with unknown numbers; in programming, variables are associated with a value of a certain type. There are many data types that can be assigned to variables. A data type is a classification of the type of information that is being stored in a variable. The basic data types that you will utilize throughout this book are boolean, int, float, string, list, tuple, dictionary, set. A formal description of these data types is given in the following sections.

Integrated airline fleet introduction and assignment under a daily route-based network

• Original Research
• Published: 06 May 2024

Cite this article

• Zhou Jing   ORCID: orcid.org/0000-0001-9986-0390 1 &
• Liang Zhe 1  

This study investigates an integrated airline fleet introduction and assignment problem under a daily route-based network. It is critical for an airline to integrate advanced digital technology with the methodology of operational research to achieve smart operations. An integer programming model is proposed for this problem. Based on the model, a hybrid algorithm combining a multi-encoding variable neighborhood search (VNS) and Branch-and-Bound (B&B) method is proposed. Firstly, the multi-encoding VNS solves fleet introduction and determines fleet numbers. A self-adaptive multi-layer encoding process with nine neighborhood structures is designed in the VNS process to improve the local search efficiency. Secondly, given the fleet numbers, the improved B&B method driven by profit matrix is designed to solve fleet assignment. There are three modified strategies in the B&B method containing cyclic best-first search, wide branching, and upper bound pruning. Finally, computational experiments are conducted to test algorithm performance. The proposed algorithm is compared with basic VNS, differential evolution, and genetic algorithm on objective value, running speed, and stability. The experiments show that the proposed model and algorithm offer a smart methodology for airline integrated problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Abara, J. (1989). Applying integer linear programming to the fleet assignment problem. Interfaces, 19 (4), 20–28.

Article   Google Scholar  

Ahuja, K., Goodstein, J., Mukherjee, A., Orlin, B., & Sharma, D. (2007). A very large-scale neighborhood search algorithm for the combined through-fleet-assignment model. INFORMS Journal on Computing, 19 (3), 416–428.

American Airlines. (2019). Hello, neo: American Airlines welcomes its newest aircraft to the fleet . [online] Available at: https://news.aa.com/news/news-details/2019/Hello-neo-American-Airlines-Welcomes-Its-Newest-Aircraft-to-theFleet/default.aspx . Accessed 22 January 2024.

Al-Thani, N., Ahmed, M., & Haouari, M. (2016). A model and optimization-based heuristic for the operational aircraft maintenance routing problem. Transportation Research Part C: Emerging Technologies, 72 , 29–44.

Barnhart, C., Farahat, A., & Lohatepanont, M. (2009). Airline fleet assignment with enhanced revenue modeling. Operations Research, 57 (1), 231–244.

Barnhart, C., Kniker, T., & Lohatepanont, M. (2002). Itinerary-based airline fleet assignment. Transportation Science, 36 (2), 199–217.

Bazargan, M., & Hartman, J. (2012). Aircraft replacement strategy: Model and analysis. Journal of Air Transport Management, 25 , 26–29.

Bélanger, N., Desaulniers, G., Soumis, F., Desrosiers, J., & Lavigne, J. (2006). Weekly airline fleet assignment with homogeneity. Transportation Research Part B: Methodological, 40 (4), 306–318.

Birolini, S., Antunes, A., Cattaneo, M., Malighettia, P., & Paleari, S. (2021a). Integrated flight scheduling and fleet assignment with improved supply-demand interactions. Transportation Research Part B: Methodological, 149 , 162–180.

Birolini, S., Jacquillat, A., Cattaneo, M., & Antunes, A. (2021b). Airline network planning: Mixed-integer non-convex optimization with demand-supply interactions. Transportation Research Part B: Methodological, 154 , 100–124.

China Eastern Airlines. (2024). C919 flies the Shanghai Hongqiao-Beijing Daxing route for the first time . [online] Available at: https://www.ceair.com/global/static/Announcement/AnnouncementMessage/chinaeasternnewstest/202401/t20240109_25082.html . Accessed 22 January 2024.

Civil Aviation Administration of China. (2023c). Statistics of main production indicators of CAAC in November 2023 . [online] Available at: http://www.caac.gov.cn/XXGK/XXGK/TJSJ/202302/P020230220411670766655.pdf . Accessed 20 January 2024.

Civil Aviation Administration of China. (2023b). List of Transportation Airlines . [online] Available at: http://www.caac.gov.cn/GYMH/MHGK/HKGS/index.html . Accessed 20 January 2024.

Civil Aviation Administration of China. (2023a). Statistical Bulletin on the Development of Civil Aviation Industry in 2022 . [online] Available at: http://www.caac.gov.cn/XXGK/XXGK/TJSJ/202209/P020220920312815593554.pdf . Accessed 20 January 2024.

Cui, R., Dong, X., & Lin, T. (2019). Models for aircraft maintenance routing problem with consideration of remaining time and robustness. Computers & Industrial Engineering , 137 , 106045

Eltoukhy, A. E. E., Chan, F. T. S., & Chung, S. H. (2017). Airline schedule planning: A review and future directions. Industrial Management & Data Systems, 117 (6), 1201–1243. https://doi.org/10.1108/imds-09-2016-0358

Erick, S. (2022c). Average New Aircraft Lease Rates Worldwide in 2021, by Aircraft Model . [online] Available at: https://www.statista.com/statistics/1258900/aircraft-lease-rates-aircraft-model . Accessed 9 October 2022.

Erick S. (2022b). Size of aircraft fleets by region worldwide in 2019 and 2040 . [online] Available at: https://www.statista.com/statistics/262971/aircraft-fleets-by-region-worldwide/ . Accessed 4 August 2022.

Erick, S. (2022a). Average Prices for Boeing Aircraft as of March 2022, by Type . [online] Available at: https://www.statista.com/statistics/273941/prices-of-boeing-aircraft-by-type . Accessed 9 October 2022.

Faust, O., Go̎nsch, J., & Klein, R. (2017). Demand-oriented integrated scheduling for point-to-point airlines. Transportation Science, 51 (1), 196–213.

Gao, C., Johnson, E., & Smith, B. (2009). Integrated airline fleet and crew robust planning. Transportation Science, 43 (1), 2–16.

Guzhva, V., Raghavan, S., & D’Agostino, D. (2018). Aircraft Leasing and Financing (1st ed., pp. 264–287). Elsevier.

Google Scholar  

Hane, C., Barnhart, C., Johnson, E., Marsten, R., Nemhauser, G., & Sigismondi, G. (1995). The fleet assignment problem: Solving a large-scale integer program. Mathematical Programming, 70 (1–3), 211–232.

Hsu, C., Li, H., Liu, S., & Chao, C. (2011). Aircraft replacement scheduling: A dynamic programming approach. Transportation Research Part E: Logistics and Transportation Review, 47 (1), 41–60.

Islam, A., & Lownes, N. (2019). When to go electric? A parallel bus fleet replacement study. Transportation Research Part D: Transport and Environment, 72 , 299–311.

Kamandanipour, K., Haji Yakhchali, S., & Tavakkoli-Moghaddam, R. (2023). Dynamic revenue management in a passenger rail network under price and fleet management decisions. Annals of Operations Research . https://doi.org/10.1007/s10479-023-05296-4

Kenan, N., Jebali, A., & Diabat, A. (2018). An integrated flight scheduling and fleet assignment problem under uncertainty. Computers and Operations Research, 100 , 333–342.

Kusoncum, C., Sethanan, K., Hartl, R., & Jamrus, T. (2022). Modified differential evolution and heuristic algorithms for dump tippler machine allocation in a typical sugar mill in Thailand. Operational Research, 22 , 5863–5895.

Liang, Z., & Chaovalitwongse, W. (2013). A network-based model for the integrated weekly aircraft maintenance routing and fleet assignment problem. Transportation Science, 47 (4), 493–507.

Mladenovic, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24 (11), 1097–1100.

Morrison, D., Jacobson, S., Sauppe, J., & Sewell, E. (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19 , 79–102.

Oum, T., Zhang, A., & Zhang, Y. (2000). Optimal demand for operating lease of aircraft. Transportation Research Part B: Methodological, 34 (1), 17–29.

Pantuso, G., Fagerholt, K., & Wallace, S. (2015). Solving hierarchical stochastic programs: Application to the maritime fleet renewal problem. INFORMS Journal on Computing, 27 (1), 89–102.

Pantuso, G., Fagerholt, K., & Wallace, S. (2016). Uncertainty in fleet renewal: A case from maritime transportation. Transportation Science, 50 (2), 390–407.

Parragh, S., & Schmid, V. (2013). Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research, 40 (1), 490–497.

Porumbel, D., Goncalves, G., Allaoui, H., & Hsu, T. (2017). Iterated local search and column generation to solve arc-routing as a permutation set-covering problem. European Journal of Operational Research, 256 (2), 349–367.

Rexing, B., Barnhart, C., Kniker, T., Jarrah, A., & Krishnamurthy, N. (2000). Airline fleet assignment with time windows. Transportation Science, 34 (1), 1–20.

Rushmeier, R. A., & Kontogiorgis, S. A. (1997). Advances in the optimization of airline fleet assignment. Transportation Science, 31 (2), 159–169.

Shao, S., Sherali, H., & Haouari, M. (2017). A novel model and decomposition approach for the integrated airline fleet assignment, aircraft routing, and crew pairing problem. Transportation Science, 51 (1), 233–249.

Sherali, H., Bae, K., & Haouari, M. (2013). A benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture. Annals of Operations Research, 210 , 213–244.

Sinclair, K., Cordeau, J., & Laporte, G. (2014). Improvements to a large neighborhood search heuristic for an integrated aircraft and passenger recovery problem. European Journal of Operational Research, 233 (1), 234–245.

Smith, C., & Johnson, L. (2006). Robust airline fleet assignment: Imposing station purity using station decomposition. Transportation Science, 40 (4), 497–516.

Statista Research Department. 2022. Boeing aircraft prices 2021 by type . [online] Available at: https://www.statista.com/statistics/273941/prices-of-boeing-aircraft-by-type/ . Accessed 4 August 2022.

Swan, W., & Adler, N. (2006). Aircraft trip cost parameters: A function of stage length and seat capacity. Transportation Research Part E: Logistics and Transportation Review, 42 (2), 105–115.

Tang, L., D’Ariano, A., Xu, X., Li, Y., Ding, X., & Samà, M. (2021). Scheduling local and express trains in suburban rail transit lines: Mixed-integer nonlinear programming and adaptive genetic algorithm. Computers & Operations Research, 135 , 105436.

Turan, H., Jalalvand, F., Elsawah, S., & Ryan, M. (2022). A joint problem of strategic workforce planning and fleet renewal: With an application in defense. European Journal of Operational Research, 296 (2), 615–634.

Wang, X., Fagerholt, K., & Wallace, S. W. (2018). Planning for charters: A stochastic maritime fleet composition and deployment problem. Omega, 79 , 54–66.

Xu, Y., Wandelt, S., & Sun, X. (2021). Airline integrated robust scheduling with a variable neighborhood search based heuristic. Transportation Research Part B: Methodological, 149 , 181–203.

Zhou, L., Liang, Z., Chou, C.-A., & Chaovalitwongse, W. A. (2020). Airline planning and scheduling: Models and solution methodologies. Frontiers of Engineering Management, 7 (1), 1–26. https://doi.org/10.1007/s42524-020-0093-5

Download references

Acknowledgements

This study is supported by National Natural Science Foundation of China under Grant No. 71825001 and 72231006.

Author information

Authors and affiliations.

School of Economics and Management, Tongji University, Shanghai, China

Zhou Jing & Liang Zhe

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Liang Zhe .

Ethics declarations

Conflict of interest.

The authors have no competing interests to declare that are relevant to the content of this article.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Jing, Z., Zhe, L. Integrated airline fleet introduction and assignment under a daily route-based network. Ann Oper Res (2024). https://doi.org/10.1007/s10479-024-05994-7

Download citation

Received : 23 July 2023

Accepted : 08 April 2024

Published : 06 May 2024

DOI : https://doi.org/10.1007/s10479-024-05994-7

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Fleet introduction
• Fleet assignment
• Daily route-based network
• Variable neighborhood search
• Branch-and-bound
• Find a journal
• Publish with us
• Track your research