A three-dimensional loading vehicle routing problem with split pickups, promised service periods and time windows under real-time disruptions

The first-mile collection usually refers to the first logistics activities in the supply chain, encompassing both the forward flow of goods from retailers to a depot and the reverse flow of returned products from customers back to retailers. With the rise of e-commerce and the growing number of product returns, optimizing this stage is crucial, as inefficiencies here can propagate throughout the entire supply chain and lead to customer dissatisfaction.
In practice, the pickup phase is usually managed by a logistics service provider (LSP), who faces daily challenges in planning routes, scheduling visits, and loading boxes under realistic physical and operational constraints. More precisely, we conducted a survey among Belgian LSPs that revealed that they deal with time windows, time-dependent travel durations, and split pickups, as well as practical three-dimensional loading issues such as box stability and reachability. To increase customer satisfaction and mirror delivery operations, we also consider that LSPs provide promised service periods during which pickups take place. Finally, these LSPs must constantly adapt their decisions to real-time changes, such as new or modified customer requests, which may render their initial planning infeasible.
This thesis aims to support LSPs in making effective and adaptive decisions under these conditions by proposing several optimization methods. Its contributions are conceptual, algorithmic, benchmarking, and managerial in nature.
The first part of the thesis addresses the static problem, where data are known in advance and do not change throughout the pickup day. We develop a mixed-integer linear programming formulation, extend the insert-and-fix heuristic, and design a three-phase heuristic capable of efficiently handling large-scale instances. The second part focuses on the dynamic problem, in which customer-related disruptions arise in real time. To help LSPs respond swiftly to such disruptions, we design a fast and responsive disruption management algorithm.
Furthermore, new benchmark instances were created to evaluate these methods, since existing datasets did not encompass all the studied features. Based on the experiments conducted on these new instances, the static problem results demonstrate significant managerial benefits: allowing split pickups reduces operational costs, and extending customer time windows shortens driver working durations. The results also highlight the effects of reachability constraints on total cost and the impact of speed variations during peak hours on schedule feasibility. For the dynamic problem, computational results show that allowing multiple departures as a recourse action enables the acceptance of more than 80% of new customers while maintaining service levels close to 98% for the other disruption types. Moreover, the managerial insights emphasize the trade-off between customer satisfaction and cost reduction when scheduling the promised service periods and underline the benefit of anticipative disruption notifications from customers to the LSP.