Last-mile delivery problems have become a subject of increasing academic study in recent years. This paper examines the operational level Three-Tier Delivery Problem with Public Transportation (3T-DPPT), which concerns the conveyance of customers’ parcels from a warehouse, typically situated outside the city, to the customers in the city center, using public transport vehicles as an intermediate leg. The parcels are conveyed from the depot to public transport stops, then taken into the city center by public transportation vehicles, and finally delivered to the customers by freighters using green and lightweight means (or even walking). In this paper, we introduce a genetic algorithm (GA) to address the resolution of large-scale instances, which exact approaches in practice cannot tackle. We provide a detailed account of its encoding and the distinct genetic operators tailored for it. We undertake a comparative analysis of its performance vis-à-vis that of a compact mixed-integer linear programming formulation on a diverse array of instances of various sizes. The outcomes underscore the efficacy and robustness of the GA approach across different instance sizes, yielding solutions that are near the optimal ones in a relatively short span of time.