论文标题
驱动程序路由和调度具有同步约束
Driver Routing and Scheduling with Synchronization Constraints
论文作者
论文摘要
本文调查了一种新型的驾驶员路由和调度问题，该问题是由长途巴士网络中的实际应用所激发的。与其他机组调度问题的关键区别在于，在途中，在任意中间停止处的总线之间可以交换驾驶员，以便我们的问题需要其他同步约束。我们为此问题提供了一个数学模型，该模型利用了时间扩展的多传输，并为所需驱动程序的总数得出了界限。此外，我们开发了一种破坏性的增强数学效果，该数学疗法汇聚到可证明的最佳解决方案，并将其应用于欧洲领先的教练公司之一Flixbus的现实世界案例研究。我们证明，与当前在实践中使用的方法相比，我们的数学算法在解决方案质量和计算时间方面优于独立MIP实现，并将所需驱动因素的数量减少多达56％。我们的解决方案方法在几秒钟内为所有实例提供了可行的解决方案，并解决了最多390个位置和70个请求的实例，在210秒以下的平均计算时间最佳。我们进一步研究了驾驶员交流对总驾驶员数量的影响，并表明允许这样的交换导致平均节省42.69％。
This paper investigates a novel type of driver routing and scheduling problem motivated by a practical application in long-distance bus networks. A key difference from other crew scheduling problems is that drivers can be exchanged between buses at arbitrary intermediate stops en route such that our problem requires additional synchronization constraints. We present a mathematical model for this problem that leverages a time-expanded multi-digraph and derive bounds for the total number of required drivers. Moreover, we develop a destructive-bound-enhanced matheuristic that converges to provably optimal solutions and apply it to a real-world case study for Flixbus, one of Europe's leading coach companies. We demonstrate that our matheuristic outperforms a standalone MIP implementation in terms of solution quality and computational time and reduces the number of required drivers by up to 56% compared to approaches currently used in practice. Our solution approach provides feasible solutions for all instances within seconds and solves instances with up to 390 locations and 70 requests optimally with an average computational time under 210 sec. We further study the impact of driver exchanges on the total driver count and show that allowing for such exchanges leads to average savings of 42.69%.
