A constraint programming approach for the pickup and delivery problem with time windows

Abstract

The pickup and delivery problem with time windows (PDPTW) is studied in this paper. It is referred to as the single-commodity capacitated vehicle routing problem with pickups and deliveries, in which a fleet of vehicles meet a group of customer demands. Each customer demand includes the usage of only one vehicle for both loading a specified quantity of one type of commodity at one place and delivering them to another place. All the demands of customers must be satisfied without exceeding the vehicle capacity and the pickup or delivery places time windows specified for each place. In this study, we introduce a novel Constraint Programming (CP) model for the PDPTW. CP is an exact solution approach that is popular for its performance to state complicated relationships and to achieve high-quality solutions within acceptable computational times for combinatorial optimization problems with complicated constraints such as the PDPTW. The performance of the proposed CP model is tested with well-known benchmark instances from literature. The results of computational analysis indicate that our CP model is very effective in finding high-quality solutions for even large size problems.

Keywords

• constraint programming
• pickup and delivery problem
• time windows
• kısıt programlama
• toplama ve dağıtım problemi
• zaman pencereleri