ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

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.


[prev] [tofc] [next]


ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).