An efficient heuristic for a hub location routing problem
- PDF / 435,201 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 246 Views
An efficient heuristic for a hub location routing problem Mustapha Ratli1 · Dragan Uroševi´c 2 · Abdessamad Ait El Cadi1 · Jack Brimberg3 · Nenad Mladenovi´c 4 · Raca Todosijevi´c1 Received: 31 May 2020 / Accepted: 19 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper examines a new model for hub location known as the hub location routing problem. The problem shares similarities with the well studied uncapacitated single allocation p-hub median problem except that the hubs are now connected to each other by a cyclical path (or tour) known as the global route, each cluster of nonhub nodes and assigned hub is also connected by a single tour known as a local route, and the length of the local routes is constrained to a maximum number of nodes. Thus, aside from the normal tasks of hub selection and allocation of nonhub nodes, up to p + 1 travelling salesman problems need to be solved. A heuristic based on the general variable neighborhood search framework is proposed here to solve this very complicated problem. The improvement phase of the algorithm uses a sequential variable neighborhood descent with multiple neighborhoods required to suit the complex nature of the problem. A best sequencing of the neighborhoods is established through empirical testing. The perturbation phase known as the shaking procedure also uses a well-structured selection of neighborhoods in order to effectively diversify the search to different regions of the solution space. Extensive computational testing shows that the new heuristic significantly outperforms the state-of-the-art. Out of 912 test instances from the literature, we are able to obtain 691 new best known solutions. Not only are the improvements in objective values quite impressive, but also these new solutions are obtained in a small fraction of the time required by the competing algorithms. Keywords p-hub · Hub location-routing problem · Heuristics · General variable neighborhood search
1 Introduction The aim of a transportation/communication network is to facilitate transport/communication between all origin–destination (O–D) pairs. Establishing direct transport/ communication between all O–D pairs may be unreasonable for many reasons espe-
Extended author information available on the last page of the article
123
M. Ratli et al.
cially from the economic (or cost) perspective. As an alternative approach, the idea of hub networks has been proposed. The main feature of a hub network that differentiates it from other types is the existence of special nodes (hubs) designated to enable the connection between O–D pairs. Namely, instead of having a direct path between each pair of nodes, nodes communicate via hubs. For example, if we have an origin node O and a destination D, a valid path between them may have the form O − hub1 − hub2 − D. More precisely, the flow from O to D is first collected at hub1 then transferred to hub2 and finally delivered to node D. So, the main principle of hub networks is that direct connection between non-hu
Data Loading...
