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

Mustafa KÜÇÜK, (Dokuz Eylül Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, İzmir, Türkiye)
Şeyda TOPALOĞLU YILDIZ (Dokuz Eylül Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, İzmir, Türkiye)
Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi
2 0
Yıl: 2019 Cilt: 25 Sayı: 9 Sayfa Aralığı: 1041 - 1049 Metin Dili: İngilizce DOI: 10.5505/pajes.2019.56804 İndeks Tarihi: 03-07-2020

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

Öz:
The pickup and delivery problem with time windows (PDPTW) isstudied in this paper. It is referred to as the single-commoditycapacitated vehicle routing problem with pickups and deliveries, inwhich a fleet of vehicles meet a group of customer demands. Eachcustomer demand includes the usage of only one vehicle for bothloading a specified quantity of one type of commodity at one place anddelivering them to another place. All the demands of customers mustbe satisfied without exceeding the vehicle capacity and the pickup ordelivery places time windows specified for each place. In this study, weintroduce a novel Constraint Programming (CP) model for the PDPTW.CP is an exact solution approach that is popular for its performance tostate complicated relationships and to achieve high-quality solutionswithin acceptable computational times for combinatorial optimizationproblems with complicated constraints such as the PDPTW. Theperformance of the proposed CP model is tested with well-knownbenchmark instances from literature. The results of computationalanalysis indicate that our CP model is very effective in finding highquality solutions for even large size problems.
Anahtar Kelime:

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

