CaRS - Car Renter Salesman

Paulo Henrique Asconavieta da Silva, Ph.D.

CaRS is a variant of the Traveling Salesman Problem (TSP) in which the salesman travels in rented cars. Given a graph G = (V,E) and a set of cars C, a weight corresponding to each car c∈C, is associated with each edge e∈E. Additionally, there is a square matrix, Γ = [γ(c,i,j)], of order n = |V|, in which each element γ(c,i,j) corresponds to the cost of renting car c in city i and return it in city j, i,j∈V, i ≠ j. The objective is to make a Hamiltonian tour in G with the minimum total cost, where the total cost is given by the sum of the weights associated to each edge of the tour plus the sum of the fees associated to matrix Γ.

Instances
Instances

Papers

1. M. C. Goldbarg, E. F. Goldbarg, P. H. Asconavieta, M. da S. Menezes, H. P. Luna, A transgenetic algorithm applied to the traveling car renter problem, Expert Systems with Applications 40 (16) (2013) 6298 - 6310.
2. M. C. Goldbarg, P. H. Asconavieta, E. F. G. Goldbarg, Memetic algorithm for the traveling car renter problem: an experimental investigation, Memetic Computing 4 (2) (2012) 89{108. doi:10.1007/s12293-011-0070-y.
3. GOLDBARG, Marco Cesar ; Asconavieta, P. ; GOLDBARG, E. F. G. . A Memetic Algorithm for the Car Renter Problem. In: Eisuke Kita. (Org.). Evolutionary Algorithms. Rijeka: Intech, 2011, v. 1, p. 309-326.
4. GOLDBARG, Marco Cesar ; Asconavieta, P. ; GOLDBARG, E. F. G. . Algoritmos Evolucionários na Solução do Problema do Caixeiro Alugador. In: Heitor Silvério Lopes, Ricardo Hiroshi Caldeira Takahashi. (Org.). Computação Evolucionária em Problemas de Engenharia. Curitiba: Omnipax, 2011, v. , p. 301-330.
5. Asconavieta, P. ; GOLDBARG, Marco Cesar ; GOLDBARG, E. F. G. . Algoritmo em Colônia de Formigas com Multiferomônios para a Solução do Problema do Caixeiro Alugador. In: XLIV Simpósio Brasileiro de Pesquisa Operacional, 2012, Rio de Janeiro. Anais do XLIV Simpósio Brasileiro de Pesquisa Operacional. Niterói: ILTC, 2012.
6. Silva, P. H. A. ; GOLDBARG, Marco César ; GOLDBARG, E. F. G. . Evolutionary Algorithm for the Car Renter Salesman. In: IEEE CEC Congress on Evolutionary Computation, 2011, New Orleans. Proceedings of IEEE CEC 2011 Congress on Evolutionary Computation. New Orleans: IEEE, 2011. v. 1. p. 593-600.

Click here to back to the previous page.

qCaRS - Quota Traveling Car Renter Problem

Matheus da Silva Menezes, Ph.D.

qCaRS is a CaRS variant in which a quota is associated to each vertex. The objective is to determine a cycle that visits as many vertices as necessary to collect a pre-defined sum of quotasand minimizing the total cost of the tour.

Instances
Instances

Papers

1. Menezes, M. S. ; GOLDBARG, Marco César ; GOLDBARG, ELIZABETH F. G. . A memetic algorithm for the prize-collecting traveling car renter problem. In: IEEE CEC 2014 Congress on Evolutionary Computation, 2014, Pequim. Proceedings of IEEE CEC 2014 Congress on Evolutionary Computation, 2014. v. 1. p. 3258-3265.
2. GOLDBARG, Marco César ; GOLDBARG, E.F.G. ; Menezes, M. S. . Um Algoritmo Memético para o Problema do Caixeiro Alugador com Coleta de Bônus. In: XLV SBPO Simpósio Brasileiro de Pesquisa Operacional, 2013, Natal. Anais do XLV SBPO Simpósio Brasileiro de Pesquisa Operacional. Niterói: ILTC, 2013. p. 1-8.

Click here to back to the previous page.

CaRSP - Traveling Car Renter with Passengers

Gustavo de Araujo Sabry, M.Sc.

CaRSP is a CaRS variant where the salesman is allowed to share trip expenses with passengers. There is a list of potential passengers demanding rides from different cities to several destinations. Each one has a budget, i.e., a maximum fee that he/she agrees to pay. The objective is to find a route, a sequence of rented cars, and a set of passengers that minimize the salesman’s travel costs.

Instances
Instances

Click here to back to the previous page.