Traveling Salesman Problem with Optional Bonus Collection, Pickup Time and Passengers

José Gomes Lopes Filho, Marco Cesar Goldbarg, Elizabeth Ferreira Gouvêa Goldbarg, Vinícius Araújo Petch


This study introduces a variant of the Traveling Salesman Problem, named Traveling Salesman Problem with Optional Bonus Collection, Pickup Time and Passengers (PCVP-BoTc). It is a variant that incorporates elements of the Prize Collecting Traveling Salesman Problem and Ridesharing into the PCV. The objective is to optimize the revenue of the driver, which selectively defines which delivery or collection tasks to perform along the route. The economic effect 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 specific amount of time, affects the route duration, and is interconnected with the embarkment of passengers. Two mathematical formulations are presented for the problem and validated by a computational experiment using a solver. We propose four heuristic algorithms; three of them are hybrid metaheuristics. We tested the mathematical formulation implementations for 24 instances and the heuristic algorithms for 48.


Travelling salesman Problem;Travelling salesman Problem with profits; Ridesharing

Full Text:



AGATZ, N., ERERA, A., SAVELSBERGH, M., AND WANG, X. Optimization for dynamic ride-sharing: A review. European Journal of Operational Research 223, 2 (2012), 295–303.

ALONSO-MORA, J., SAMARANAYAKE, S., WALLAR, A., FRAZZOLI, E., AND RUS, D. On-demand high- capacity ride-sharing via dynamic trip-vehicle assign- ment. Proceedings of the National Academy of Sciences 114, 3 (2017), 462–467.

ARCHETTI, C., FEILLET, D., HERTZ, A., AND SPER- ANZA, M. G. The capacitated team orienteering and profitable tour problems. Journal of the Operational Research Society 60, 6 (2009), 831–842.

ARCHETTI, C., SAVELSBERGH, M., AND SPERANZA, M. G. The vehicle routing problem with occasional drivers. European Journal of Operational Research 254, 2 (2016), 472–480.

ARSLAN, A. M., AGATZ, N., KROON, L., AND ZUID- WIJK, R. Crowdsourced delivery—a dynamic pickup and delivery problem with ad hoc drivers. Transporta- tion Science 53, 1 (2018), 222–235.

BALAS, E. The prize collecting traveling salesman problem. Networks 19, 6 (1989), 621–636.

BERBEGLIA, G., CORDEAU, J.-F., AND LAPORTE, G. Dynamic pickup and delivery problems. European journal of operational research 202, 1 (2010), 8–15.

CALHEIROS, Z. S. A. O problema do caixeiro viajante com passageiros. Master’s thesis, Brasil, 2017.

CLAUS, A. A new formulation for the travelling sales- man problem. SIAM Journal on Algebraic Discrete Methods 5, 1 (1984), 21–25.

CORDEAU, J.-F., AND LAPORTE, G. The dial-a-ride problem: models and algorithms. Annals of operations research 153, 1 (2007), 29–46.

DAHLE, L., ANDERSSON, H., CHRISTIANSEN, M., AND SPERANZA, M. G. The pickup and delivery prob- lem with time windows and occasional drivers. Com- puters & Operations Research 109 (2019), 122–133.

DIJKSTRA, E. W. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269– 271.

DORIGO, M., AND DI CARO, G. Ant colony optimiza- tion: a new meta-heuristic. In Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406) (1999), vol. 2, IEEE, pp. 1470–1477.

FAGNANT, D. J., AND KOCKELMAN, K. M. The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transportation Research Part C: Emerging Technologies 40(2014), 1–13.

FARHAN, J., AND CHEN, T. D. Impact of ridesharing on operational efficiency of shared autonomous electric vehicle fleet. Transportation Research Part C: Emerg- ing Technologies 93 (2018), 310–321.

FEILLET, D., DEJAX, P., AND GENDREAU, M. Trav- eling salesman problems with profits. Transportation science 39, 2 (2005), 188–205.

FEO, T. A., AND RESENDE, M. G. Greedy random- ized adaptive search

procedures. Journal of global optimization 6, 2 (1995), 109–133.

FRIEDMAN, M. The use of ranks to avoid the assump- tion of normality implicit in

the analysis of variance. Journal of the american statistical association 32, 200 (1937), 675–701.

GAVISH, B., AND GRAVES, S. C. The travelling sales- man problem and related problems.

GENDREAU, M., GUERTIN, F., POTVIN, J.-Y., AND TAILLARD, E. Parallel tabu search for real-time vehicle routing and dispatching. Transportation science 33, 4 (1999), 381–390.

GOLDBARG, M. C., AND LUNA, H. P. L. Otimizac ̧a ̃o combinato ́ria e programac ̧a ̃o linear: modelos e algorit- mos. Elsevier, Rio de Janeiro, 2005.

GU, Q.-P., LIANG, J. L., AND ZHANG, G. Algo- rithmic analysis for ridesharing of personal vehicles. Theoretical Computer Science 749 (2018), 36–46.

