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 rep...

Full description

Saved in:
Bibliographic Details
Main Authors: Tam, V., Kwan, M.C.
Format: Conference Proceeding
Language:English
Subjects:
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Constraint optimization
Exact sciences and technology
heuristic search
IEEE services
Job shop scheduling
Processor scheduling
Proposals
Routing
scheduling
Transportation
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1082-3409
2375-0197
DOI:10.1109/ICTAI.2004.23