A constraint programming approach for the pickup and delivery problem with time windows [Pamukkale Univ Muh Bilim Derg]
Pamukkale Univ Muh Bilim Derg. 2019; 25(9): 1041-1049 | DOI: 10.5505/pajes.2019.56804  

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

Mustafa Kucuk, Seyda Topaloglu Yildiz
Dokuz Eylül University, Department Of Industrial Engineering, İzmir, Turkey

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.

Keywords: Constraint Programming, Pickup and Delivery Problem, Time Windows


Zaman pencereli toplama ve dağıtım problemi için kısıt programlama yaklaşımı

Mustafa Kucuk, Seyda Topaloglu Yildiz
Dokuz Eylül Üniversitesi, Endüstri Mühendisliği Bölümü, İzmir, Türkiye

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.

Anahtar Kelimeler: Kısıt Programlama, Toplama ve Dağıtım Problemi, Zaman Pencereleri


Mustafa Kucuk, Seyda Topaloglu Yildiz. A constraint programming approach for the pickup and delivery problem with time windows. Pamukkale Univ Muh Bilim Derg. 2019; 25(9): 1041-1049

Corresponding Author: Seyda Topaloglu Yildiz, Türkiye


TOOLS
Full Text PDF
Print
Download citation
RIS
EndNote
BibTex
Medlars
Procite
Reference Manager
Share with email
Share
Send email to author

Similar articles
Google Scholar


 
Creative Commons License
This journal is licensed under a Creative Commons Attribution 4.0 International License


LookUs & Online Makale