基于仿真的遗传算法求解动态旅行商问题

以标准旅行商问题的扩展问题--动态旅行商问题为对象,分析了动态旅行商问题中由于道路流量实时变化所引起的标准旅行商问题的数学建模与优化求解的问题复杂性.通过建立其计算机仿真模型再现动态旅行商问题中众多复杂的非平稳、随机因子.进而提出了基于计算机仿真模型的遗传算法,即根据计算机仿真的结果,应用改造后的遗传算法搜索原问题的优化解.最后,在多智能体仿真平台上实现该优化算法,并以此求解20个城市的动态旅行商问题,计算结果验证了算法的有效性.     

时变网络环境下旅行商问题研究

对时变旅行商问题进行描述,提出处理一般跨时段的新方法,并建立数学模型.在求解方法上构造动态搜索优化算法ds-k-opt(k=2,2.5,3)求解该问题.通过实验仿真,大部分动态搜索优化算法解质量优于动态规划启发式算法,且求解规模更大.动态搜索优化算法解随k值增大而更优,算法运行时间也随之增加.     

机载公共设备综合管理系统的动态反馈调度

机载公共设备的综合管理是一种必然趋势,多处理机任务分配和调度是机载公共设备综合管理系统中一个关键技术问题.针对混合任务和不确定的负载,设计动态反馈调度算法使之具有检测、分类、自适应、反馈的功能,采用静态分配和动态调度相结合的方法、局部反馈和全局反馈调度相结合的方法,实现多处理机欠载、过载、超过载、优先级倒置、任务接收和任务拒绝情况下的动态调度.     

基于解均匀度的车辆路径问题的自适应蚁群算法

蚁群算法是一种新型的模拟进化算法，具有许多优良的性质，可以很好地解决旅行商问题(Traveling Salesman Problem，TSP)，但同时也存在计算时间长、易出现停滞等缺陷。在分析车辆路径问题(Vehicle Roulting Problem，VRP)与TSP区别的基础上，将蚁群算法应用于VRP的求解，通过引入解均匀度、选择窗口以及吸引力等概念对算法的转移策略和更新策略进行改进，构造了具有自适应功能的蚁群算法。实验仿真结果表明所设计的算法具有很强的搜索能力，计算效率较高，能够有效地解决加速收敛与停滞现象之间的矛盾。     

生产系统的产品再设计策略

为研究在单一产品生产环境中产品再设计对价值、成本和质量管理有关问题的影响,提出了一个动态规划模型,该模型可以确定企业最优的产品再设计程度和实施再设计的最优时间,这样能使累积的净产品价值最大化．该模型可以使用不同的学习率和不同的成本数据进行计算,最后的结果表明,早期实施最优产品再设计策略提高了产品的累积净价值．     

预知信息和有限运载能力下应急车辆路径选择问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法,分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善.     

一类多旅行商问题的计算及仿真分析

旅行售货商问题(TSP)是组合优化领域的经典问题之一,而考虑多个旅行商的多旅行商问题(MTSP)是经典的旅行商问题的扩展.多旅行商问题的特点使其符合许多实际问题,并且通过对多旅行商问题加入约束条件可以使其转化为车辆选择问题(VRPs).针对一类特殊的MTSP问题采用Lin-Kernighan算法进行求解分析,并在此基础之上针对访问城市数目均衡的多旅行商问题采用两阶段方法进行求解,计算仿真结果是令人满意的.     

O2O模式下的配送车辆实时取送货路径选择问题

伴随020模式下外卖市场的迅猛发展,由此导致的最后3公里配送需求日益激增,外卖的配送时效受到了广泛的关注.外卖的及时配送,即配送车辆的路径选择问题成为餐饮服务业重要的研究问题.针对020平台外卖配送服务过程中,需求无法确定和配送车辆必须返回原点取货的情形,提出了带有取送货的在线旅行商问题(traveling salesman problem, TSP).分析了该问题在正半轴和一般网络上的下界,针对需求点仅在正半轴上的情形设计了TAIB算法,针对需求点在一般网络上设计了IGNORE算法,并进一步分析了两个算法的竞争性能,结论可以为现实中外卖配送车辆的实时调度决策提供依据.     

