Adapting the large neighborhood search to effectively solve pickup and delivery problems with time windows

Pickup and delivery problems with time windows (PDP-TW) are challenging combinatorial optimization problems widely occurring in modern distribution and transportation industry. A previous proposal successfully adapted and combined the well-known push forward insertion heuristic (PFIH) with a new repair-based swap operator as a computationally reduced version of the large neighborhood search (LNS) to efficiently solve the PDP-TWs. We focus on a more systematic scheme to adapt the LNS in order to effectively solve PDP-TWs. Up to our knowledge, this work represents the first attempt to systematically adapt LNS for solving PDP-TWs. Besides, the empirical results obtained by our search proposals affirmed the attractive capability of the LNS approach to effectively reduce the total distance traveled in solving PDP-TWs, with similar results also achieved by the original LNS method in tackling the conventional vehicle routing problems with time windows. Lastly, our proposal of adapting LNS to solve hard combinatorial problems opens up many possible directions for future investigations.