Caixeiro viajante com coleta de prêmios e passageiros

Abstract

The Prize Collect Traveling Salesman Problem with Ridesharing is a model that merge elements of the classic problem PCTSP with ridesharing. The costs of the driver journey are reduced through the apportionment of expenses due to the sharing of accents in the vehicle used in the task of collecting prizes. The tasks in the route are selected according to the routing model with collection of prizes, therefore considering penalties for the non-attendance of existing task and additionally determining the fulfillment of a minimum demand of tasks. The demand for collaborative transport is protected by restrictions that ensure passengers are transported to their destination. Likewise, the apportionment costs will be less than or equal to the tariff limits established by the passengers. The present work presents the mathematical formulation for the problem, validates the model in an exact solution process and examines the performance of two algorithms that execute construction steps with exact criteria and six with heuristic criteria. Accurate step-by-step algorithms aim to create anchoring results to evaluate algorithm performance with heuristic decisions. Three instance groups are also proposed for the problem in order to allow future experimentation of new algorithms. Finally, it is concluded that the algorithms of heuristic steps achieve promising performance for the problem examined.