  In logistic applications that require the pickup and delivery of items, route
optimization problems can be modeled as precedence constrained traveling
salesperson problems. The combinatorial nature of this problem restricts the
application of exact algorithms to small instances, and heuristics are largely
preferred for tractability. However, due to precedence constraints that
restrict the order in which locations can be visited, heuristics outside of the
nearest neighbor algorithm have been neglected in literature. While the convex
hull cheapest insertion heuristic is known to produce good solutions in the
absence of precedence constraints, i.e., when locations can be visited in any
order, it has not been adapted for pick-up and delivery considerations. This
paper presents an adapted convex hull cheapest insertion heuristic that
accounts for precedence constraints and compares its solutions with the nearest
neighbor heuristic using the TSPLIB benchmark data set. The proposed algorithm
is particularly suited to cases where pickups are located in the periphery and
deliveries are centrally located, outperforming the Nearest Neighbor algorithm
in every examined instance.
