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

Z Kartal, A T Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

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 (n2) and O (n4)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.
Original languageEnglish
Title of host publicationMODSIM2015, 21st International Congress on Modelling and Simulation
EditorsRobert Anderssen, Tony Weber, Malcolm McPhee
Place of PublicationAustralia
PublisherModelling and Simulation Society of Australia and New Zealand
Pages1724-1730
Number of pages7
ISBN (Electronic)9780987214355
Publication statusPublished - 2015
Externally publishedYes
EventInternational Congress on Modelling and Simulation 2015: Partnering with industry and the community for innovation and impact through modelling - Gold Coast Convention and Exhibition Centre, Broadbeach, Australia
Duration: 29 Nov 20154 Dec 2015
Conference number: 21st
https://web.archive.org/web/20150627050926/http://www.mssanz.org.au:80/modsim2015/
https://web.archive.org/web/20150626200712/http://mssanz.org.au:80/modsim2015/index.html

Conference

ConferenceInternational Congress on Modelling and Simulation 2015
Abbreviated titleMODSIM2015
CountryAustralia
CityBroadbeach
Period29/11/154/12/15
OtherThe 21st International Congress on Modelling and Simulation (MODSIM2015) was held at the Gold Coast Convention and Exhibition Centre, Broadbeach, Queensland, Australia from Sunday 29 November to Friday 4 December 2015.

It was held jointly with the 23rd National Conference of the Australian Society for Operations Research and the DSTO led Defence Operations Research Symposium (DORS 2015).

The theme for this event was Partnering with industry and the community for innovation and impact through modelling.
Internet address

Keywords

  • p-hub center problems
  • hub location
  • hub location and routing problem
  • p-hub center and routing problems

Cite this

Kartal, Z., & Ernst, A. T. (2015). Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem. In R. Anderssen, T. Weber, & M. McPhee (Eds.), MODSIM2015, 21st International Congress on Modelling and Simulation (pp. 1724-1730). Australia: Modelling and Simulation Society of Australia and New Zealand.
Kartal, Z ; Ernst, A T. / Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem. MODSIM2015, 21st International Congress on Modelling and Simulation. editor / Robert Anderssen ; Tony Weber ; Malcolm McPhee. Australia : Modelling and Simulation Society of Australia and New Zealand, 2015. pp. 1724-1730
@inproceedings{19e47c8bc4ae45bcac8f5080eb66a87e,
title = "Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem",
abstract = "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 (n2) and O (n4)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.",
keywords = "p-hub center problems, hub location, hub location and routing problem, p-hub center and routing problems",
author = "Z Kartal and Ernst, {A T}",
year = "2015",
language = "English",
pages = "1724--1730",
editor = "Robert Anderssen and Tony Weber and Malcolm McPhee",
booktitle = "MODSIM2015, 21st International Congress on Modelling and Simulation",
publisher = "Modelling and Simulation Society of Australia and New Zealand",
address = "New Zealand",

}

Kartal, Z & Ernst, AT 2015, Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem. in R Anderssen, T Weber & M McPhee (eds), MODSIM2015, 21st International Congress on Modelling and Simulation. Modelling and Simulation Society of Australia and New Zealand, Australia, pp. 1724-1730, International Congress on Modelling and Simulation 2015, Broadbeach, Australia, 29/11/15.

Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem. / Kartal, Z; Ernst, A T.

MODSIM2015, 21st International Congress on Modelling and Simulation. ed. / Robert Anderssen; Tony Weber; Malcolm McPhee. Australia : Modelling and Simulation Society of Australia and New Zealand, 2015. p. 1724-1730.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

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

AU - Kartal, Z

AU - Ernst, A T

PY - 2015

Y1 - 2015

N2 - 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 (n2) and O (n4)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.

AB - 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 (n2) and O (n4)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.

KW - p-hub center problems

KW - hub location

KW - hub location and routing problem

KW - p-hub center and routing problems

UR - http://www.mssanz.org.au/modsim2015/J4/kartal.pdf

M3 - Conference Paper

SP - 1724

EP - 1730

BT - MODSIM2015, 21st International Congress on Modelling and Simulation

A2 - Anderssen, Robert

A2 - Weber, Tony

A2 - McPhee, Malcolm

PB - Modelling and Simulation Society of Australia and New Zealand

CY - Australia

ER -

Kartal Z, Ernst AT. Integer Programming Formulations for the Uncapacitated Vehicle Routing p-Hub Center Problem. In Anderssen R, Weber T, McPhee M, editors, MODSIM2015, 21st International Congress on Modelling and Simulation. Australia: Modelling and Simulation Society of Australia and New Zealand. 2015. p. 1724-1730