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

This paper considers the pickup and delivery problem with time windows (PDPTW). It is named as the single-commodity vehicle routing problem with pickups and deliveries, in which a fleet of vehicles satisfy a collection of customer requests. Each customer request requires the use of a single vehicle both to load a specified amount of one type of commodity at one location and to deliver them to another location. All requests must be performed without violating the vehicle capacity and the customer time windows specified for each location. In this study, we propose a novel Constraint Programming (CP) model for the PDPTW. CP is an exact solution approach which is well known for its abilities to express complex relationships and to obtain high-quality solutions within reasonable computational times for densely constrained combinatorial optimization problems such as the PDPTW. The performance of the proposed CP model is evaluated using benchmark instances from the literature. The computational results show that the proposed CP model is effective in finding high-quality solutions for large size problems.

Zaman pencereli toplama ve daðýtým problemi için kýsýt programlama yaklaþýmý

Bu makale zaman pencereli toplama ve daðýtým problemini (ZPTDP) ele almaktadýr. Problem, müþteri taleplerinin bir araç filosu tarafýndan karþýlandýðý, tek tip ürünlü, toplama ve daðýtýmlý araç rotalama problemi olarak adlandýrýlmaktadýr. Her müþteri talebi belli miktardaki bir ürünün bir lokasyondan yüklenmesini ve baþka bir lokasyona teslim edilmesini gerekli kýlmaktadýr. Talepler karþýlanýrken araçlarýn kapasitesi ve her bir lokasyon için belirlenmiþ zaman pencereleri ihlal edilmemelidir. Bu çalýþmada, ZPTDP için yeni bir kýsýt programlama (KP) modeli önermekteyiz. KP, ZPTDP gibi yoðun kýsýtlý kombinatorik optimizasyon problemlerinin karmaþýk iliþkilerinin tanýmlanmasýnda ve kabul edilebilir hesaplama süresi içinde yüksek kaliteli çözümler bulma yeterliliðinde iyi bilinen, kesin bir çözüm yaklaþýmýdýr. Önerilen KP modelini literatürde sýkça kullanýlan problem örneklerine uyguladýk. Aldýðýmýz sonuçlar KP modelimizin büyük boyutlu problemlerde dahi yüksek kaliteli sonuçlar verebilecek kadar etkili olduðunu göstermiþtir.