A hybrid constraint programming / local search approach to the pick-up and delivery problem with time windows

Routing vehicles to serve customers is a problem that naturally arises in many distribution systems. Moreover, fleet management requires fast algorithms able to cope with continuously changing needs. Many efforts have been addressed to tackle different vehicle routing problem's variants. Among them, the pick up and delivery problem with time windows (PDTW) has received far less attention despite its relevance from practical and theoretical perspectives. The present paper provides a hybrid approach to the PDTW based on Constraint Programming paradigm and local search. Indeed, the proposed algorithm includes some performance improvements to enhance its efficiency. Thus, this hybrid approach may provide a solution to problems otherwise intractable in a reasonable computational time, as shown in the presented results. Due to these characteristics, the proposed algorithm may be an efficient tool in decision making support, as well as a mechanism able to provide an initial solution for subsequent optimization techniques.