具有Back-time约束的k-TSP问题(英文)

本文讨论了具有Back-time约束的k-TSP问题,给出了求解该问题的近似算法,以及在最坏情况下由该算法产生的近似解的估计.

K-TSP问题的近似算法

利用△TSP问题的Christofides算法及其在K TSP问题上的扩展 ,通过权函数变换c′ij=cij-ui-vj 使c′ij>0 ,c′ik+c′kj≥c′ij,给出了求解K TSP问题的有效途径 ,得到了目标函数的更好的界值估计 ,C(Ha)≤λ(n)C(H ) -(λ(n) -1 ) {(k-1 )c11+∑ni=1 cii}.

城市垃圾分类收运中的数学模型化方法

研究厨余垃圾的处理与清运问题,为大、小型处理设备的数量选择、选址及垃圾收运路线的设计分别建立了最优化模型。模型中将城市道路网抽象成无向赋权图,考虑了在交通拥堵和环境影响下的运输成本、设备处理量的均衡性和对环境的影响程度,构成多目标优化问题,进而运用改进的粒子群算法确定大型设备的位置,并给出了设置小型设备的基本原则;通过分析大、小型设备在不同处理能力下总成本的差异,确定了适合城市实际情况的最优设备处理能力。垃圾收运路线设计中以运输成本与环保成本作为优化指标,建立了基于K-TSP的运输车辆清运路线模型,并运用蚁群算法进行路网优化。最后对深圳市南山区的厨余垃圾收运问题进行了仿真,仿真结果表明,上述模型和算法能有效地解决城市垃圾分类收运问题。