Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem
Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem
复制标题
DOI：
10.1016/j.ejor.2016.06.058
复制
发表时间：
2017-02
期刊：
影响因子：
--
通讯作者：
Emilio Zamorano;R. Stolletz
中科院分区：
文献类型：
--
作者：
Emilio Zamorano;R. Stolletz
本文讨论了由外部维护提供者的案例所引起的技术人员路由和调度问题。技术人员精通不同的技能，并组成团队执行维护任务。任务是受技能限制的，并且有可能跨越数天的时间窗口。目标是确定每天将技术人员分配到团队中，将团队分配到任务中，以及将团队分配到日常路线中，从而将操作成本降至最低。我们提出了一个混合整数规划和分支价格算法来解决这个问题。利用问题的结构，替代公式用于算法的列生成阶段。使用来自外部维护提供商的真实数据，我们进行数值研究，以评估我们提出的解决方案方法的性能。
This paper addresses a technician routing and scheduling problem motivated by the case of an external maintenance provider. Technicians are proficient in different skills and paired into teams to perform maintenance tasks. Tasks are skill constrained and have time windows that may span multiple days. The objective is to determine the daily assignment of technicians into teams, of teams to tasks, and of teams to daily routes such that the operation costs are minimized. We propose a mixed integer program and a branch-and-price algorithm to solve this problem. Exploiting the structure of the problem, alternative formulations are used for the column generation-phase of the algorithm. Using real-world data from an external maintenance provider, we conduct numerical studies to evaluate the performance of our proposed solution approaches.