A memetic algorithm for the prize-collecting Traveling Car Renter Problem

Author

da Silva Menezes, Matheus ; Goldbarg, Marco C. ; Goldbarg, Elizabeth F. G.

Author_Institution

Univ. Fed. Rural do Semi-Arido - UFERSA Angicos, Mossoro, Brazil

fYear

2014

fDate

6-11 July 2014

Firstpage

3258

Lastpage

3265

Abstract

This paper introduces a new variant of the Traveling Car Renter Problem, named Prize-collecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The bonus represents a degree of satisfaction to visit the vertex. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, i.e. reaching a pre-specified satisfaction, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-four instances. A memetic algorithm is proposed and its performance is evaluated in comparison to the results obtained with the solver.

Keywords

computational complexity; cost reduction; evolutionary computation; transportation; travelling salesman problems; NP-hard problem; PCTSP; mathematical formulation; memetic algorithm; pCaRS; prize-collecting traveling car renter problem; prize-collecting traveling salesman problem; tour cost minimization; Algorithm design and analysis; Biological cells; Cities and towns; Memetics; Sociology; Statistics; Vehicles;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation (CEC), 2014 IEEE Congress on

Conference_Location

Beijing

Print_ISBN

978-1-4799-6626-4

Type

conf

DOI

10.1109/CEC.2014.6900337

Filename

6900337