动态规划启发式算法求解时变车辆调度问题

时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关, 还与所处的时段有关. 对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法, 直接推导出跨时段对应的车辆行驶时间. 在此基础上建立了数学模型, 并构造动态规划启发式算法进行求解. 该算法能够通过设置参数H平衡求解质量和运行时间. 通过对10组随机产生的数据进行测试, 结果表明动态规划启发式算法能够在很短时间内改进最近邻算法. 当H=2时, 求解质量改进11%, 平均运算时间为1.34秒; 当H=3时, 在不到2秒的运算时间内求解质量改进17%.     

应急系统调度问题的模糊规划方法

应急系统调度问题通常仅把“应急时间最短”作为系统的优化目标,易导致出救点数目较大的情况,无论从系统的稳定可靠性还是费用考虑,这种提发生是极其不利的,针对这一特点,提出了基于“时间最短”,“出救点数目最少”的多目标数学模型,考虑决策者偏好的模糊性,本文采用模糊规划的思想方法处理该问题,并给出了相应的求解算法,算例及实际运用令人满意。     

“红包车”机制下的共享单车调度问题

共享单车具有随取随放的优点,但用户的租还车使站点之间经常出现供需不平衡现象.为了有效缓解运营商调度压力,提出了一种顾客参与调度的共享单车调度方式.将某些闲置的共享单车设置为红包车,鼓励用户将红包车骑到需求旺盛的区域,用户完成调度后可以获得红包奖励.以运营商运输成本,红包奖励支出以及未满足站点需求的惩罚成本最小为目标建立了混合整数规划模型,并设计了混合禁忌搜索算法对模型进行了求解.数值实验表明:红包车机制可有效减少运营商总成本;混合禁忌搜索算法可以有效求解大规模问题.     

具有服务时长的在线TSP问题

针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据.     

基于递阶遗传算法的一类多旅行商问题优化

针对最小化单个旅行商路程的多旅行商问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

基于预知信息和实时服务选择的在线TSP问题

现实生活中,提供外送服务的快餐店为了降低成本、提高效率,在接到顾客的订餐信息时,可能会因为距离等因素拒绝一些顾客的送餐要求,而拒绝顾客需求会带来一定的惩罚(如丧失部分客户).针对快餐店选择性提供送餐服务,同时送餐点信息被提前获知但是不能马上被服务的情形,提出了基于预知信息和实时服务选择的在线旅行商问题(traveling salesman problem,TSP).针对需求点在正半轴和直线上的情形分析了问题的下界,并设计了相应的算法,同时分析了每个算法的竞争性能.结果表明,算法的竞争性能会随着预知信息的增加而得到改善.     

求解TSP问题的最近邻域与插入混合算法

研究了求解旅行商问题(TSP)的构建型启发式算法中的最近邻域算法和插入算法的特点, 集最近邻域算法求解速度快、插入算法求解质量高的优点, 提出了一种最近邻域与插入混合算法. 分析了混合算法的合理性、复杂度及参数取值, 并分别采用以上三种算法求解了TSPLIB标准库中多个算例, 结果表明混合算法的求解速度接近最近邻域算法, 对城市数量小于1000的小规模TSP问题的求解质量与插入算法相当, 而对大规模TSP问题的求解质量明显优于插入算法.     

基于信息素递减的蚁群算法

通过对蚂蚁巡游路径的分析,发现经典蚁群算法在解决旅行商问题(TravelingSalesmanProblem,TSP)时的缺陷,在此基础上给出了新的信息素更新公式,提出了基于信息素递减的蚁群算法。新算法避免了蚂蚁在寻找最优解的过程中,由于禁忌表元素的逐渐增加而限制蚂蚁巡游路径选择的缺点,减少了巡游后期信息素对于后继蚂蚁的影响,提高了后继蚂蚁的巡游质量。通过具体的算例分析,表明此算法比传统的蚁群优化算法(AntColonyOptimization,ACO)算法有更快的收敛速度和非常好的稳定性。