Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering ...Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.展开更多
Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially ove...Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.展开更多
This research focuses on the home health care optimization problem that involves staff routing and scheduling problems.The considered problem is an extension of multiple travelling salesman problem.It consists of find...This research focuses on the home health care optimization problem that involves staff routing and scheduling problems.The considered problem is an extension of multiple travelling salesman problem.It consists of finding the shortest path for a set of caregivers visiting a set of patients at their homes in order to perform various tasks during a given horizon.Thus,a mixed-integer linear programming model is proposed to minimize the overall service time performed by all caregivers while respecting the workload balancing constraint.Nevertheless,when the time horizon become large,practical-sized instances become very difficult to solve in a reasonable computational time.Therefore,a new Learning Genetic Algorithm for mTSP(LGA-mTSP)is proposed to solve the problem.LGA-mTSP is composed of a new genetic algorithm for mTSP,combined with a learning approach,called learning curves.Learning refers to that caregivers’productivity increases as they gain more experience.Learning curves approach is considered as a way to save time and costs.Simulation results show the efficiency of the proposed approach and the impact of learning curve strategy to reduce service times.展开更多
A layout of the offshore wind farm(OSWF)plays a vital role in its capital cost of installation. One of the major contributions in the installation cost is electrical collector system(ECS). ECS includes: submarine cabl...A layout of the offshore wind farm(OSWF)plays a vital role in its capital cost of installation. One of the major contributions in the installation cost is electrical collector system(ECS). ECS includes: submarine cables,number of wind turbines(WTs), offshore platforms etc. By considering the above mentioned problem having an optimized design of OSWF provides the better feasibility in terms of economic considerations. This paper explains the methodology for optimized designing of ECS. The proposed methodology is based on combined elitist ant colony optimization and multiple travelling salesman problem.The objective is to minimize the length of submarine cable connected between WTs and to minimize the wake loss in the wind farm in order to reduce the cost of cable and cable power loss. The methodology is applied on North Hoyle and Horns Rev OSWFs connected with 30 and 80 WTs respectively and the results are presented.展开更多
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.展开更多
基金the Natural Science Basic Research Program of Shaanxi(2021JQ-368).
文摘Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.
基金supported in part by the National Natural Science Foundation of China(61773115,61374069,61374148)the Natural Science Foundation of Jiangsu Province(BK20161427)
文摘Multi-bridge machining systems(MBMS) have gained wide applications in industry due to their high production capacity and efficiency. They contain multiple bridge machines working in parallel within their partially overlapping workspaces.Their scheduling problems can be abstracted into a serial-colored travelling salesman problem in which each salesman has some exclusive cities and some cities shared with its neighbor(s). To solve it, we develop a greedy algorithm that selects a neighboring city satisfying proximity. The algorithm allows a salesman to select randomly its shared cities and runs accordingly many times. It can thus be used to solve job scheduling problems for MBMS. Subsequently, a collision-free scheduling method is proposed to address both job scheduling and collision resolution issues of MBMS. It is an extension of the greedy algorithm by introducing time window constraints and a collision resolution mechanism. Thus, the augmented greedy algorithm can try its best to select stepwise a job for an individual machine such that no time overlaps exist between it and the job sequence of the neighboring machine dealt in the corresponding overlapping workspace; and remove such a time overlap only when it is inevitable. Finally, we conduct a case study of a large triplebridge waterjet cutting system by applying the proposed method.
文摘This research focuses on the home health care optimization problem that involves staff routing and scheduling problems.The considered problem is an extension of multiple travelling salesman problem.It consists of finding the shortest path for a set of caregivers visiting a set of patients at their homes in order to perform various tasks during a given horizon.Thus,a mixed-integer linear programming model is proposed to minimize the overall service time performed by all caregivers while respecting the workload balancing constraint.Nevertheless,when the time horizon become large,practical-sized instances become very difficult to solve in a reasonable computational time.Therefore,a new Learning Genetic Algorithm for mTSP(LGA-mTSP)is proposed to solve the problem.LGA-mTSP is composed of a new genetic algorithm for mTSP,combined with a learning approach,called learning curves.Learning refers to that caregivers’productivity increases as they gain more experience.Learning curves approach is considered as a way to save time and costs.Simulation results show the efficiency of the proposed approach and the impact of learning curve strategy to reduce service times.
文摘A layout of the offshore wind farm(OSWF)plays a vital role in its capital cost of installation. One of the major contributions in the installation cost is electrical collector system(ECS). ECS includes: submarine cables,number of wind turbines(WTs), offshore platforms etc. By considering the above mentioned problem having an optimized design of OSWF provides the better feasibility in terms of economic considerations. This paper explains the methodology for optimized designing of ECS. The proposed methodology is based on combined elitist ant colony optimization and multiple travelling salesman problem.The objective is to minimize the length of submarine cable connected between WTs and to minimize the wake loss in the wind farm in order to reduce the cost of cable and cable power loss. The methodology is applied on North Hoyle and Horns Rev OSWFs connected with 30 and 80 WTs respectively and the results are presented.
基金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.
