CAJ | 학술논문

选择性单商品配送收集问题（1-TSP-SELPD）是单商品配送收集问题（1-PDTSP）的推广，在许多实际领域都有广泛应用。1-TSP-SELPD属于NP难题，为了有效求解该问题，设计一个有效的蚁群算法。该算法从三个方面来提高求解性能：第一是启发式参数随着搜索状态自适应调整；第二是信息更新量随着求解质量进行动态变化；第三是设计适用于1-TSP-SELPD特点的、有约束的局部搜索技术用来加快收敛速度和提高解的质量。比较实验表明：该算法在求解质量、稳定性和收敛速度都有显著提高。
선택성단상품배송수집문제（1-TSP-SELPD）시단상품배송수집문제（1-PDTSP）적추엄，재허다실제영역도유엄범응용。1-TSP-SELPD속우NP난제，위료유효구해해문제，설계일개유효적의군산법。해산법종삼개방면래제고구해성능：제일시계발식삼수수착수색상태자괄응조정；제이시신식경신량수착구해질량진행동태변화；제삼시설계괄용우1-TSP-SELPD특점적、유약속적국부수색기술용래가쾌수렴속도화제고해적질량。비교실험표명：해산법재구해질량、은정성화수렴속도도유현저제고。
One-commodity travelling salesman problem with selective pickup and delivery ( 1-TSP-SELPD ) is the generalisation of one-commodity pickup-and-delivery travelling salesman problem ( 1-PDTSP ) and has wide applications in many practical areas . The 1-TSP-SELPD is known as an NP-hard.In order to effectively solve it , in this paper we propose an effective ant colony algorithm .The algorithm improves the performance of the solution from three aspects .The first is that the heuristic parameter will be adjusted adaptively with the searching state;The second is that the updated information amount will be changed dynamically with solution quality ;The third is that to design the constrained local searching technique suitable to the characteristics of 1-TSP-SELPD for accelerating the convergence speed and improving the quality of solution .Comparative experiments show that the improved algorithm has noticeable improvements in solution quality , stability and convergence speed .