A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints

Gonzalo Lera-Romero and Juan José Miranda-Bront
Authors registered in the RePEc Author Service: Juan José Miranda Bront ()

European Journal of Operational Research, 2021, vol. 289, issue 3, 879-896

Abstract: In this paper we study the time-dependent profitable tour problem with resource constraints (TDPTPRC), a generalization of the profitable tour problem (PTP) which includes variable travel times to account for road congestion. In this problem, the set of customers to be served is not given and must be determined based on the profit collected when visited, keeping a balance with the total travel time. We propose a mixed integer linear programming (MILP) formulation that exploits the travel time function to reduce the size of a standard formulation from the literature. We derive four new families of valid inequalities and study the connections among them, as well as their associated separation problems. We develop a tailored Branch and Cut (BC) algorithm including these new families in addition to some well known valid inequalities from related problems. Computational results on four different problems, with alternative resources and objectives, show that the approach is flexible and effective. The algorithm achieves significant reductions in the computing times on benchmark instances from the related literature, and outperforms a recent method proposed for the time-dependent traveling salesman problem with time windows.

Keywords: Traveling salesman; Profitable tour problem; Time-dependent travel times; Integer programming; Branch and cut (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719305788
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:3:p:879-896

DOI: 10.1016/j.ejor.2019.07.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().