Optimization Online


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

Gonzalo Lera-Romero(gleraromero***at***dc.uba.ar)
Juan Jose Miranda Bront(jmiranda***at***utdt.edu)

Abstract: In this paper we study the time-dependent profitable tour problem with resource con-straints (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. In this paper, 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 three 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: Profitable Tour Problem; Time-Dependent Travel Times; Integer Programming; Branch and Cut

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 02/19/2019
Entry Accepted: 02/19/2019
Entry Last Modified: 02/19/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society