|
|||||
|
|
An exact algorithm for the network pricing problem |
|
| Authors: | L. Brotcorne F. Cirinei P. Marcotte G. Savard |
| Affiliation: | a INRIA Lille Nord Europe, Parc Scientifique de la Haute Borne, 40 Avenue Halley, BAT A Park Plaza 59650 Villeneuve d’Ascq, France;b ExPretio, 200 Laurier Street West, Suite 400, Montréal (QC), H2T 2N8, Canada;c CIRRELT and Département d’Informatique et de Recherche Opérationnelle, Université de Montréal C.P. 6128, Succursale Centre-Ville, Montréal (QC), H3C 3J7, Canada;d GERAD and Département de Mathématiques et de Génie Industriel, Ecole Polytechnique de Montréal C.P. 6079, Succursale Centre-Ville, Montréal (QC), H3C 3A7, Canada |
| Abstract: | This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation. |
| Keywords: | Pricing Bilevel programming Networks Column generation Combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ | |