ECAI 2004 Conference Paper

[full paper]

Improving the Initialization and Repair Heuristics to Effectively Solve the Pickup and Delivery Problems with Time Windows

Vincent TAM, M.C. KWAN

Pickup and delivery problems with time windows (PDP-TW) are challenging real-world scheduling problems in which each delivery vehicle is assigned to handle different pairs of delivery-and-pickup requests. In our previous work, we successfully adapted the push forward insertion heuristic (PFIH) for initialization, and proposed a new Swap operator to effectively solve PDP-TW. In this paper, we have improved our previous search proposal by modifying the adapted PFIH method to efficiently obtain a better initial solution. More importantly, we proposed an adaptive swapping (ADP-SWAP) mechanism that can flexibly revise the neighbourhood size to aggressively look for possible improvements. Our search prototype using improved initialization and repair methods achieved remarkable results against those of a tabu-embedded metaheuristic search or our previous work on a set of modified Solomon's test cases. Besides, there are still many exciting directions for possible improvements or investigation in our search framework.

Keywords: Scheduling, Meta-Heuristics for AI, Automated Reasoning.

Citation: Vincent TAM, M.C. KWAN: Improving the Initialization and Repair Heuristics to Effectively Solve the Pickup and Delivery Problems with Time Windows . In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.687-691.