Variable neighborhood search algorithms for the vehicle routing problem with two-dimensional loading constraints and mixed linehauls and backhauls
Autor: | Cláudio Alves, Telmo Pinto, José Manuel Valério de Carvalho |
---|---|
Přispěvatelé: | Universidade do Minho |
Jazyk: | angličtina |
Rok vydání: | 2020 |
Předmět: |
021103 operations research
Science & Technology Backhauls Computer science Strategy and Management 0211 other engineering and technologies Social Sciences Loading constraints 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research 01 natural sciences Computer Science Applications 010201 computation theory & mathematics Management of Technology and Innovation Vehicle routing problem Business and International Management Routing (electronic design automation) Algorithm Variable neighborhood search Routing |
Zdroj: | Repositório Científico de Acesso Aberto de Portugal Repositório Científico de Acesso Aberto de Portugal (RCAAP) instacron:RCAAP |
Popis: | In this paper, we explore a vehicle routing problem with two-dimensional loading constraints and mixed linehauls and backhauls. The addressed problem belongs to a subclass of general pickup and delivery problems. Two-dimensional loading constraints are also considered. These constraints arise in many real-world situations and can improve efficiency since backhaul customers do not need to be delayed in a route when it is possible to load their items earlier and without rearrangements of the items. To tackle this problem, we report extensive computational experiments to assess the performance of different variants of the variable neighborhood search approaches. The initial solution relies on an insertion heuristic. Both shaking and local search phases resort to 10 neighborhood structures. Some of those structures were specially developed for this problem. The feasibility of routes is heuristically obtained with a classical bottom-left based method to tackle the explicit consideration of loading constraints. All the strategies were implemented and exhaustively tested on instances adapted from the literature. The results of this computational study are discussed at the end of this paper. This work has been supported by FEDER funding through the Programa Operacional Factores de Competitividade COMPETE and through the Portuguese Science and Technology Foundation (FCT): project UID/CEC/00319/2013, grant SFRH/BD/73584/2010 and project MITP-TB/PFM/0005/2013 in the frame of MIT-Portugal program. |
Databáze: | OpenAIRE |
Externí odkaz: |