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

Abstract

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.

Keywords

• Kısıt programlama,Toplama ve dağıtım problemi,Zaman pencereleri

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

References

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 three-dimensional 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 integer-programming 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-a-ride 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/SSSA5P_12.8.0/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html (09.06.2019).
30. Laborie P, Rogerie J. “Reasoning with conditional time-intervals”. 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.