A hierarchical optimization approach for dynamic pickup and delivery problem with LIFO constraints
Abstract
We consider a dynamic pickup and delivery problem (DPDP) where loading and unloading operations must follow a last in first out (LIFO) sequence. A fleet of vehicles will pick up orders in pickup points and deliver them to destinations. The objective is to minimize the total over-time (that is the amount of time that exceeds the committed delivery time) and total travel distance. Given the dynamics of orders and vehicles, this paper proposes a hierarchical optimization approach based on multiple intuitive yet often-neglected strategies, namely what we term as the urgent strategy, hitchhike strategy and packing-bags strategy. These multiple strategies can dynamically adapt to dispatch orders to vehicles according to the status of orders and by considering the travel distance and overtime. To account for the LIFO constraints, block-based operators are designed to schedule the delivery routes, thereby enhancing the search efficiency. The result on real-world instances shows that our proposed hierarchical optimization approach outperforms the current practice and the winning approach in an international competition. Finally, the insights gained from generated instances shows the hierarchical optimization approach has broader applicability.