Telecommunication networks frequently face technological advancements and need to upgrade their infrastructure. Adapting legacy networks to the latest technology requires synchronized technicians responsible for migrating the equipment. The goal of the network migration problem is to find an optimal plan for this process. This is a defining step in the customer acquisition of telecommunications service suppliers, and its outcome directly impacts the network owners' purchasing behaviour. We propose the first exact method for the network migration problem, a logic-based Benders decomposition approach that benefits from a hybrid constraint programming-based column generation in its master problem and a constraint programming model in its subproblem. This integrated solution technique is applicable to any integer programming problem with similar structure, most notably the vehicle routing problem with node synchronization constraints. Comprehensive evaluation of our method over instances based on six real networks demonstrates the computational efficiency of the algorithm in obtaining quality solutions. We also show the merit of each incorporated optimization paradigm in achieving this performance.
翻译:使遗留网络适应最新技术需要同步技术人员负责设备迁移。网络迁移问题的目标是为这一进程找到最佳计划。这是客户获取电信服务供应商的决定性步骤,其结果直接影响网络所有者的购买行为。我们提出了网络迁移问题的第一个确切方法,一种基于逻辑的本德尔斯分解方法,它得益于基于总问题的混合约束性编程列材生成,以及其次问题的制约性编程模式。这种综合解决方案技术适用于结构相似的任何整数编程问题,其中最突出的是具有节奏同步限制的车辆路由问题。对基于六个实际网络的我们的方法进行综合评估,显示了获得高质量解决方案的算法计算效率。我们还展示了实现这一绩效的每一种整合优化模式的优点。