This paper presents a novel parcel delivery system consisting of an unmanned aerial vehicle (UAV) and a public train. The train moves along a fixed route following a predefined timetable and carries a set of parcels. The UAV departs from the train, delivers a parcel to a customer, returns to the train, and picks another parcel. The UAV can also travel with the train and replace the battery on the roof of it. Since the train is not controlled by the parcel delivery system, its timetable should be taken into account to efficiently deliver parcels. An optimal control problem is formulated with the objective of minimizing the total delivery time and a suboptimal algorithm is developed, which is computationally efficient. A case study is conducted to evaluate the proposed algorithm and compare it with existing schemes. The proposed approach is more cost efficient than the Truck only scheme and the Truck plus UAV scheme, since there is no cost associated with the truck. Moreover, it improves delivery time and covers a larger area compare to the UAV only delivery scheme.