A Noble Genetic Algorithm to Solve a Solid Green Traveling Purchaser Problem with Uncertain Cost Parameters

Abstract

The traveling purchaser problem (TPP) is a notable generalization of the traveling salesman problem (TSP) which involves selecting a subset of markets at a minimum traveling cost such that the demand for each product is satisfied. A solid green traveling purchaser problem (SGTPP) is a TPP in which, at each market, some conveyances are available to travel to another market with minimum cost considering the environmental impact caused by carbon emission. In this paper, we formulate an SGTPP with travel cost between each pair of markets and purchase price of the products as uncertain variables. Using uncertainty theory, an expected value model is formulated and then transformed into the corresponding deterministic form. Finally, a noble genetic algorithm (nGA) is designed to solve the proposed model. The algorithm is called noble because it adopts a crossover of the combination of a probabilistic selection of three parents, according to real-life In Vitro Fertilization (IVF) techniques. Computational results reveal that our proposal is favorably compared to previous algorithms in the existing literature.

KEYWORDS AND PHRASES:

• In vitro fertilization crossover
• noble genetic algorithm
• solid traveling purchaser problem
• uncertainty theory

Acknowledgements

The authors would like to thank the reviewers and Editor for their constructive comments and suggestions and especially appreciated the Editor-in-Chief for their valuable comments, which improved the quality and presentation of this article. We are grateful to Prof. Baoding Liu, Dept. of Mathematical Sciences, Tsinghua University, Beijing, China for his valuable comments, suggestions, and encouragement to writing this article. We are also thankful to Madhushree Das, Research Scholar, Dept. of Computer Science and Application, Prabhat Kumar College, Contai, West Bengal, India for her support.

Additional information

Funding

This research was supported by Department of Science and Technology and Bio-Technology, West Bengal by Grant Number 1001 (Sanc.)/ST/P/S&T/16G-13/2018 dated 05.08.2019.