In this paper, we model and solve the one-to-one pickup and delivery traveling salesman problem with handling costs (PDTSPH). We consider a rear-loaded vehicle with a single compartment operated in a last-in-first-out (LIFO) fashion. The LIFO stack implies that when the vehicle arrives at a pickup location, the item is positioned on top of the stack. An item can be delivered without handling when it is on top of the stack, otherwise handling is needed and is penalized. The item sequence remains the same after the handling operations. The objective is to minimize a weighted sum of the travel distance and penalty costs. This problem is a generalization of the pickup and delivery traveling salesman problem (PDTSP) and the PDTSP with LIFO (PDTSPL). Setting the penalty of the handling operations sufficiently small, the problem reduces to the PDTSP, whereas a sufficiently large penalty reduces the problem to the PDTSPL. We propose an adaptive large neighborhood search metaheuristic to solve the PDTSPH and provide computational results on known instances for the PDTSPL. We show the impact of the value of the penalty for the handling operations in different settings. We indicate the need to include handling operations in the generation of routes, and show that relaxing the LIFO policy can be valuable.

Entrée gratuite.

Bienvenue à tous.