BibTex RIS Cite

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

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.

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).

-

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

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

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).
There are 32 citations in total.

Details

Primary Language English
Journal Section Operations Research
Authors

Baris Kiremitci

Serap Kiremitci This is me

Timur Keskintürk

Publication Date November 14, 2014
Published in Issue Year 2014 Volume: 43 Issue: 2

Cite

APA Kiremitci, B., Kiremitci, S., & Keskintürk, T. (2014). Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43(2), 391-403.
AMA Kiremitci B, Kiremitci S, Keskintürk T. Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi. November 2014;43(2):391-403.
Chicago Kiremitci, Baris, Serap Kiremitci, and Timur Keskintürk. “Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı”. İstanbul Üniversitesi İşletme Fakültesi Dergisi 43, no. 2 (November 2014): 391-403.
EndNote Kiremitci B, Kiremitci S, Keskintürk T (November 1, 2014) Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi 43 2 391–403.
IEEE B. Kiremitci, S. Kiremitci, and T. Keskintürk, “Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı”, İstanbul Üniversitesi İşletme Fakültesi Dergisi, vol. 43, no. 2, pp. 391–403, 2014.
ISNAD Kiremitci, Baris et al. “Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı”. İstanbul Üniversitesi İşletme Fakültesi Dergisi 43/2 (November 2014), 391-403.
JAMA Kiremitci B, Kiremitci S, Keskintürk T. Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi. 2014;43:391–403.
MLA Kiremitci, Baris et al. “Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı”. İstanbul Üniversitesi İşletme Fakültesi Dergisi, vol. 43, no. 2, 2014, pp. 391-03.
Vancouver Kiremitci B, Kiremitci S, Keskintürk T. Zaman Pencereli Çok Araçlı Dağıtım Toplamalı Rotalama Problemi için Gerçek Değerli Genetik Algoritma Yaklaşımı. İstanbul Üniversitesi İşletme Fakültesi Dergisi. 2014;43(2):391-403.