Öz:
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 ürünlü, toplama ve dağıtımlı araç rotalama problemi olarak adlandırılmaktadır. Her müşteri talebi belli miktardaki tek tip ürünün bir lokasyondan yüklenmesini ve başka bir lokasyona teslim edilmesini içermektedir. Müşteri talepleri araçların kapasitesi ve her bir lokasyon için belirlenmiş toplama ve dağıtım zaman pencereleri ihlal edilmeden karşılanmalıdır. Bu çalışmada, ZPTDP için yeni bir kısıt programlama (KP) modeli sunmaktayız. KP, ZPTDP gibi zor 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 bulmada yeterliliği iyi bilinen, kesin bir çözüm yaklaşımıdır. Önerilen KP modelini literatürde sıkça kullanılan karşılaştırma örneklerine uyguladık. Aldığımız sonuçlar KP modelimizin büyük boyutlu problemlerde bile yüksek kaliteli sonuçlar verebilecek kadar etkili olduğunu göstermiştir.
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • [1] Hernández‐Pérez H, Salazar‐González JJ. “The multi‐commodity pickup‐and‐delivery traveling salesman problem”. Networks, 63(1), 46-59, 2014.
  • [2] Ho SC, Szeto WY. “GRASP with path relinking for the selective pickup and delivery problem”. Expert Systems with Applications, 51, 14-25, 2016.
  • [3] Lenstra JK, Desroches M, Savelbergh MWP, Soumis F. “Vehicle routing with time windows: optimization and approximation”. Vehicle routing: Methods and studies, CWI Report, 65-84, 1988.
  • [4] Desrosiers J, Dumas Y, Solomon MM, Soumis F. “Time constrained routing and scheduling”. Handbooks in operations research and management science, 8, 35-139, 1995.
  • [5] Solomon MM, Desrosiers J. “Survey paper: time window constrained routing and scheduling problems”. Transportation Science, 22(1), 1-13, 1988.
  • [6] Savelsbergh MW, Sol M. “The general pickup and delivery problem”. Transportation Science, 29(1), 17-29, 1995.
  • [7] Toth P, Vigo D. The vehicle routing problem. Philadelphia, USA, SIAM, 2002.
  • [8] Li H, Lim A. “A metaheuristic for the pickup and delivery problem with time windows”. International Journal on Artificial Intelligence Tools, 12(2), 173-186, 2003.
  • [9] Bent R, Van Hentenryck P. “A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows”. Computers and Operations Research, 33(4), 875-893, 2006.
  • [10] Ropke S, Pisinger D. “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”. Transportation Science, 40(4), 455-472, (2006)..
  • [11] Parragh SN, Doerner KF, Hartl RF. “A survey on pickup and delivery models part ii: Transportation between pickup and delivery places”. Journal für Betriebswirtschaft, 58(2), 81-117, 2008.
  • [12] Nagata Y, Kobayashi S. “Guided ejection search for the pickup and delivery problem with time windows”. Evolutionary Computation in Combinatorial Optimization, Istanbul, Turkey, 7-9 April 2010.
  • [13] Nalepa J, Blocho M. “Enhanced guided ejection search for the pickup and delivery problem with time windows”. Intelligent Information and Database Systems, Da Nang, Vietnam, 14–16 March 2016.
  • [14] Xu H, Chen ZL, Rajagopal S, Arunapuram S. “Solving a practical pickup and delivery problem”. Transportation Science, 37(3), 347-364, 2003.
  • [15] Qu Y, Bard JF. “The heterogeneous pickup and delivery problem with configurable vehicle capacity”. Transportation Research Part C: Emerging Technologies, 32, 1-20, 2013.
  • [16] Bettinelli A, Ceselli A, Righini G. “A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows”. Mathematical Programming Computation, 6(2), 171-197, 2014.
  • [17] Männel D, Bortfeldt A. “A hybrid algorithm for the vehicle routing problem with pickup and delivery and threedimensional loading constraints”. European Journal of Operational Research, 254(3), 840-858, 2016.
  • [18] Tchoupo MN, Yalaoui A, Amodeo L, Yalaoui F, Flori P, Lutz F. “An efficient column-generation algorithm for a new fleet size and mix pickup and delivery problem with Time windows”. IFAC-PapersOnLine, 51(9), 440-445, 2018.
  • [19] Györgyi P, Kis T. “A probabilistic approach to pickup and delivery problems with time window uncertainty”. European Journal of Operational Research, 274(3), 909- 923, 2019.
  • [20] Lu EHC, Yang YW. “A hybrid route planning approach for logistics with pickup and delivery”. Expert Systems with Applications, 118, 482-492, 2019.
  • [21] Ropke S, Cordeau JF, Laporte G. “Models and branch‐and‐cut algorithms for pickup and delivery problems with time windows”. Networks: An International Journal, 49(4), 258-272, 2007.
  • [22] Rais A, Alvelos F, Carvalho MS. “New mixed integerprogramming model for the pickup-and-delivery problem with transshipment”. European Journal of Operational Research, 235(3), 530-539, 2014. [23] Cordeau JF. “A branch-and-cut algorithm for the dial-aride problem”. Operations Research, 54(3), 573-586, 2006.
  • [24] Rossi F, Van Beek P, Walsh T. “Constraint programming”. Foundations of Artificial Intelligence, 3, 181-211, 2008.
  • [25] Gedik R, Kirac E, Milburn AB, Rainwater C. “A constraint programming approach for the team orienteering problem with time windows”. Computers and Industrial Engineering, 107, 178-195, 2017.
  • [26] Rahimian E, Akartunalı K, Levine J. “A hybrid integer and constraint programming approach to solve nurse rostering problems”. Computers and Operations Research, 82, 83-94, 2017.
  • [27] Hojabri H, Gendreau M, Potvin JY, Rousseau LM. “Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints”. Computers and Operations Research, 92, 87- 97, 2018.
  • [28] Laborie P, Rogerie J, Shaw P, Vilím P. “IBM ILOG CP optimizer for scheduling”. Constraints, 23(2), 210-250, 2018.
  • [29] IBM Knowledge Center. “IBM ILOG CPLEX Optimization Studio V12.8.0 documentation”. https://www.ibm.com/support/knowledgecenter/en/SS SA5P_12.8.0/ilog.odms.studio.help/Optimization_Studio/ topics/COS_home.html (09.06.2019).
  • [30] Laborie P, Rogerie J. “Reasoning with conditional timeintervals”. Twenty-First International FLAIRS Conference, Florida, USA, 15–17 May 2008.
  • [31] Laborie P, Rogerie J, Shaw P, Vilím P. “Reasoning with conditional time intervals. Part II: An algebraical model for resources”. Twenty-Second International FLAIRS Conference, Florida, USA, 15–17 May 2009.
  • [32] Solomon MM. “Algorithms for the vehicle routing and scheduling problems with time window constraints”. Operations Research, 35(2), 254–265, 1987.
