Quota traveling car renter problem: Model and evolutionary algorithm

The quota traveling car renter problem is the quota variant of the traveling car renter problem. A graph is given where a bonus is associated with each vertex. The bonus is collected at every visited vertex. Several cars are available to travel the edges of the graph, each of which associates weight...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 2016-11, Vol.367-368, p.232-245
Main Authors: Goldbarg, Marco C., Goldbarg, Elizabeth F.G., Menezes, Matheus da S., Luna, Henrique P.L.
Format: Article
Language:English
Subjects:
Cars
Combinatorial optimization
Cost engineering
Evolutionary algorithms
Evolutionary computation
Graph theory
Graphs
Integer programming
Optimization
Quota traveling car renter problem
Quotas
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The quota traveling car renter problem is the quota variant of the traveling car renter problem. A graph is given where a bonus is associated with each vertex. The bonus is collected at every visited vertex. Several cars are available to travel the edges of the graph, each of which associates weights with the edges. The problem involves finding a cycle on a subset of vertices such that a predefined minimum sum of bonuses is obtained at least. The objective is to minimize the cost of the tour using the available cars. In this study, we propose an integer programming model for the problem, which is solved, and we present optimal solutions for 24 instances. We propose an evolutionary algorithm with a plasmid operator, which we compare with a memetic algorithm. We also present the results obtained based on computational experiments with 72 instances.
ISSN:0020-0255
1872-6291
DOI:10.1016/j.ins.2016.05.027