OPTW的两阶段网络优化算法

以组合最优化问题中的定向问题为原型,结合它的新一类变形问题包括网络磁盘故障修复问题、制药销售员问题和垃圾回收车路线问题等进行分析,建立网络上有时间窗口限制的定向问题的数学模型,利用两阶段算法原理的思想,设计一种网络上满足时间窗口限制的定向问题求解算法,进行实例验证.结果表明该算法易于实现、且收益增幅明显等优点,为一类网络上有时间窗口限制的最优化问题提供新的求解算法.

A two-stage geometric network algorithm for OPTW

With the orienteering problem in combinatorial optimization problems as the prototype plus a new type of deformation problems,including network disk restoration,pharmaceutical salesmen's problems and the recycling-car routing problem,this paper establishes a network-based mathematical model for the orienteering problem with a time window limit,and designs a kind of two-stage geometric network algorithm for it. The experiments have shown that this algorithm is easily applicable and has the advantage of apparent earnings growth,that is,a new algorithm for solving the problem with the time window limit in a class of geometric network optimization.