Login | Register

Network design under uncertainty and demand elasticity


Network design under uncertainty and demand elasticity

Zetina, Carlos ORCID: https://orcid.org/0000-0001-5502-3232 (2018) Network design under uncertainty and demand elasticity. PhD thesis, Concordia University.

Text (application/pdf)
Zetina_PhD_S2019.pdf - Accepted Version


Network design covers a large class of fundamental problems ubiquitous in the fields of transportation and communication. These problems are modelled mathematically using directed graphs and capture the trade-off between initial investment in infrastructure and operational costs. This thesis presents the use of mixed integer programming theory and algorithms to solve network design problems and their extensions. We focus on two types of network design problems, the first is a hub location problem in which the initial investments are in the form of fixed costs for installing infrastructure at nodes for them to be equipped for the transhipment of commodities. The second is a fixed-charge multicommodity network design problem in which investments are in the form of installing infrastructure on arcs so that they may be used to transport commodities.

We first present an extension of the hub location problem where both demand and transportation cost uncertainty are considered. We propose mixed integer linear programming formulations and a branch-and-cut algorithm to solve robust counterparts for this problem. Comparing the proposed models' solutions to those obtained from a commensurate stochastic counterpart, we note that their performance is similar in the risk-neutral setting while solutions from the robust counterparts are significantly superior in the risk-averse setting.

We next present exact algorithms based on Benders decomposition capable of solving large-scale instances of the classic uncapacitated fixed-charge multicommodity network design problem. The method combines the use of matheuristics, general mixed integer valid inequalities, and a cut-and-solve enumeration scheme. Computational experiments show the proposed approaches to be up to three orders of magnitude faster than the state-of-the-art general purpose mixed integer programming solver.

Finally, we extend the classic fixed-charge multicommodity network design problem to a profit-oriented variant that accounts for demand elasticity, commodity selection, and service commitment. An arc-based and a path-based formulation are proposed. The former is a mixed integer non-convex problem solved with a general purpose global optimization solver while the latter is an integer linear formulation with exponentially many variables solved with a hybrid matheuristic. Further analysis shows the impact of considering demand elasticity to be significant in strategic network design.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical, Industrial and Aerospace Engineering
Item Type:Thesis (PhD)
Authors:Zetina, Carlos
Institution:Concordia University
Degree Name:Ph. D.
Program:Industrial Engineering
Date:12 November 2018
Thesis Supervisor(s):Contreras, Ivan and Cordeau, Jean-François
Keywords:Network design; Mathematical Programming; Benders decomposition; Gravity Model
ID Code:984814
Deposited On:10 Jun 2019 15:07
Last Modified:10 Jun 2019 15:07
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top