An efficient column‐generation‐based algorithm for solving a pickup‐and‐delivery problem

We introduce a new variation of the pickup‐and‐delivery problem. Current methods for solving this problem rely on column‐generation subroutines embedded in a branch‐and‐bound tree. Yet, when applied to our problem, these techniques suffer from significant combinatorial explosion in the number of routes generated by the column‐generation subroutine and the number of nodes explored in the branch‐and‐bound tree. In this paper, by exploiting the problem structure, we develop a specialized column‐generation subroutine that reduces the combinatorial explosion significantly leading to a more efficient procedure to solve the problem.