Problema do caixeiro viajante com coleta opcional de bônus, tempo de coleta e passageiros

Abstract

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.