Séminaire conjoint CRT-Chaire de recherche du Canada en distributique

TITRE: Creating Lasso-solutions for the Pickup and Delivery Problem using Tabu Search

CONFÉRENCIER: Arild Hoff, Department of Informatics, Molde University College, Norway

DATE et ENDROIT: Jeudi 9 décembre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE: Gilbert Laporte (343-6143)

RÉSUMÉ: We consider the Pickup and Delivery Problem where the same costumers might require both deliveries of goods and pickup of other goods. In real life problems this is the case for instance for breweries when they deliver bottles of beer or mineral water and collect empty bottles from the same customers on the same tour. This problem could be defined for just one vehicle which then makes it a Traveling Salesman Problem with Pickup and Delivery (TSPPD), or for several vehicles making it the more general Vehicle Routing Problem with Pickup and Delivery (VRPPD). For these situations it is possible to relax the customary practice of always picking up when delivering, and postpone the pick-up until the vehicle has sufficient free space. In the case of breweries, these solutions will first only deliver bottles until the vehicle is partly unloaded, then do both delivery and pickup at the remaining customers and at last pick up the empty bottles from the first visited customers. These customers are revisited, but in reverse order, ththus giving rise to lasso shaped solutions. To find such solutions, we use the metaheuristic Tabu Search on some well known TSPPD/VRPPD-problems, and compare them to the standard types of solutions on the same problems.