Quotation Strodl, Johannes, Doerner, Karl F., Tricoire, Fabien, Hartl, Richard F. 2010. On index structures in hybrid metaheuristics for routing problems with hard feasibility checks: An application to the 2-dimensional loading vehicle routing problem. Lecture Notes in Computer Science. 6373 160-173.


RIS


BibTeX

Abstract

In this paper we study the impact of different index structures used within hybrid solution approaches for vehicle routing problems with hard feasibility checks. We examine the case of the vehicle routing problem with two-dimensional loading constraints, which combines the loading of freight into the vehicles and the routing of the vehicles to satisfy the demands of the customers. The problem is solved by a variable neighborhood search for the routing part, in which we embed an exact procedure for the loading subproblem. The contribution of the paper is threefold: i) Four different index mechanisms for managing the subproblems are implemented and tested. It is shown that simple index structures tend to lead to better solutions than more powerful albeit complex ones, when using the same runtime limits. ii) The problem of balancing the CPU budget between exploration of different solutions and exact solution of the loading subproblem is investigated; experiments show that solving exactly hard subproblems can lead to better solution quality over the whole solution process. iii) New best results are presented on existing benchmark instances.

Tags

Press 'enter' for creating the tag

Publication's profile

Status of publication Published
Affiliation External
Type of publication Journal article
Journal Lecture Notes in Computer Science (LNCS)
WU-Journal-Rating new STRAT-C
Language English
Title On index structures in hybrid metaheuristics for routing problems with hard feasibility checks: An application to the 2-dimensional loading vehicle routing problem
Volume 6373
Year 2010
Page from 160
Page to 173
Reviewed? Y
URL https://link.springer.com/chapter/10.1007/978-3-642-16054-7_12
DOI https://doi.org/10.1007/978-3-642-16054-7_12
Open Access N

Associations

People
Tricoire, Fabien (Details)
External
Doerner, Karl F. (Universität Wien, Austria)
Hartl, Richard F. (Universität Wien, Austria)
Strodl, Johannes (Universität Wien, Austria)
Google Scholar: Search