Traditionally, vessel air emissions are monitored onboard vessels or at fixed points at sea. These methods are not cost-effective for implementing emission control laws that address air pollution monitoring of vessels travelling over a large body of water. Unmanned aerial vehicles (UAVs) equipped with pollution monitoring sensors are becoming a research focus. However, due to battery capacity constraints, the monitoring scope of UAVs is still not optimal. Thus, using a ship (such as a patrol ship) as a UAV mobile supply base can overcome battery limitations and increase monitoring coverage. This paper investigates the joint routing and scheduling problem of ship-deployed multiple UAVs (SDMUs) for the monitoring of pollution from vessels. The artificial bee colony (ABC) algorithm based on simulated annealing is employed to minimize the total monitoring time. The model and solution algorithm are verified by real-time dynamic vessel data from Tianjin Port.