doctoralThesis
Problema do caixeiro viajante com coleta opcional de bônus, tempo de coleta e passageiros
Fecha
2019-12-13Registro en:
LOPES FILHO, José Gomes. Problema do caixeiro viajante com coleta opcional de bônus, tempo de coleta e passageiros. 2019. 94f. Tese (Doutorado em Ciência da Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2019.
Autor
Lopes Filho, José Gomes
Resumen
This study introduces a variant of the Bonus Collecting Traveling Salesman Problem,
named Traveling Salesman Problem with Optional Bonus Collection, Pickup Time and
Passengers (PCVP-BoTc). It is a vehicle routing problem variant which combines the
selective collection of bonuses with ridesharing. The objective is to optimize the revenue
of the driver, which selectively de nes which delivery or collection tasks to perform along
the route. The economic e ect of the collection is modeled by a bonus. The model can be
applied to the solution of hybrid routing systems with route tasks and solidary transport.
The driver, while performing the selected tasks, can give rides to persons who share route
costs with him. Passengers are protected by restrictions concerning the maximum value
they agree to pay for a ride and maximum travel duration. The activity of collecting
the bonus in each locality demands a speci c amount of time, a ects the route duration,
and is interconnected with the embarkment of passengers. Four nonlinear mathematical
formulations, two quadratic, are presented for the problem. The quadratic formulations
were validated by a computational experiment using a solver. Seven heuristic algorithms
have been proposed; six of them are hybrid metaheuristics. We tested the mathematical
formulation implementations for 48 instances and the heuristic algorithms for 96.