A column generation approach for the lexicographic optimization of intra-hospital transports
提出一种列生成方法，通过词典序优化解决医院内部转运任务分配的多目标问题，在德国医院实际应用，可减轻医护人员工作负担。
Abstract Over the last few years, the efficient design of processes in hospitals and medical facilities has received more and more attention, particularly when the improvement of the processes is aimed at relieving the workload of medical staff. To this end, we have developed a method to determine optimal allocations of intra-hospital transports to hospital transport employees. When optimizing transport plans in hospitals, there are various optimization goals to strive for. Therefore, we used a lexicographic approach to solve this multi-criteria optimization problem. To calculate optimal transport plans in a sufficiently short computation time, we have decomposed the problem at hand with the Dantzig–Wolfe reformulation and solved the resulting pricing subproblem with an enumerative column generation approach. To improve the efficiency of the column generation process, we have investigated and implemented different pruning methods, dominance rules and a column reuse mechanism for the online setting of the application at hand. In an extensive computational study, we first evaluated the efficiency of the different pruning methods before we compared our solution approach with the standard branch-and-bound column search approach, classical column generation methods and the solution of an integrated MIP model solved by a commercial solver. Finally, we present performance indicators of the transport optimization tool, which was developed from our method and is now productively used in a German hospital.