  The convex hull cheapest insertion heuristic is a well-known method that
efficiently generates good solutions to the Traveling Salesperson Problem.
However, this heuristic has not been adapted to account for precedence
constraints that restrict the order in which locations can be visited. Such
constraints result in the precedence constrained traveling salesperson problem
or the sequential ordering problem, which are commonly encountered in
applications where items have to be picked up before they are delivered. In
this paper, we present an adapted version of this heuristic that accounts for
precedence constraints in the problem definition. This algorithm is compared
with the widely used Nearest Neighbor heuristic on the TSPLIB benchmark data
with added precedence constraints. It is seen that the proposed algorithm is
particularly well suited to cases where delivery nodes are centrally
positioned, with pickup nodes located in the periphery, outperforming the
Nearest Neighbor algorithm in 97\% of the examined instances.
