Publication detail

Hybrid Algorithm for Network Design Problem with Uncertain Demands

ROUPEC, J. POPELA, P. HRABEC, D. NOVOTNÝ, J. HAUGEN, K. OLSTAD, A.

Czech title

Hybridní algoritmus pro návrh sítě s neurčitou poptávkou

English title

Hybrid Algorithm for Network Design Problem with Uncertain Demands

Type

conference paper

Language

en

Original abstract

The purpose of the paper is to present a hybrid algorithm to solve a transportation optimization model with random demand parameters and network design variables. At first, the classical deterministic linear transportation model with network design 0-1 variables is introduced. Then, randomness is considered for demand parameters and modeled by here-and-now approach. The obtained scenario-based model leads to a mixed integer linear program (MILP) that can be solved by common integer programming techniques, see e.g. the branch-and-bound algorithm implemented in the CPLEX solver. Such a program may reach solvability limitations of MIP algorithms for large scale real world data, so a suitable heuristic development is welcome. Therefore, the idea of combination of traditional optimization algorithm and genetic algorithm is discussed and developed. At the end, the results are illustrated and also verified for a small test instance by figures.

Czech abstract

Cílem článku je prezentovat hybridní algoritmus pro řešení dopravních optimalizačních modelů s náhodnou poptávkou a návrhovými proměnnými sítě. V úvodu je popsán klasický deterministický lineární dopravní model s návrhovými 0-1 proměnnými. Dále je zavedena náhodnost poptávky a je modelována HN přístupem. Vzniklý scénářový model vede na smíšenou úlohu celočíselného lineárního programování (MILP), která může být řešena obecnými technikami celočíselného lineárního programování, např. algoritmem větví a mezí implementovaným v GAMS v řešiči CPLEX. Takový program může překročit meze řešitelnosti MIP algoritmů pro rozsáhlá data, proto je vhodné použít heuristické techniky. Je popsána a diskutována metoda kombinující tradiční optimalizační algoritmus a genetický algoritmus. Tato metoda je použita a verifikována na testovací úloze.

English abstract

The purpose of the paper is to present a hybrid algorithm to solve a transportation optimization model with random demand parameters and network design variables. At first, the classical deterministic linear transportation model with network design 0-1 variables is introduced. Then, randomness is considered for demand parameters and modeled by here-and-now approach. The obtained scenario-based model leads to a mixed integer linear program (MILP) that can be solved by common integer programming techniques, see e.g. the branch-and-bound algorithm implemented in the CPLEX solver. Such a program may reach solvability limitations of MIP algorithms for large scale real world data, so a suitable heuristic development is welcome. Therefore, the idea of combination of traditional optimization algorithm and genetic algorithm is discussed and developed. At the end, the results are illustrated and also verified for a small test instance by figures.

Keywords in Czech

hybridní algoritmus, transportation network design problem, stochastic programing, genetic algorithm, GAMS

Keywords in English

hybrid algorithm, návrh dopravní sítě, stochastické programování, genetický algoritmus, GAMS

RIV year

2013

Released

23.10.2013

ISBN

978-988-19252-3-7

ISSN

2078-0958

Book

Lecture Notes in Engineering and Computer Science WCECS 2013

Volume

2013

Number

1

Edition number

1

Pages from–to

554–559

Pages count

6

BIBTEX


@inproceedings{BUT103257,
  author="Jan {Roupec} and Pavel {Popela} and Dušan {Hrabec} and Jan {Novotný} and Kjetil Kare {Haugen} and Asmund {Olstad},
  title="Hybrid Algorithm for Network Design Problem with Uncertain Demands",
  booktitle="Lecture Notes in Engineering and Computer Science WCECS 2013",
  year="2013",
  volume="2013",
  number="1",
  month="October",
  pages="554--559",
  isbn="978-988-19252-3-7",
  issn="2078-0958"
}