返回
类型 综合研究 预答辩日期 2017-10-27
开始(开题)日期 2015-12-17 论文结束日期 2017-09-04
地点 自动化学院教育部重点实验室 论文选题来源 国家自然科学基金项目     论文字数 6.5 (万字)
题目 着色旅行商问题及其动态化研究
主题词 着色旅行商问题,动态优化,进化算法,元启发优化算法
摘要 课题组由多横梁水切割系统的调度问题出发,提出了一般性的着色旅行商问题(Colored Traveling Salesman Problem,CTSP)。该问题通过引入颜色来表现个体城市对于不同旅行商的访问允许性的差异,实现了对现有TSP、MTSP的泛化。CTSP可广泛适用于现实世界中存在多任务、访问差别化情形的优化调度问题(静态)的描述与建模,如多机工程系统的调度问题。为使CTSP更具有一般性、更加系统,本文拟在先前星型CTSP(Radial CTSP)的成果基础上,进一步提出并研究连环CTSP、通用CTSP与两类动态CTSP的建模与求解方法。主要研究内容与工作如下: 1)厘清了星型CTSP与MTSP、TSP的区别与联系。首先理论上证明了星型CTSP是对MTSP、TSP的泛化。接着,从模型与解空间角度上入手,分析证明星型CTSP并非MTSP与TSP的组合,而是对两者组合问题的泛化。同时,以工业实例和仿真实验为手段,量化证实了星型CTSP相比MTSP与TSP组合问题的求解优势。 2)在星型CTSP的理论基础上,提出连环CTSP(Serial CTSP),其各个旅行商均拥有专属城市集,且两两相邻的旅行商共享一个城市集。可用于建模作用域呈串行(局部)重叠的多机系统的作业调度问题。相应地,提出了连环CTSP的种群增量学习(Population-Based Incremental Learning,PBIL)求解算法。大量仿真实验结果表明,PBIL算法是求解连环CTSP的有效算法,在解质量、收敛速度和计算耗时方面优于先前提出的3种改进的遗传算法,即贪婪遗传算法、爬山遗传算法和模拟退火遗传算法。 3)鉴于星型和连环CTSP的城市颜色模式过于单调,无法描述加工任务对执行个体的访问允许性更为复杂的作业调度问题,提出通用CTSP(General CTSP),它通过引入城市-颜色矩阵,将星型CTSP和连环CTSP统一泛化,可广泛适用个体任务不仅存在访问差异而且差异具有多样性的一大类优化调度问题。提出通用CTSP的变邻域搜索(Variable Neighborhood Search,VNS)求解算法,采用了无冗余的高效的直接编码方式,并通过两阶段贪婪初始化和局部2-OPT操作增强算法的局部搜索能力。大量仿真实验结果表明,VNS算法是求解通用CTSP的有效算法,在解质量、收敛速度和计算耗时方面全面优于先前提出的3种遗传算法和PBIL算法。 4)以通用CTSP为基础,提出两类动态CTSP,即城市边权重时变和城市颜色时变。分别适用于建模一类客户需求差异化的运输成本动态变化的物流配送优化问题和一类多仓库电商的供货决策问题。提出这两类动态CTSP的新型VNS求解算法,算法采纳了多种群策略和种群迁移策略,分别用于增强算法的种群多样性和收敛性速度,以便快速适应动态变化的环境,有效跟踪最优解的变化。设计了两个相对应的动态环境仿真器来模拟两类CTSP的环境动态变化,并提出了算法性能评价标准,包括离线性能指标、动态运行曲线及解的标准方差。大量仿真实验结果表明,带贪婪初始化和优势种群迁移策略的VNS算法是求解这两类动态CTSP的有效算法,相比VNS、贪婪初始化VNS和带优势种群迁移VNS按性能评价标准更优。
英文题目 A COLORED TRAVELING SALESMAN PROBLEM AND ITS DYNAMICS PROBLEM
英文主题词 Colored Traveling Salesman Problem, dynamic optimization, path optimization, evolutionary algorithm, metaheuristic
英文摘要 Based on the scheduling problem of multi–bridge waterjet cutting system, a general Colored Traveling Salesman Problem (CTSP) is proposed. It is a generalization of the existing Traveling Salesman Problem (TSP) and Mutiple Traveling Salesman Problem (MTSP) and innovatively introduces the colors to describe the accessibility difference of cities to all salesmen. It can be widely applied to the description and modeling of the optimal static scheduling problem which owns the multi tasks with different accessibilities in the real world, such as multi-machine scheduling problem. To generalize and systematize CTSP, this dissertation proposes a serial CTSP (S-CTSP), a general-CTSP (G-CTSP), two kinds of dynamic CTSPs, and their solution methods, derived from the prior radial CTSP (R-CTSP). The main research contents and work are as follows: 1) This work clarifies the differences and relations among R-CTSP, MTSP and TSP. First, R-CTSP is proved to be the generalization of MTSP and TSP, in theory. Second, from the aspects of models and solution spaces, we confrim that R-CTSP is not the combination of MTSP and TSP, but their generalizations. In addition, with the help of an industrial examples and extensive simulation experiments, R-CTSP is comfirmed to be superior to the combinatorial problem of MTSP and TSP in solving. 2) Based on R-CTSP, an S-CTSP is proposed in this work. Each of its salesmen has some exclusive cities and shares some cities with its neighbor(s) in a serial manner. It can be used to model the scheduling problem of multimachine engineering systems whose machines are arranged serially with partially overlapped workspaces. Accordingly, a population-based incremental learning (PBIL) approach is presented to solve it. Extensive simulation is conducted and the results show that the proposed PBIL is effective and well outperforms three prior genetic algorithms (GA) presented by us, i.e., GA with greedy initialization, hill-climbing GA, and simulated annealing GA, in terms of solution quality, time consumption, and convergence rate. 3) A general CTSP (G-CTSP) is proposed, where a city color matrix is introduced to describe the accessibility difference of cities to the salesmen. It can be applied to a large class of scheduling problems in which individual tasks have different and diversitified accessibilities. A metaheuristic called variable neighborhood search (VNS) is proposed to address G-CTSP. It exploits an efficient direct-route coding that does not yield duplicated solutions. Then, a two-stage greedy algorithm and a 2-opt method are adopted to achieve powerful local search ability. The results of extensive simulation show that VNS is effective for CTSP and it outperforms greedy initialized GA, hill-climbing GA, simulated annealing GA, and PBIL, with respect to solution quality, time consumption, and convergence rate. 4) Based on the general CTSP, two kinds of dynamic CTSP (DCTSP) are proposed, namely, CTSP with varying edge weights (CTSP-VEW) and CTSP with varying city colors (CTSP-VCC). They can be applied to dynamic routing problems of logistics distribution system with various accessibilities of goods to different types of vehicles and supply decision problem of the multi-warehouses online retailers with the varying supply, respectively. A VNS algorithm is proposed to address CTSP-VEW and CTSP-VCC. It adopts multi-population strategy and population immigration strategy to enhance its population diversity and promote convergence speed of the algorithm in the dynamic environments, respectively. Two dynamic environment simulators are designed for simulating the environment changes of the two DCTSPs, and several evaluation criteria of algorithm performance are designed, including off-line performance, dynamic performance curve and standard deviation of solutions. The results of extensive simulation show that the greedy-initialization VNS with the best population immigrant scheme is the best approach for CTSP-VEW and CTSP-VCC, among VNS, greedy-initialization VNS, and VNS with the best population immigrant scheme, in terms of the proposed evaluation criteria.
学术讨论
主办单位时间地点报告人报告主题
自动化学院 20160920 教育部重点实验室会议室 周翔教授 Dynamic Inventory Management with Total Minimum Order Commitments and Two Supply Options
自动化学院 20160930 教育部重点实验室会议室 赵千川教授 物联网及其楼宇控制应用初探
自动化学院 20150526 教育部重点实验室会议室 Prof. Haibo He Adaptive Learning and Optimization for Machine Intelligence: From the Foundations to Complex Systems
自动化学院 20141110 教育部重点实验室会议室 Dr. Stanley B. Gershwin Flow Line Design: Optimal Simultaneous Machine Selection and Buffer Sizing
李俊老师课题组 20140618 中心楼403 孟祥虎 三横梁水刀切割的路径优化
李俊老师课题组 20150226 中心楼403 孟祥虎 CTSP求解策略的对比研究
李俊老师课题组 20160710 中心楼403 孟祥虎 求解CTSP的变邻域搜索算法
李俊老师课题组 20170208 中心楼403 孟祥虎 Dynamic CTSP
     
学术会议
会议名称时间地点本人报告本人报告题目
IEEE ICNSC 2014 20140417 美国迈阿密 Improved Population-Based Incremental Learning Algorithm for Vehicle Routing Problems with Soft Time Windows
中国自动化学会网络信息服务专业委员会 20160825 上海 动态着色旅行商的研究方法
     
代表作
论文名称
Variable Neighborhood Search for a Colored Traveling Salesman Problem
Population-Based Incremental Learning Algorithm for a Serial Colored Traveling Salesman Problem
 
答辩委员会组成信息
姓名职称导师类别工作单位是否主席备注
周献中 正高 博导 南京大学
徐贵力 正高 教授 博导 南京航空航天大学
严洪森 正高 教授 博导 东南大学
陈夕松 正高 教授 硕导 东南大学
何勇 正高 教授 博导 东南大学
      
答辩秘书信息
姓名职称工作单位备注
窦建平 副高 副教授 东南大学