A Hierarchical Bio-inspired Computing for the Hub Location-Routing Problem in Parcel Service

摘要

This paper deals with a hub location-routing problem (HLRP) which integrates the hub location problem (HLP) and the multi-hub vehicle routing problem (MH-VRP) in parcel delivery service. The HLRP is very difficult to be solved since it is composed of two NP-hard problems, the HLP and the MH-VRP. To solve these problems simultaneously we present a novel solution framework which divides the problem into two sub-problems: HLP in the first stage and the MH-VRP in the second one. The two-phase approach hybridizes two bio-inspired computing techniques, an ant colony optimization algorithm for the first stage with a genetic algorithm for the second stage, respectively. We determine the locations of prescribed p hubs within a set of candidate potential parcel sorting centers (PSC), the allocation of each customer node to each selected PSC as well as the vehicle routes for each PSC in order to minimize the sum of the fixed hub costs, traveling costs and fixed vehicle costs. A hierarchical bio-inspired computing based on an ant colony optimization and a genetic search is developed which solves the HLP and VRP hierarchically. The performance of the proposed solution method is investigated through a computational experiment.