Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem

Hub facilities are used in many-to-many transportation networks such as passenger airlines,parcel delivery, and telecommunication system networks. In these networks, the flow that is interchanged between the demand centers is routed via the hubs to provide discounted transport. Many parcel delivery firms serve on a hub based system where the flows from different demand nodes are concentrated, sorted and disseminated at the hub centers in order to transfer them to the destinations points. The main purpose of hub location problem is to decide the location of hub facilities and to allocate demand nodes to the hubs.In hub based systems, as an alternative way of serving each origin destination node directly, the flow is accumulated at the hub facilities in order to exploit the substantial economies of scale.

Hub location problems can be categorized in terms of the objective function of the mathematical models. In the literature, hub location problems with total transportation cost objectives (median), min-max type objectives (center) and covering type objectives are well studied.

In the hub location problem literature, it is assumed that only one vehicle serves between each demand center and hub. The vehicles are not permitted to visit more than one city. The need to design a network of combined hub locations and vehicle routes arises in various applications. For example, in cargo delivery systems, sending separate vehicles between each demand center and hub is rather costly in terms of investment on the total number of vehicles. Instead, if the vehicles are allowed to follow a route by visiting different demand nodes in each stop, the total investment cost may decrease considerably. In airline companies, similarly, if a separate aircraft and separate air staff are assigned for each destination, they incur high investment and operating costs. Also, traffic congestion occurs at airports and in air networks.

In the light of above-mentioned real life considerations, the vehicle routing hub location problem has been receiving increased attention from researchers. This problem is to decide the location of hubs, the allocation demand centers to the hubs and the associated routing structure with multiple stopovers and allowing vehicles to make a tour so as to minimize total transportation cost.
In addition to the cost, parallel to the increase of the competition in the market, companies tend to promise to the customers ’next day delivery’ or ’delivery within 24 h’ guarantees. However, the hub location and vehicle routing problem, which consider both the flows and distances, may sometimes lead to delays from non-simultaneous arrivals at hubs, when worst-case route lengths for vehicles are excessively large. Although classical hub location problems provide one option when origin-destination distances are huge, they become less appropriate when vehicle routing is required and delivery time is a major concern.

In this study, we introduce the uncapacitated vehicle routing p-hub center problem to the literature. The aim of our model is to find the location of the hubs, assign demand centers to the hubs and determine the routes of vehicles for each hub such that the maximum distance or travel time between origin-destination pairs is minimized. We propose mathematical programming formulations for this problem with O (n²) and O (n⁴)variables. The formulations trade off tightness against formulation size. The computational results on standard data sets from the literature allow this trade off to be evaluated empirically and provide an indication of the challenge of solving these combined vehicle routing hub location problems.