A Transgenetic Algorithm for the Bi-objective Traveling Purchaser Problem


Abstract

This work proposes an algorithm based on Computational Transgenetic (CT) metaphor to deal with the bi-objective traveling purchaser problem (2TPP). The 2TPP consists in determining a route through a subset of markets to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. This problem contains a finite set of solutions and belongs to the field of the bi-objective combinatorial optimization. CT is an evolutionary algorithm based on the endosymbiotic evolution and others interactions of the intracellular flow. In the proposed approach, named bi-objective Transgenetic Algorithm (2TA), a pair of transponson agents (one for each objective) and a plasmid agent associated with the cost are applied. The method is validated in 175 uncapacitated instances of the TPPLib benchmark. In these instances the multi-objective version (2TA) is compared to a scalarized version (1TA). The results demonstrate the superiority of 2TA and encourage further research.