Calendrier

GERAD Seminar: An ALNS for the one-to-one pickup and delivery TSP with handling costs

GERAD Seminar:  An ALNS for the one-to-one pickup and delivery TSP with handling costs

Title: An ALNS for the one-to-one pickup and delivery TSP with handling costs

Speaker:  Marjolein Veenstra, University of Groningen, Netherlands

Abstract:

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.

Date

Wednesday January 28, 2015
Starts at 13:45

Price

gratuit

Contact

514-340-6053 x 6991

Place

Université de Montréal - Pavillon André-Aisenstadt
2920, chemin de la Tour
Montréal
QC
Canada
H3T 1N8
514 343-6111
4488

Categories