Abstract: According to whether customers purchase on-time delivery services or are willing to pay additional fees for early delivery, on-demand delivery orders are classified into different types. In addition to the initial order requirements, new orders may arise during the delivery process. A mathematical model is established with the objective of minimizing the sum of vehicle delivery costs and customer time costs, considering constraints such as delivery time windows, vehicle capacity, and the service range of crowdsourced vehicles. An improved hybrid tabu search algorithm based on rolling time horizons is designed to solve the problem, which incorporates a dynamic adjustment mechanism for the tabu step size and a diversification strategy for solutions. Parameter analysis shows that, in order to effectively reduce costs, transportation companies should avoid setting long update intervals. Instead, they should prioritize the delivery of heterogeneous orders of the second and third categories, and expand the service range of crowdsourced vehicles while fully utilizing the vehicles within this range. Multiple case studies of different scales demonstrate that the improved hybrid tabu search algorithm based on rolling time horizons can effectively solve cases of various scales.