In Japan, truck transport handles approximately 90% of all freight logistics. However, a legal revision in 2024 introduced a cap of 960 h per year on truck drivers’ overtime work. At the same time, the demand for freight transportation continues to grow, creating an urgent need to further improve the efficiency of delivery operations. This study focuses on optimizing last-mile delivery, specifically by minimizing the total delivery time, which consists of two components: the travel time of the truck and the unloading time at each customer location. To reduce travel time, it is generally effective to maximize loading efficiency—that is, to load as many packages as possible on a single truck. Doing so allows the truck to visit more customers in a single trip and reduces the total distance traveled. However, increasing the loading density can lead to longer unloading times, as packages positioned deeper inside the truck may need to be temporarily removed or rearranged to access the target item. Therefore, it is important to consider both delivery route planning and package loading configuration together. In this study, we address this integrated optimization problem by extending the Environment-Adaptive Genetic Algorithm (EAGA)—a metaheuristic framework developed in our previous research. The extended algorithm simultaneously considers package placement within the truck and delivery sequencing, with the goal of minimizing the overall delivery time.