Using genetic algorithm to solve multiple traveling salesman problem and considering Carbon emissions

Chris Jojo Obi; Xiong Qiang; Appiah Martinson Yeboah

doi:10.17485/IJST/v13i36.1316

Article

Using genetic algorithm to solve multiple traveling salesman problem and considering Carbon emissions

VIEWS 2435
PDF 613

Indian Journal of Science and Technology

DOI: 10.17485/IJST/v13i36.1316

Year: 2020, Volume: 13, Issue: 36, Pages: 3707-3715

Original Article

Using genetic algorithm to solve multiple traveling salesman problem and considering Carbon emissions

Chris Jojo Obi^1*, Xiong Qiang¹, Appiah Martinson Yeboah¹

¹School of Management, Jiangsu University, 301, Xuefu Road, Zhenjiang, 212013, China

*Corresponding Author
Email: [email protected]

Received Date:18 August 2020, Accepted Date:16 September 2020, Published Date:06 October 2020

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

Objectives: The Multiple Travelling Salesman problem is a complex combinatorial optimization problem which is a variance of the Traveling Salesman Problem,where a lot of salesmen are utilized in the solution. In this work a cold chain logistics and route optimization model with minimum transport cost, carbon cost and Refrigeration cost are constructed. Methods: A genetic algorithm is then proposed to solve for the Multiple Travelling Salesman Problem with time windows while transport cost, carbon emission cost and refrigeration cost is minimized. Findings: It was observed that the algorithm evolved towards the direction of the optimal value of the fitness function. Novelty: There are a number of studies that considered tournament selection strategy but just a few have applied genetic algorithm considering insertion method to solve a Multiple Travelling salesman Problem. This study uses insertion method to obtain optimal solution. Also, the researcher considered time windows, transport cost, carbon emission cost and refrigeration cost.

Keywords: Genetic algorithm method; cold-logistics; multiple travelling salesman problem

References

Aditi KM. A hybrid heuristic algorithm for single and multi-objective imprecise traveling salesman problems. Journal of Intelligent and Fuzzy Systems. 2001. Available from: https://doi.org/10.3233/IFS-151913
Ala MN. Particle Swarm Optimization: Algorithm and its Codes in MATLAB. 2016. Available from: https://doi.org/10.13140/RG.2.1.4985.3206
Ali O, Vanoudheusden D. Logistics Planning for Agricultural Vehicles. In: Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management. (pp. 8-11) 2009.
Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega. 2006;34(3):209–219. Available from: https://dx.doi.org/10.1016/j.omega.2004.10.004
Gutin G, PA. The Traveling Salesman Problem and Its Variations Combinatorial Optimization. Kluwer Academic Publishers. 2002.
Hussain A, Muhammad YS, Sajid MN, Hussain I, Shoukry AM, Gani S. Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator. Computational Intelligence and Neuroscience. 2017;2017:1–7. Available from: https://dx.doi.org/10.1155/2017/7430125
Krishna HR. Self-Adaptive Trust Model for Secure Geographic Routing in Wireless Sensor Networks Computer Engineering and Intelligent Systems. 2015. Available from: https://doi.org/10.5815/ijisa.2015.03.03
Leng L, Zhang J, Zhang C, Zhao Y, Wang W, Li G. A novel bi-objective model of cold chain logistics considering location-routing decision and environmental effects. PLOS ONE. 2020;29.
Liao TY. On-Line Vehicle Routing Problems for Carbon Emissions Reduction. . Computer-Aided Civil and Infrastructure Engineering. 2017;17. Available from: https://doi.org/10.1111/mice.12308
Jiang HCL. A Travelling Salesman Problem with Carbon Emission Reduction in the Last Mile Delivery. IEEE Access. 2019;8. Available from: https://doi.org/10.1080/00207543.2019.1656842
Zhang Y, Guo W, Cheng T, Zhang J. Cold chain distribution: How to deal with node and arc time windows. Annals of Operation Research. 2020. Available from: https://doi.org/10.1007/s10479-018-3071-0
Meneghetti A, Monti L. Greening the food supply chain: an optimisation model for sustainable design of refrigerated automated warehouses. International Journal of Production Research. 2015;53(21):6567–6587. Available from: https://dx.doi.org/10.1080/00207543.2014.985449
Leng LO, Zhang J, Zhang C, Zhao Y, Wang W, Li G. A novel bi-objective model of cold chain logistics considering location-routing decision and environmental effects. PLOS. 2020;29.
Venkatesh P, AS. Two metaheuristic approaches for the multiple traveling salesperson problem. Applied Soft Computing. 2015;p. 74–89. Available from: https://doi.org/10.1016/j.asoc.2014.09.029
Shokouhi RA. Solving multiple traveling salesman problem using the gravitational emulation local search algorithm. Applied Maths. 2015;11. Available from: https://doi.org/10.12785/amis/090218
Wang S, Tao F, Shi Y. Optimization of Location–Routing Problem for Cold Chain Logistics Considering Carbon Footprint. International Journal of Environmental Research and Public Health. 2018;15(1). Available from: https://dx.doi.org/10.3390/ijerph15010086
Xiao-Hong L, Shan MY, Zhang RL, Zhang LH. Green Vehicle Routing Optimization Based on Carbon Emission and Multiobjective Hybrid Quantum Immune Algorithm. Hindawi Mathematical Problems in Engineering. 2018;1.
Harrath Y, AF. A novel hybrid approach for solving the multiple traveling salesmen problem. Arab Journal of Basic and applied sciences. 2019;11. Available from: https://doi.org/10.1080/25765299.2019.1565193
Ziqi W, Peihan W. Optimization of a Low-Carbon Two-Echelon Heterogeneous-Fleet Vehicle Routing for Cold Chain. Sustainability. 2020;22.

Copyright

© 2020 Obi et al.This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Published By Indian Society for Education and Environment (iSee).