RESEARCH
Areas of interest
- Combinatorial optimization
- Mathematical Programming
- Graph algorithms
- Metaheuristics
- Vehicle routing problems
- Computer vision
Projects & Research
Traveling Car Renter Salesman Problem
The Car Renter Salesman Problem (CaRS) is a new variant of the classic Traveling Salesman Problem where the salesman’s tour can be decomposed into contiguous paths that are travelled by different rented cars. The goal is to determine the minimum cost Hamiltonian cycle, considering the cost of the route added to the cost of penalties paid for exchanging vehicles during the route. The penalty is due to fees paid to return the rented cars to their bases.
The Car Renter Salesman Problem (CaRS) is a new variant of the classic Traveling Salesman Problem where the salesman’s tour can be decomposed into contiguous paths that are travelled by different rented cars. The goal is to determine the minimum cost Hamiltonian cycle, considering the cost of the route added to the cost of penalties paid for exchanging vehicles during the route. The penalty is due to fees paid to return the rented cars to their bases.
Research in metaheuristics for combinatorial optimization problems has lately experienced a noteworthy shift towards the hybridization of metaheuristics with other techniques for optimization. At the same time, the focus of research has changed from being rather algorithm-oriented to being more problem-oriented. Nowadays the focus is on solving a problem at hand in the best way possible, rather than promoting a certain metaheuristic. This has led to an enormously fruitful cross-fertilization of different areas of optimization, algorithmics, mathematical modeling, operations research, statistics, simulation, and other fields. This cross-fertilization has resulted in a multitude of powerful hybrid algorithms that were obtained by combining components or concepts from different optimization techniques. Hereby, hybridization is not restricted to different variants of metaheuristics but includes, for example, the combination of mathematical programming, dynamic programming, constraint programming or statistical modeling with
metaheuristics.
This
paper presents a corrected formulation to the mixed integer
quadratically constrained programming model of the Traveling Car Renter
Salesman Problem (CaRS), proposed by da Silva and Ochi (2016, An
efficient hybrid algorithm for the Traveling Car Renter Problem. Expert
Systems with Applications, 64, 132-140). In the CaRS, various vehicle
types are available for rent in the cities, each one has its own rental
cost, when a car is returned to the city where it was rented an
additional tax must be charged, the objective is construct a Hamiltonian
circuit that minimize the total cost of the circuit plus the return
cost of cars. We highlight the errors in the original formulation,
propose corrections to the formulation, and provide an analytical
validation of the corrections.
This
paper presents a hybrid metaheuristic approaches to deal with CaRS:
Large neighborhood Dynasearch. This hybrid metaheuristic uses dynamic
programming as a neighborhood exploration strategy inside Large
neighborhood search. A computational experiment applies the proposed
approach to the Car Renter Salesman Problem. The results are compared to
the best known algorithm in literature for non-Euclidean instances of
this problem.
In
this article, is studied a possibility of solving the CaRS, which
ranges among NP-hard problems, and offer a theoretical overview of some
methods used for solving this problem. We discuss the Population-Based
Iterated Local Search, where iterated local search is extended from
working on a single solution to working on a population which is
managed in the style of evolution strategies. The quality of the
solution is compared with the optimal solution.
We discuss the Ant System (AS), which belongs to the group of evolutionary techniques and presents the approach used in the application of AS to the CaRS.
Leave a Comment