In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenet...
详细信息
In this paper an evolutionary algorithm is presented for the Traveling Purchaser Problem, an important variation of the Traveling Salesman Problem. The evolutionary approach proposed in this paper is called transgenetic algorithm. It is inspired on two significant evolutionary driving forces: horizontal gene transfer and endosymbiosis. The performance of the algorithm proposed for the investigated problem is compared with other recent works presented in the literature. Computational experiments show that the proposed approach is very effective for the investigated problem with 17 and 9 new best solutions reported for capacitated and uncapacitated instances, respectively. (C) 2008 Elsevier B.V. All rights reserved.
The Traveling Car Renter is a new problem and constitutes a generalization of the Traveling Salesman. Several applications arise from it, mainly in the scheduling optimization of rental cars and in other problems conc...
详细信息
The Traveling Car Renter is a new problem and constitutes a generalization of the Traveling Salesman. Several applications arise from it, mainly in the scheduling optimization of rental cars and in other problems concerning transport systems. In this paper, an integer quadratic programming model is presented for the Traveling Car Renter. It is linearized and implemented on a solver providing optimal solutions to a set of eighteen small instances. Large instances are tackled with a transgenetic algorithm proposed here. A computational experiment is reported on sixty instances and the proposed algorithm is compared to a memetic algorithm presented previously. The computational experiment aimed at focusing on the differences of performance between the two heuristic algorithms due to the search strategy used by each of them. Therefore, the implementation of both methods shared several elements. The results show that the transgenetic algorithm presents the best performance, indicating that its cooperative evolutionary process was more effective on the investigated problem than the competitive scheme of the memetic algorithm. (C) 2013 Published by Elsevier Ltd.
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 ...
详细信息
ISBN:
(纸本)9781424481262
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.
暂无评论