  This paper addresses a new variant of the multi-trip single vehicle routing
problem where the nodes are related to each other through AND-type precedence
constraints. The problem aims at determining a sequence of trips to visit all
the nodes respecting every precedence constraint within and among the routes so
to minimize the total traveling cost. Our motivation comes from routing
problems where a node may have a set of predecessors (not just single one
proposed in the dial-a-ride or pickup and delivery problems) resulting in a set
of pairwise relations that specify which customers need to be visited before
which other ones. We develop three Mixed Integer Programming (MIP) models to
formulate the problem. The models are experimentally compared to determine the
best one. Moreover, a solution approach based on the Logic-Based Benders
Decomposition (LBBD) algorithm is developed which allows to decompose the
original problem into an assignment master problem and independent sequencing
subproblems. A new valid optimality cut is devised to achieve faster
convergence. The cut performance is experimentally investigated by comparing
with a recently proposed one in the literature. We further relax the algorithm
to find the sub-optimal solution and demonstrate its efficiency. Extensive
computational experiments are conducted to assess the proposed algorithms in
terms of solution quality and CPU time.
