Research Article
BibTex RIS Cite

A Hyrid Genetic Algorithm Approach for Solving Partner Constrained Lane Covering Problems

Year 2020, Volume: 22 Issue: 65, 401 - 416, 15.05.2020
https://doi.org/10.21205/deufmd.2020226509

Abstract

Partner
Constrained Lane Covering Problems (PCLCPs) are NP-Hard arc routing problems
arising in collaborative truckload transportation procurement networks. The
objective in these problems is to cover a set of full truckload shipment lanes
of multiple shippers using cyles, each of which may include lanes from
different shippers and empty truck movements, with minimum total cost such that
each shipper does not share cycles with more than a prespecified number of partners.
This paper presents a hybrid genetic algorithm (HGA) approach that combines
genetic algorithm, local search and large neighborhood search approaches for
solving PCLCPs.  This approach is the
first meta-heuristic that has been proposed for solving NP-Hard LCPs. The
proposed MGA has been tested on instances that were previously used in the
literature. It has improved the previous best known solutions of a significant
portion of the large scale instances that were tested. 

References

  • Ergun, Ö., Kuyzu, G., Savelsbergh, M., 2007. Shipper collaboration. Computers & Operations Research, 34, 1551–1560.
  • Ergun, Ö., Kuyzu, G., Savelsbergh, M., 2007. Reducing Truckload Transportation Costs Through Collaboration. Transportation Science 41, 206–221.
  • Kuyzu, G., 2017. Lane covering with partner bounds in collaborative truckload transportation procurement. Computers & Operations Research 77, 32–43.
  • Immorlica, N., Mahdian, M., Mirrokni, V.S., 2005. Cycle Cover with Short Cycles, in: Diekert, V., Durand, B. (Eds.), STACS 2005, Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 641–653.
  • Thomassen, C., 1997. On the complexity of finding a minimum cycle cover of a graph. SIAM Journal on Computing 26, 675–677.
  • Hochbaum, D. S. , Olinick, V., 2001. The bounded cycle-cover problem, INFORMS Journal on Computing, 13(2), 104-119.
  • Fernandes, C.G., Lee, O., Wakabayashi, Y., 2009. Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width. Discrete Applied Mathematics 157, 272–279.
  • Golden, B.L., Wong, R.T., 1981. Capacitated arc routing problems. Networks 11, 305–315.
  • Corberán, A., Prins, C., 2010. Recent results on Arc Routing Problems: An annotated bibliography. Networks 56, 50–69.
  • Moscato, P., Cotta, C., 2010. A Modern Introduction to Memetic Algorithms, in: Gendreau, M., Potvin, J.-Y. (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science. Springer US, Boston, MA, pp. 141–183.
  • Lacomme, P., Prins, C., Ramdane-Cherif, W., 2004. Competitive Memetic Algorithms for Arc Routing Problems. Ann Oper Res 131, 159–185.
  • Prins, C., 2004. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31, 1985–2002.
  • Prins, C., 2009. Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, Artificial Intelligence Techniques for Supply Chain Management 22, 916–928.
  • Liu, R., Jiang, Z., Liu, X., Chen, F., 2010. Task selection and routing problems in collaborative truckload transportation. Transportation Research Part E: Logistics and Transportation Review 46, 1071–1085.
  • Chen, Y., Hao, J.-K., Glover, F., 2016. A hybrid metaheuristic approach for the capacitated arc routing problem. European Journal of Operational Research 253, 25–39.
  • Arakaki, R.K., Usberti, F.L., 2018. Hybrid genetic algorithm for the open capacitated arc routing problem. Computers & Operations Research 90, 221–231.
  • Tirkolaee, E.B., Hosseinabadi, A.A.R., Soltani, M., Sangaiah, A.K., Wang, J., 2018. A Hybrid Genetic Algorithm for Multi-Trip Green Capacitated Arc Routing Problem in the Scope of Urban Services. Sustainability 10, 1366.
  • Hiermann, G., Hartl, R.F., Puchinger, J., Vidal, T., 2019. Routing a mix of conventional, plug-in hybrid, and electric vehicles. European Journal of Operational Research 272, 235–248.
  • G. Ulusoy, “The fleet size and mix problem for capacitated arc routing”, European Journal of Operational Research, 22(3), 329-337, 1985.
  • Pisinger, D., Ropke, S., 2010. Large Neighborhood Search, in: Gendreau, M., Potvin, J.-Y. (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science. Springer US, Boston, MA, pp. 399–419.
  • Pugliese, L.D.P., Guerriero, F., 2013. A survey of resource constrained shortest path problems: Exact solution approaches. Networks 62, 183–200.

Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı

Year 2020, Volume: 22 Issue: 65, 401 - 416, 15.05.2020
https://doi.org/10.21205/deufmd.2020226509

Abstract

Ortak Kısıtlı Rota Kapsama
Problemleri (OKRKP’ler) tam kamyon yükü hizmeti satın alma işbirliği ağlarında ortaya
çıkan NP-Zor ayrıt rotalama problemleridirler. Bu problemlerde amaç, işbirliği
yapan birden fazla gönderici firmanın tam kamyon yükü gönderi rotalarını,
birden fazla gönderici firmadan gönderi rotası ve boş kamyon hareketleri içerebilecek
ve göndericilerin çevrim paylaşmak istediği azami ortak sayılarını aşmadan
kapsayan en kısa toplam uzunluklu yönlü çevrimler kümesini bulmaktır. Bu
makale, OKRKP’lerin çözümü için geliştirilen; genetik algoritma, yerel arama ve
geniş komşuluk arama yaklaşımlarının birleşiminden oluşan bir melez genetik
algoritma (MGA) yaklaşımını sunmaktadır. Bu yaklaşım, NP-Zor RKP’lerin çözümü
için önerilen ilk meta-sezgisel çözüm yaklaşımıdır. 
Önerilen MGA, daha önce literatürdeki
çalışmalarda kullanılan problem örnekleri üzerinde denenmiştir. Deneylerde
kullanılan büyük ölçekli problem örneklerinin önemli bir kısmında bilinen en
iyi çözümlerden daha iyi çözümler elde edilmiştir. 

References

  • Ergun, Ö., Kuyzu, G., Savelsbergh, M., 2007. Shipper collaboration. Computers & Operations Research, 34, 1551–1560.
  • Ergun, Ö., Kuyzu, G., Savelsbergh, M., 2007. Reducing Truckload Transportation Costs Through Collaboration. Transportation Science 41, 206–221.
  • Kuyzu, G., 2017. Lane covering with partner bounds in collaborative truckload transportation procurement. Computers & Operations Research 77, 32–43.
  • Immorlica, N., Mahdian, M., Mirrokni, V.S., 2005. Cycle Cover with Short Cycles, in: Diekert, V., Durand, B. (Eds.), STACS 2005, Lecture Notes in Computer Science. Springer Berlin Heidelberg, pp. 641–653.
  • Thomassen, C., 1997. On the complexity of finding a minimum cycle cover of a graph. SIAM Journal on Computing 26, 675–677.
  • Hochbaum, D. S. , Olinick, V., 2001. The bounded cycle-cover problem, INFORMS Journal on Computing, 13(2), 104-119.
  • Fernandes, C.G., Lee, O., Wakabayashi, Y., 2009. Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width. Discrete Applied Mathematics 157, 272–279.
  • Golden, B.L., Wong, R.T., 1981. Capacitated arc routing problems. Networks 11, 305–315.
  • Corberán, A., Prins, C., 2010. Recent results on Arc Routing Problems: An annotated bibliography. Networks 56, 50–69.
  • Moscato, P., Cotta, C., 2010. A Modern Introduction to Memetic Algorithms, in: Gendreau, M., Potvin, J.-Y. (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science. Springer US, Boston, MA, pp. 141–183.
  • Lacomme, P., Prins, C., Ramdane-Cherif, W., 2004. Competitive Memetic Algorithms for Arc Routing Problems. Ann Oper Res 131, 159–185.
  • Prins, C., 2004. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research 31, 1985–2002.
  • Prins, C., 2009. Two memetic algorithms for heterogeneous fleet vehicle routing problems. Engineering Applications of Artificial Intelligence, Artificial Intelligence Techniques for Supply Chain Management 22, 916–928.
  • Liu, R., Jiang, Z., Liu, X., Chen, F., 2010. Task selection and routing problems in collaborative truckload transportation. Transportation Research Part E: Logistics and Transportation Review 46, 1071–1085.
  • Chen, Y., Hao, J.-K., Glover, F., 2016. A hybrid metaheuristic approach for the capacitated arc routing problem. European Journal of Operational Research 253, 25–39.
  • Arakaki, R.K., Usberti, F.L., 2018. Hybrid genetic algorithm for the open capacitated arc routing problem. Computers & Operations Research 90, 221–231.
  • Tirkolaee, E.B., Hosseinabadi, A.A.R., Soltani, M., Sangaiah, A.K., Wang, J., 2018. A Hybrid Genetic Algorithm for Multi-Trip Green Capacitated Arc Routing Problem in the Scope of Urban Services. Sustainability 10, 1366.
  • Hiermann, G., Hartl, R.F., Puchinger, J., Vidal, T., 2019. Routing a mix of conventional, plug-in hybrid, and electric vehicles. European Journal of Operational Research 272, 235–248.
  • G. Ulusoy, “The fleet size and mix problem for capacitated arc routing”, European Journal of Operational Research, 22(3), 329-337, 1985.
  • Pisinger, D., Ropke, S., 2010. Large Neighborhood Search, in: Gendreau, M., Potvin, J.-Y. (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science. Springer US, Boston, MA, pp. 399–419.
  • Pugliese, L.D.P., Guerriero, F., 2013. A survey of resource constrained shortest path problems: Exact solution approaches. Networks 62, 183–200.
There are 21 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Research Article
Authors

Gültekin Kuyzu 0000-0002-1997-306X

Publication Date May 15, 2020
Published in Issue Year 2020 Volume: 22 Issue: 65

Cite

APA Kuyzu, G. (2020). Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi, 22(65), 401-416. https://doi.org/10.21205/deufmd.2020226509
AMA Kuyzu G. Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı. DEUFMD. May 2020;22(65):401-416. doi:10.21205/deufmd.2020226509
Chicago Kuyzu, Gültekin. “Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi 22, no. 65 (May 2020): 401-16. https://doi.org/10.21205/deufmd.2020226509.
EndNote Kuyzu G (May 1, 2020) Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 22 65 401–416.
IEEE G. Kuyzu, “Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı”, DEUFMD, vol. 22, no. 65, pp. 401–416, 2020, doi: 10.21205/deufmd.2020226509.
ISNAD Kuyzu, Gültekin. “Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi 22/65 (May 2020), 401-416. https://doi.org/10.21205/deufmd.2020226509.
JAMA Kuyzu G. Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı. DEUFMD. 2020;22:401–416.
MLA Kuyzu, Gültekin. “Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı”. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen Ve Mühendislik Dergisi, vol. 22, no. 65, 2020, pp. 401-16, doi:10.21205/deufmd.2020226509.
Vancouver Kuyzu G. Ortak Kısıtlı Rota Kapsama Problemlerinin Çözümü İçin Melez Genetik Algoritma Yaklaşımı. DEUFMD. 2020;22(65):401-16.

Dokuz Eylül Üniversitesi, Mühendislik Fakültesi Dekanlığı Tınaztepe Yerleşkesi, Adatepe Mah. Doğuş Cad. No: 207-I / 35390 Buca-İZMİR.