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.