The fees will result in much more carry-on, but the American carriers have been dealing with this for a few years now and have got a pattern down that AC shouldn't have too much difficulty following -

- Confirmation screen (with pictures) at online check-in explaining what is and isn't allowed as carry on

- Proactive announcements in the gate area indicating that a given flight is full and offering to check rollaboards 'to their final destination' free of charge

- Rollaboard sizers prominently displayed in the gate area

- Gate agents proactively pulling people aside during boarding with noncompliant bags

- Flight attendants proactively reorganizing overhead bins during boarding and making it clear that only ONE item is allowed in the bin

- Onboard: Hustling bags forward to check them (for free) when the bins are all full