我的最新论文针对经典NP-hard问题,首次提出了两个ILP模型和精确算法。在领域最常用的Mandl's network数据集上,该算法实现了高效获得最优解,在精确算法效率方面处于领先地位。
TRNDP和VRP在一定程度上很相似,都是需要构建线路让车来跑。但TRNDP又具备其独特的结构和规则,客流分配子问题的存在让问题复杂度急剧上升,也使得最重要的决策单元(线路)并不是直接作用于目标函数(如果采用“乘客出行时间”为目标函数),而是通过决定客流来体现对目标函数的影响。
目前这个领域的精确算法研究较少,提出的模型具有较强的拓展性。TRNDP可以添加很多新东西进入考虑(如发车频率、能否跨站等等),可以在该模型基础上添加新东西,并对应设计算法。
(未完待续)
问题描述+算法求解表现