A Heuristic Procedure with Local Branching for the Fixed Charge Network Design Problem with User-optimal Flow

Pedro Henrique González, Luidi Gelabert Simonetti, Carlos Alberto de Jesus Martinhon, Philippe Yves Paul Michelon, Edcarllos Santos

2014

Abstract

Due to the constant development of society, increasing quantities of commodities have to be transported in large urban centers. Therefore, network design problems arise as tools to support decision-making, aiming to meet the need of finding efficient ways to perform the transportation of each commodity from its origin to its destination. This paper reviews a bi-level formulation, an one level formulation obtained by applying the complementary slackness theorem, Bellman’s optimality conditions and Big-M linearizing technique. A heuristic procedure is proposed, through combining a randomized constructive algorithm with a Relax-and-Fix heuristic to generate an initial solution. After that a Local Branching technique is applied to improve the constructed solution, so high quality solutions can be found. Besides that, our computational results are compared with the results found in the literature, showing the efficiency of the proposed method.

Paper Citation

in Harvard Style

Henrique González P., Gelabert Simonetti L., Alberto de Jesus Martinhon C., Yves Paul Michelon P. and Santos E. (2014). A Heuristic Procedure with Local Branching for the Fixed Charge Network Design Problem with User-optimal Flow . In Proceedings of the 16th International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-989-758-027-7, pages 384-394. DOI: 10.5220/0004885903840394

in Bibtex Style

@conference{iceis14,
author={Pedro Henrique González and Luidi Gelabert Simonetti and Carlos Alberto de Jesus Martinhon and Philippe Yves Paul Michelon and Edcarllos Santos},
title={A Heuristic Procedure with Local Branching for the Fixed Charge Network Design Problem with User-optimal Flow},
booktitle={Proceedings of the 16th International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2014},
pages={384-394},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0004885903840394},
isbn={978-989-758-027-7},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 16th International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - A Heuristic Procedure with Local Branching for the Fixed Charge Network Design Problem with User-optimal Flow
SN - 978-989-758-027-7
AU - Henrique González P.
AU - Gelabert Simonetti L.
AU - Alberto de Jesus Martinhon C.
AU - Yves Paul Michelon P.
AU - Santos E.
PY - 2014
SP - 384
EP - 394
DO - 10.5220/0004885903840394