GUROBI, O. Gurobi optimizer reference manual version 6.5. (2016).

GUTIN, G., AND PUNNEN, A. P. The traveling sales- man problem and its variations, vol. 12. Springer Sci- ence & Business Media, 2006.

HANDOKO, S. D., CHUIN, L. H., GUPTA, A., SOON, O. Y., KIM, H. C., AND SIEW, T. P. Solving multi- vehicle profitable tour problem via knowledge adoption in evolutionary bi-level programming. In 2015 IEEE Congress on Evolutionary Computation (CEC) (2015), IEEE, pp. 2713–2720.

HANSEN, P., AND MLADENOVIC ́ , N. Variable neigh- borhood search: Principles and applications. European journal of operational research 130, 3 (2001), 449–467.

HELSGAUN, K. General k-opt submoves for the lin– kernighan tsp heuristic. Mathematical Programming Computation 1, 2-3 (2009), 119–163.

HO, S. C., SZETO, W., KUO, Y.-H., LEUNG, J. M., PETERING, M., AND TOU, T. W. A survey of dial-a- ride problems: Literature review and recent develop- ments. Transportation Research Part B: Methodologi- cal 111 (2018), 395–421.

JABERI, N., AND RAFEH, R. On the linearization of zinc models. Journal of Advances in Computer Re- search 5, 4 (2014), 1–8.

JACOBSON, S. H., AND KING, D. M. Fuel saving and ridesharing in the us: Motivations, limitations, and op- portunities. Transportation Research Part D: Transport and Environment 14, 1 (2009), 14–21.

JOZEFOWIEZ, N., GLOVER, F., AND LAGUNA, M. Multi-objective meta-heuristics for the traveling sales- man problem with profits. Journal of Mathematical Modelling and Algorithms 7, 2 (2008), 177–195.

LAHYANI, R., KHEMAKHEM, M., AND SEMET, F. Heuristics for rich profitable tour problems. In 2013 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO) (2013), IEEE, pp. 1–3.

LI, B., KRUSHINSKY, D., REIJERS, H. A., AND VAN WOENSEL, T. The share-a-ride problem: People and parcels sharing taxis. European Journal of Opera- tional Research 238, 1 (2014), 31–40.

LI, Z., HONG, Y., AND ZHANG, Z. Do ride-sharing services affect traffic congestion? an empirical study of uber entry. Soc. Sci. Res. Netw 2002 (2016), 1–29.

LIN, C. A vehicle routing problem with pickup and de- livery time windows, and coordination of transportable resources. Computers & Operations Research 38, 11 (2011), 1596–1609.

LO ́ PEZ-IBA ́ N ̃ EZ, M., DUBOIS-LACOSTE, J., CA ́ CERES, L. P., BIRATTARI, M., AND STU ̈ TZLE, T. The irace package: Iterated racing for automatic algo- rithm configuration. Operations Research Perspectives 3 (2016), 43–58.

MA, S., ZHENG, Y., AND WOLFSON, O. Real- time city-scale taxi ridesharing. IEEE Transactions on Knowledge and Data Engineering 27, 7 (2014), 1782– 1795.

PARRAGH, S. N., DOERNER, K. F., AND HARTL, R. F. A survey on pickup and delivery problems - part i: Transportation between customers and depot. Journal fu ̈r Betriebswirtschaft 58, 1 (2008), 21–51.

PARRAGH, S. N., DOERNER, K. F., AND HARTL, R. F. A survey on pickup and delivery problems - part ii: Transportation between pickup and delivery locations. Journal fu ̈r Betriebswirtschaft 58, 2 (2008), 81–117.

PILLAC, V., GENDREAU, M., GUE ́RET, C., AND MEDAGLIA, A. L. A review of dynamic vehicle routing problems. European Journal of Operational Research 225, 1 (2013), 1–11.

PSARAFTIS, H. N. A dynamic programming solu- tion to the single vehicle many-to-many immediate re- quest dial-a-ride problem. Transportation Science 14, 2 (1980), 130–154.

SIEGEL, S., AND CASTELLAN JR, N. J. Nonparamet- ric statistics for the behavioral sciences, 2 ed. Mcgraw- Hill Book Company, New York, NY, 1988.

SUN, P., VEELENTURF, L. P., DABIA, S., AND VAN WOENSEL, T. The time-dependent capacitated profitable tour problem with time windows and prece- dence constraints. European Journal of Operational Research 264, 3 (2018), 1058–1073.

YU, B., MA, Y., XUE, M., TANG, B., WANG, B., YAN, J., AND WEI, Y.-M. Environmental benefits from ridesharing: A case of beijing. Applied energy 191 (2017), 141–152.

ZHANG, M., WANG, J., AND LIU, H. The probabilis- tic profitable tour problem. International Journal of Enterprise Information Systems (IJEIS) 13, 3 (2017), 51–64.


Copyright (c) 2020 José Gomes Lopes Filho, Marco Cesar Goldbarg, Elizabeth Ferreira Gouvêa Goldbarg, Vinícius Araújo Petch

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.