Prize Collecting Traveling Salesman Problem with Ridesharing
DOI:
https://doi.org/10.22456/2175-2745.94082Keywords:
Travelling salesman Problem, Ridesharing, MetaheuristicAbstract
The Prize Collecting Traveling Salesman Problem with Ridesharing is a model that joins elements from the Prize Collecting Traveling Salesman and the collaborative transport. The salesman is the driver of a capacitated vehicle and uses a ridesharing system to minimize travel costs. There are a penalty and a bonus associated with each vertex of a graph, G, that represents the problem. There is also a cost associated with each edge of G. The salesman must choose a subset of vertices to be visited so that the total bonus collection is at least a given a parameter. The length of the tour plus the sum of penalties of all vertices not visited is as small as possible. There is a set of persons demanding rides. The ride request consists of a pickup and a drop off location, a maximum travel duration, and the maximum amount the person agrees to pay. The driver shares the cost associated with each arc in the tour with the passengers in the vehicle. Constraints from ride requests, as well as the capacity of the car, must be satisfied. We present a mathematical formulation for the problem investigated in this study and solve it in an optimization tool. We also present three heuristics that hybridize exact and heuristic methods. These algorithms use a decomposition strategy that other enriched vehicle routing problems can utilize.
Downloads
References
BALAS, Egon. The prize collecting traveling salesman problem. Networks, v. 19, n. 6, p. 621-636, 1989.
NOURINEJAD, Mehdi. Dynamic optimization models for ridesharing and carsharing. Tese de Doutorado. Department of Civil Engineering, University of Toronto. 2014.
GRIBKOVSKAIA, Irina; LAPORTE, Gilbert; SHYSHOU, Aliaksandr. The single vehicle routing problem with deliveries and selective pickups. Computers & Operations Research, v. 35, n. 9, p. 2908-2924, 2008.
CALHEIROS, Z. S. A. O problema do caixeiro viajante com passageiros. Dissertação de Mestrado, Universidade Federal do Rio Grande do Norte, Natal, Brasil. 2017.
BASTOS, R. E. M.; GOLDBARG, M. C.; GOLDBARG, E. F. G.; O problema do caixeiro viajante com passageiros e lotação. SBPO, Anais, 2016.
SABRY, G. A.; GOLDBARG, M. C.; GOLDBARG, Elizabeth Ferreira Gouvêa. Problema do Caixeiro Viajante Alugador com Passageiros: Uma Abordagem Algorítmica. In: XVIII CLAIO, the Latin-Iberoamerican Conference on Operations Research, Santiago. In: Proceedings of the CLAIO. Santiago: Ediciones UC. v. 1. p. 764-771. 2016.
GOLDBARG, Marco C. et al. A transgenetic algorithm applied to the traveling car renter problem. Expert Systems with Applications, v. 40, n. 16, p. 6298-6310, 2013.
SILVA, J. G. d. S. Algoritmos de solução para o problema do caixeiro viajante com passageiros e quota. Dissertação de Mestrado, Universidade Federal do Rio Grande do Norte, Natal, Brasil. 2017.
MILLER, Clair E.; TUCKER, Albert W.; ZEMLIN, Richard A. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), v. 7, n. 4, p. 326-329, 1960.
FEO, Thomas A.; RESENDE, Mauricio GC. A probabilistic heuristic for a computationally difficult set covering problem. Operations research letters, v. 8, n. 2, p. 67-71, 1989.
LIPOWSKI, Adam; LIPOWSKA, Dorota. Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and its Applications, v. 391, n. 6, p. 2193-2196, 2012.
HELSGAUN, Keld. An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, v. 126, n. 1, p. 106-130, 2000.
MLADENOVIĆ, Nenad; HANSEN, Pierre. Variable neighborhood search. Computers & operations research, v. 24, n. 11, p. 1097-1100, 1997.
Gurobi Optimization, I. Gurobi optimizer reference manual. URL http://www.gurobi.com. 2019.
LÓPEZ-IBÁNEZ, Manuel et al. The irace package: Iterated racing for automatic algorithm configuration. IRIDIA, Universite Libre de Bruxelles, Brussels, Belgium, Tech. Rep. TR/IRIDIA/2011-004, 2011.
CONOVER, W. J. Statistics of the Kolmogorov-Smirnov type. Practical nonparametric statistics, p. 428-473, 1999.
FRIEDMAN, Milton. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the american statistical association, v. 32, n. 200, p. 675-701, 1937.
