Heuristics for a pick-up and delivery problem with time windows
| Autor: | Albert Lopez, Adria |
|---|---|
| Přispěvatelé: | Van Wunnik, Lucas Philippe, Van der Hurk, Evelien, Universitat Politècnica de Catalunya. Departament d'Organització d'Empreses, Danmarks tekniske universitet |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | Pick-up and Delivery Problem with Time Windows (PDPTW) is the problem of serving anumber of requests using a fleet of vehicles. In this work, different types of customers arehandled: walking and disabled customers (which use wheelchairs), and an heterogeneousfleet of vehicles is considered. The maximum time between the start and the end of theservice is of one hour.This thesis presents an Adaptive Large Neighborhood Search (ALNS) for solving large scaleinstances of the PDPTW. The requests for one day are grouped by time slices and clustered by pick-up and delivery locations. A construction heuristic calculates an initial solution by creating routes and assigning these routes to the vehicles. Then, an ALNS is applied to improve the solution.The metaheuristic is evaluated on real life large instances supplied by the transport company Konsentra. It finds better solutions than the company’s solutions, achieving a reductionin operational costs of 49% on average. The results indicate an improvement in vehicle efficiency, with an increase in customers served per vehicle hour by the minibuses of 304% on average. The improvement of the initial solution by the ALNS is of 30% on average, compared to 11% for the LNS, which proves that the performance of the ALNS is clearlybetter than implementing an LNS Objectius de Desenvolupament Sostenible::8 - Treball Decent i Creixement Econòmic Objectius de Desenvolupament Sostenible::11 - Ciutats i Comunitats Sostenibles |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|