ABSTRACT
Thispaper describes a newly developed hybrid heuristic for solving theuncapacitated single allocation hub location problem (USAHLP). The hybrid IGAalgorithm integrates fuzzy Iterative Self Organizing Data (ISODATA) clusteringwith a genetic algorithm (GA). The candidate hub nodes are first determined byemploying fuzzy ISODATA clustering, then the satisfactory hubs among thecandidates by the presentation and evolution of chromosomes are searched bygenetic algorithm, making the total cost including collection, transfer,distribution, and the costs of establishing hubs as minimized as possible. Thisnew hybrid algorithm is simple to use to optimize practical transportation networks. It is applied to redesign a new logisticsnetwork for a large logistics company in Hebeiprovince, which needs to merge its old freight network and express network intoone logistic system. 30% decrease in the total logistics cost for the newnetwork proves its effectiveness.
Introduction
Hub-and-spoke networks provide services via aspecified set of hub nodes so as to reduce the overall transportation cost. Allhubs, which act as switching points for intermodal flows, are interconnectedand none of the non-hubs are directly connected. Each of the other non-hub nodesis allocated to a single hub or multiple hubs and is referred to as a spoke.With its improvement to operation of distribution function, hub-and-spokenetworks are widely studied in the area of logistics, such as package delivery(Kuby et al., 1993), goods supply (Abdinnour-Helm, 2001), trucking (Tayloret al., 1995)and intermodaltransportation (Racunica et al., 2005). Many types of hub-and-spoke networks have been researched since thefirst problem was formulated by O’Kelly (1987) and Campbell (2002). One of themost commonly encountered problems in practice is the uncapacitated singleallocation hub location problem (USAHLP). In this kind of problem, thenumber of hubs is not predetermined, there are no capacity restrictions on thevolume of a hub, each spoke (non-hub node) is allocated to a single hub node,the objective function is to find the location of the hubs and the allocationof the nodes so that the total cost including collection, transfer,distribution, and the costs of establishing hubs is minimized. Because USAHLPis NP-hard (O’Kelly, 1987), many heuristics are proposed. O’Kelly (1992)devised a problem specific heuristics composed of two steps which involves anestimate of a good upper bound and the computation of a tight lower bound on thesolution. Smith et al.(1996) mapped the problem onto a Hopfield neural network which guarantees feasibilityof the final solution and proposed a novel modification to the Hopfield networkwhich enables escape from local minima. Abdinnour-Helm (1998) developed a hybridof Genetic Algorithms (GAs) and Tabu Search (TS), in which Gas are used todetermine the number and the locations of hubs, TS is used to find the optimalassignment of spokes to hubs. Topcuoglua et al. (2005) provided the node whichhas higher amount of flow to become a hub with higher probability and used thechromosome consisting of two arrays: HubArray and AssignArray to search theoptimal solution with genetic algorithm.