In this paper we applicate the Hungarian algorithm for assignment problem to solve traveling salesman problem. Tree examples of application of algorithm are included.
With the increase of space debris,space debris removal has gradually become a major issue to address by worldwide space agencies.Multiple debris removal missions,in which multiple debris objects are removed in a singl...With the increase of space debris,space debris removal has gradually become a major issue to address by worldwide space agencies.Multiple debris removal missions,in which multiple debris objects are removed in a single mission,are an economical approach to purify the space environment.Such missions can be considered typical time-dependent traveling salesman problems(TDTSPs).In this study,an intelligent global optimization algorithm called Timeline Club Optimization(TCO)is proposed to solve multiple debris removal missions of the TDTSP model.TCO adopts the traditional ant colony optimization(ACO)framework and replaces the pheromone matrix of the ACO with a new structure called the Timeline Club.The Timeline Club records which debris object to be removed next at a certain moment from elitist solutions and decides the probability criterion to generate debris sequences in new solutions.Two hypothetical scenarios,the Iridium-33 mission and the GTOC9 mission,are considered in this study.Simulation results show that TCO offers better performance than those of beam search,ant colony optimization,and the genetic algorithm in multiple debris removal missions of the TDTSP model.展开更多
Firstly an overview of the potential impact on work-in-process （WIP） and lead time is provided when transfer lot sizes are undifferentiated from processing lot sizes. Simple performance examples are compared to thos...Firstly an overview of the potential impact on work-in-process （WIP） and lead time is provided when transfer lot sizes are undifferentiated from processing lot sizes. Simple performance examples are compared to those from a shop with one-piece transfer lots. Next, a mathematical programming model for minimizing lead time in the mixed-model job shop is presented, in which one-piece transfer lots are used. Key factors affecting lead time are found by analyzing the sum of the longest setup time of individual items among the shared processes （SLST） and the longest processing time of individual items among processes （LPT）. And lead time can be minimized by cutting down the SLST and LPT. Reduction of the SLST is described as a traveling salesman problem （TSP）, and the minimum of the SLST is solved through job shop scheduling. Removing the bottleneck and leveling the production line optimize the LPT. If the number of items produced is small, the routings are relatively short, and items and facilities are changed infrequently, the optimal schedule will remain valid. Finally a brief example serves to illustrate the method.展开更多
针对迭代局部搜索(iterated local search,ILS)算法求解旅游线路时间花费较长的问题,提出了一种ILS结合布谷鸟搜索(cuckoo search,CS)的优化算法,来优化旅游线路的时间花费。该算法首先根据相关目标和约束采用ILS算法求解旅游景点及初...针对迭代局部搜索(iterated local search,ILS)算法求解旅游线路时间花费较长的问题,提出了一种ILS结合布谷鸟搜索(cuckoo search,CS)的优化算法,来优化旅游线路的时间花费。该算法首先根据相关目标和约束采用ILS算法求解旅游景点及初始旅游线路,然后在满足旅游景点时间窗约束及景点总数不变的情况下采用CS算法进一步最小化旅游线路的时间花费。该研究获得的线路更符合旅游习惯,并且旅游时间花费更少。通过Daminaos数据集和桂林景点数据集进行验证,结果表明该优化算法相比于仅使用ILS算法所规划出的旅游线路,平均时间花费减少8%,更符合用户旅游选择习惯。展开更多
针对带有时间窗限制的旅行商问题(travelling salesman problem with time windows,TSPTW)提出了一种基于磁场模型的蚁群变异算法(MFM-ACOMF).它通过修正传统蚁群算法的启发函数,满足用户的时间需求,并降低算法陷入局部最优的可能性;在...针对带有时间窗限制的旅行商问题(travelling salesman problem with time windows,TSPTW)提出了一种基于磁场模型的蚁群变异算法(MFM-ACOMF).它通过修正传统蚁群算法的启发函数,满足用户的时间需求,并降低算法陷入局部最优的可能性;在得到最终解后,通过变异策略对未达到时间窗标准的顾客节点进行优化.仿真实验结果表明:MFM-ACOMF算法与传统ACOM算法相比,在最优解质量和顾客满意率方面都有一定程度的提高.展开更多
文摘In this paper we applicate the Hungarian algorithm for assignment problem to solve traveling salesman problem. Tree examples of application of algorithm are included.
基金This research was supported by the National Key R&D Program of China(No.2019YFA0706500).
文摘With the increase of space debris,space debris removal has gradually become a major issue to address by worldwide space agencies.Multiple debris removal missions,in which multiple debris objects are removed in a single mission,are an economical approach to purify the space environment.Such missions can be considered typical time-dependent traveling salesman problems(TDTSPs).In this study,an intelligent global optimization algorithm called Timeline Club Optimization(TCO)is proposed to solve multiple debris removal missions of the TDTSP model.TCO adopts the traditional ant colony optimization(ACO)framework and replaces the pheromone matrix of the ACO with a new structure called the Timeline Club.The Timeline Club records which debris object to be removed next at a certain moment from elitist solutions and decides the probability criterion to generate debris sequences in new solutions.Two hypothetical scenarios,the Iridium-33 mission and the GTOC9 mission,are considered in this study.Simulation results show that TCO offers better performance than those of beam search,ant colony optimization,and the genetic algorithm in multiple debris removal missions of the TDTSP model.
基金This project is supported by National Natural Science Foundation of China (No.70372062, No.70572044)Program for New Century Excellent Talents in University of China (No.NCET-04-0240).
文摘Firstly an overview of the potential impact on work-in-process （WIP） and lead time is provided when transfer lot sizes are undifferentiated from processing lot sizes. Simple performance examples are compared to those from a shop with one-piece transfer lots. Next, a mathematical programming model for minimizing lead time in the mixed-model job shop is presented, in which one-piece transfer lots are used. Key factors affecting lead time are found by analyzing the sum of the longest setup time of individual items among the shared processes （SLST） and the longest processing time of individual items among processes （LPT）. And lead time can be minimized by cutting down the SLST and LPT. Reduction of the SLST is described as a traveling salesman problem （TSP）, and the minimum of the SLST is solved through job shop scheduling. Removing the bottleneck and leveling the production line optimize the LPT. If the number of items produced is small, the routings are relatively short, and items and facilities are changed infrequently, the optimal schedule will remain valid. Finally a brief example serves to illustrate the method.
文摘针对迭代局部搜索(iterated local search,ILS)算法求解旅游线路时间花费较长的问题,提出了一种ILS结合布谷鸟搜索(cuckoo search,CS)的优化算法,来优化旅游线路的时间花费。该算法首先根据相关目标和约束采用ILS算法求解旅游景点及初始旅游线路,然后在满足旅游景点时间窗约束及景点总数不变的情况下采用CS算法进一步最小化旅游线路的时间花费。该研究获得的线路更符合旅游习惯,并且旅游时间花费更少。通过Daminaos数据集和桂林景点数据集进行验证,结果表明该优化算法相比于仅使用ILS算法所规划出的旅游线路,平均时间花费减少8%,更符合用户旅游选择习惯。
文摘针对带有时间窗限制的旅行商问题(travelling salesman problem with time windows,TSPTW)提出了一种基于磁场模型的蚁群变异算法(MFM-ACOMF).它通过修正传统蚁群算法的启发函数,满足用户的时间需求,并降低算法陷入局部最优的可能性;在得到最终解后,通过变异策略对未达到时间窗标准的顾客节点进行优化.仿真实验结果表明:MFM-ACOMF算法与传统ACOM算法相比,在最优解质量和顾客满意率方面都有一定程度的提高.
