A BRANCH-AND-PRICE ALGORITHM FOR THE WINDY RURAL POSTMAN PROBLEM

被引：0
|
作者：
Afsar, Hasan Murat [1 ]
Jozefowiez, Nicolas [2 ,3 ]
Lopez, Pierre [2 ]
机构：
[1] Univ Technol Troyes, Inst Charles Delaunay, LOSI, F-10010 Troyes, France
[2] CNRS, LAAS, F-31077 Toulouse 4, France
[3] Univ Toulouse, INSA, LAAS, F-31400 Toulouse, France
来源：
RAIRO-OPERATIONS RESEARCH | 2011年 / 45卷 / 04期
关键词：
Branch-and-price; windy rural postman problem; CUTTING PLANE ALGORITHM; ROUTING PROBLEM;
D O I：
10.1051/ro/2012004
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we propose an exact solution method for the windy rural postman problem (WRPP). The motivation to study this problem comes from some real-life applications, such as garbage collecting in a predefined sector with hills, where the traversing or the servicing speed can change following the direction. We present a Dantzig-Wolfe decomposition and a branch-and-price algorithm to solve the WRPP. To the best of our knowledge, Dantzig-Wolfe decomposition has never been used to solve that problem. The numerical results show that optimal solutions are found in a very reasonable amount of time on instances with up to 100 nodes and 180 edges.
引用
收藏
页码：353 / 364
页数：12
相关论文
共 50 条
  • [1] A branch-and-cut algorithm for the profitable windy rural postman problem
    Avila, Thais
    Corberan, Angel
    Plana, Isaac
    Sanchis, Jose M.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 249 (03) : 1092 - 1101
  • [2] A branch-and-cut algorithm for the windy profitable location rural postman problem
    Khorramizadeh, Mostafa
    Javvi, Roghayeh
    ANNALS OF OPERATIONS RESEARCH, 2024, 341 (2-3) : 993 - 1022
  • [3] A Branch-Price-and-Cut Algorithm for the Min-Max k-Vehicle Windy Rural Postman Problem
    Benavent, Enrique
    Corberan, Angel
    Desaulniers, Guy
    Lessard, Francois
    Plana, Isaac
    Sanchis, Jose M.
    NETWORKS, 2014, 63 (01) : 34 - 45
  • [4] A branch-and-price algorithm for a targeting problem
    Kwon, Ojeong
    Lee, Kyungsik
    Kang, Donghan
    Park, Sungsoo
    NAVAL RESEARCH LOGISTICS, 2007, 54 (07) : 732 - 741
  • [5] A branch-and-price algorithm for the ring/ring problem
    Osorio, Cecilia Lescano
    Hoshino, Edna Ayako
    PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, 2021, 195 : 516 - 522
  • [6] A Branch-and-Price Algorithm for the Multiple Knapsack Problem
    Lalonde, Olivier
    Cote, Jean-Francois
    Gendron, Bernard
    INFORMS JOURNAL ON COMPUTING, 2022, 34 (06) : 3134 - 3150
  • [7] A branch-and-price algorithm for the generalized assignment problem
    Savelsbergh, M
    OPERATIONS RESEARCH, 1997, 45 (06) : 831 - 841
  • [8] A branch-and-price algorithm for the Minimum Latency Problem
    Bulhoes, Teobaldo
    Sadykov, Ruslan
    Uchoa, Eduardo
    COMPUTERS & OPERATIONS RESEARCH, 2018, 93 : 66 - 78
  • [9] A Branch-and-Price algorithm for a compressor scheduling problem
    Friske, Marcelo Wuttig
    Buriol, Luciana S.
    Camponogara, Eduardo
    COMPUTERS & INDUSTRIAL ENGINEERING, 2018, 116 : 72 - 81
  • [10] Branch-and-price algorithm for a multicast routing problem
    Sung, CS
    Hong, JM
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1999, 50 (11) : 1168 - 1175
12345