APA KÜÇÜK M, TOPALOĞLU YILDIZ Ş (2019). A constraint programming approach for the pickup and delivery problem with time windows. , 1041 - 1049. 10.5505/pajes.2019.56804
Chicago KÜÇÜK Mustafa,TOPALOĞLU YILDIZ Şeyda A constraint programming approach for the pickup and delivery problem with time windows. (2019): 1041 - 1049. 10.5505/pajes.2019.56804
MLA KÜÇÜK Mustafa,TOPALOĞLU YILDIZ Şeyda A constraint programming approach for the pickup and delivery problem with time windows. , 2019, ss.1041 - 1049. 10.5505/pajes.2019.56804
AMA KÜÇÜK M,TOPALOĞLU YILDIZ Ş A constraint programming approach for the pickup and delivery problem with time windows. . 2019; 1041 - 1049. 10.5505/pajes.2019.56804
Vancouver KÜÇÜK M,TOPALOĞLU YILDIZ Ş A constraint programming approach for the pickup and delivery problem with time windows. . 2019; 1041 - 1049. 10.5505/pajes.2019.56804
IEEE KÜÇÜK M,TOPALOĞLU YILDIZ Ş "A constraint programming approach for the pickup and delivery problem with time windows." , ss.1041 - 1049, 2019. 10.5505/pajes.2019.56804
ISNAD KÜÇÜK, Mustafa - TOPALOĞLU YILDIZ, Şeyda. "A constraint programming approach for the pickup and delivery problem with time windows". (2019), 1041-1049. https://doi.org/10.5505/pajes.2019.56804
APA KÜÇÜK M, TOPALOĞLU YILDIZ Ş (2019). A constraint programming approach for the pickup and delivery problem with time windows. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25(9), 1041 - 1049. 10.5505/pajes.2019.56804
Chicago KÜÇÜK Mustafa,TOPALOĞLU YILDIZ Şeyda A constraint programming approach for the pickup and delivery problem with time windows. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 25, no.9 (2019): 1041 - 1049. 10.5505/pajes.2019.56804
MLA KÜÇÜK Mustafa,TOPALOĞLU YILDIZ Şeyda A constraint programming approach for the pickup and delivery problem with time windows. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, vol.25, no.9, 2019, ss.1041 - 1049. 10.5505/pajes.2019.56804
AMA KÜÇÜK M,TOPALOĞLU YILDIZ Ş A constraint programming approach for the pickup and delivery problem with time windows. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. 2019; 25(9): 1041 - 1049. 10.5505/pajes.2019.56804
Vancouver KÜÇÜK M,TOPALOĞLU YILDIZ Ş A constraint programming approach for the pickup and delivery problem with time windows. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi. 2019; 25(9): 1041 - 1049. 10.5505/pajes.2019.56804
IEEE KÜÇÜK M,TOPALOĞLU YILDIZ Ş "A constraint programming approach for the pickup and delivery problem with time windows." Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25, ss.1041 - 1049, 2019. 10.5505/pajes.2019.56804
ISNAD KÜÇÜK, Mustafa - TOPALOĞLU YILDIZ, Şeyda. "A constraint programming approach for the pickup and delivery problem with time windows". Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi 25/9 (2019), 1041-1049. https://doi.org/10.5505/pajes.2019.56804
Sayfa Oluşturulma Tarihi
23-04-2024 12:31

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları