Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı

Year 2014, Volume: 43 Issue: 2, 391 - 403, 14.11.2014

Baris Kiremitci , Serap Kiremitci Timur Keskintürk

Abstract

Bu çalışmada; çok araçlı, dağıtım toplamalı, zaman pencereli rotalama problemlerinin, gerçek değerli kodlamalı genetik algoritma ile çözümü ele alınmıştır. Problemde rotalar, kapasite, zaman pencereleri, eşleşme ve öncelik kısıtları dikkate alınarak oluşturulmaktadır. Amaç fonksiyonu, toplam mesafenin minimizasyonu, araç sayısının minimizasyonu veya her ikisi birlikte olacak şekilde belirlenebilmektedir. Gerçek hayatta problemin geniş bir uygulama sahası olmasına rağmen araç rotalama literatüründe, problemin zorluğundan dolayı, çok fazla yayın yer almamaktadır. Çalışmamızda probleme özgün yeni bir gerçek değerli kodlamalı genetik algoritma geliştirilmiştir. Probleme ait değişkenler farklı bir yapıda, gerçek değerlerle kodlanmıştır. Böylelikle daha küçük boyutlu kromozomlarla, daha az değişkenle çözüm prosesi geliştirilmeye çalışılmıştır. Algoritma literatürdeki bir kısım problemler üzerinde denenmiş ve mevcut algoritmalar ile performans karşılaştırılması yapılmıştır.

Keywords

Bu çalışmada; çok araçlı, dağıtım toplamalı, zaman pencereli rotalama problemlerinin, gerçek değerli kodlamalı genetik algoritma ile çözümü ele alınmıştır. Problemde rotalar, kapasite, zaman pencereleri, eşleşme ve öncelik kısıt

References

• D. Simchi-Levi, X. Chen, J. Bramel, The Logic of Logistics: Theory, Algorithms and Applications for Logistics Management, Springer, 2005.
• O. Bräysy, M. Gendreau, Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Science, 39, 1, 119-139 (2005).
• T.G. Crainic, G. Laporte, Fleet Management and Logistics, Springer, 1998.
• J.F. Cordeau, G. Laporte, M.W.P. Savelsbergh, D. Vigo, Vehicle Routing. Transportation, Handbooks in Operations Research and Management Science, 14, 367–428 (2007).
• M.M. Solomon, J. Desrosiers, Survey Paper-Time Window Constrained Routing and Scheduling Problems. Transportation Science, 22, 1-13 (1988).
• M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35, 2, 254-265 (1987).
• B. Funke, T. Grünert, S. Irnich, Local search for vehicle routing and scheduling problems: Review and conceptual integration. Journal of Heuristics, 11, 4, 267-306 (2005).
• L.D. Bodin, Twenty years of routing and scheduling. Operations Research, 38, 4, 571- 579 (1990).
• G.B. Dantzig, J.H. Ramser, The Truck Dispatching Problem. Management Science, 6, 1, 80–91 (1959).
• G. Laporte, Fifty Years of Vehicle Routing. Transportation Science, 43, 4, 408–16 (2009).
• B. Eksioglu, A.V. Vural, A. Reisman, The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57, 1472–1483 (2009).
• B.L. Golden, A.A. Assad, E.A. Wasil, Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. The vehicle routing problem, 9, 245-286 (2002).
• Partyka, Janice G., and Randolph W. Hall, On the Road to Service. OR/MS Today 27, 4, 26–35 (2000).
• R.H. Ballou, Business Logistics and Supply Chain Management, Pearson Prentice Hall, 2004.
• P. Brandimarte, G. Zotteri, Introduction to Distribution Logistics, Wiley-Interscience. 2007.
• P. Toth, D. Vigo, The Vehicle Routing Problem, SIAM, 2002.
• G. Desaulniers, J. Desrosiers, M.M. Solomon, Column Generation, Springer, 2005.
• G. Berbeglia, J.-F. Cordeau, I. Gribkovskaia, G. Laporte, Static pickup and delivery problems: A classification schema and survey. Top, 15, 1–31 (2007).
• M.W.P Savelsbergh, M. Sol, The General Pickup and Delivery Problem. Transportation Science, 29, 1, 17–29 (1995).
• M. I. Hosny, C. L. Mumford, Investigating Genetic Algorithms for Solving the Multiple Vehicle Pickup and Delivery Problem with Time Windows. MIC2009, Metaheuristic International Conference, Hamburg, Germany. 2009.
• M. I. Hosny, C. L. Mumford, The single vehicle pickup and delivery problem with time windows: intelligent operators for heuristic and metaheuristic algorithms. Journal Heuristics, 16, 417–39 (2010).
• S. Ropke, J.F. Cordeau, G. Laporte, Models and branch-and-cut algorithms for pickup and delivery problems with time windows. NETWORKS, 258–72 (2007).
• S. Ropke, J.-F. Cordeau, Branch-and-cut-and price for the pickup and delivery problem with time windows. Transportation Science, 43, 3, 267–86 (2009).
• D.E. Goldberg, Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley Publishing Company, USA, 1989.
• Z. Michalewicz, Genetic Algorithms + Data Structure = Evolution Programs, Springer- Verlag, Berlin, 1992.
• C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems, McGraw-Hill Book Company Inc., Europe, 1995.
• R. M. Jorgensen, J. Larsen, K. B. Bergvinsdottir, Solving the dial-a-ride problem using genetic algorithms. Journal of the Operational Research, 58, 10, 1321–31 (2007).
• G. Pankratz, A grouping genetic algorithm for the pickup and delivery problem with time windows. OR Spectrum, 27, 21–41 (2005).
• J.-C. Créput, A. Koukam, J. Kozlak, J. Lukasik, An Evolutionary Approach to Pickup and Delivery Problem with Time Windows. In Computational Science-ICCS 2004, 1102–8 (2004).
• Y. Nagata, S. Kobayashi, A Memetic Algorithm for the Pickup and Delivery Problem with Time Windows Using Selective Route Exchange Crossover, In Parallel Problem Solving from Nature PPSN XI, 6238, 536–545 (2010).
• D. E. Goldberg, K. Deb, A Comparative Analysis of Selection Schemes Used in Genetic Algorithms, Urbana, 51, 61801–996 (1991).
• H. Li, A. Lim, A Metaheuristic for the Pickup and Delivery Problem with Time Windows, In Tools with Artificial Intelligence, Proceedings of the 13th International Conference on, 160–67 (2001).