智能制造环境下的备件生产与运输协同调度问题研究

智能制造和即时配送环境下的备件生产与运输协同调度问题是目前国内研究的一大热点,这是因为备件供应链响应速度已成为当前备件制造企业赢得客户的关键因素。为了提高客户满意度,尽可能缩短从客户下达定制化生产订单到订单配送完成的时间,本文建立了以所有客户总等待时间最短为目标的混合整数规划模型和集合覆盖模型,推导了最优解性质,并设计改进的分支定价算法求得最优解。通过将小规模算例结果与CPLEX进行对比,验证了模型和算法的有效性。多组算例测试结果表明,所提出的模型和算法可以有效提升智能制造环境下的备件供应链运作效率。     

选址-库存-路径问题模型及其集成优化算法

设施选址、库存控制和车辆路径安排是物流系统优化中的三个关键问题,三者之间存在相互依赖的关系,应该根据这种关系来相应地进行综合优化与管理物流活动。以典型的单一生产基地、单一产品、采用不断审查的(Q, r)库存策略的供应链二级分销网络为研究对象,建立了一个随机型选址-库存-路径问题优化模型;在将非线性混合整数规划转化为线性整数集合覆盖模型的基础上,采用列生成算法来获得一个近似最优解,再用分支定价法对初始解进行改进,以实现对整个问题“完全集成”的优化。最后,用随机生成的方式,产生了10至160个客户的计算实例,分析了运输费用和库存费用对总成本的影响,算法运算时间表明本文给出的算法能较快地求解这一复杂问题。     

基于动态服务网络的铁路紧急输送计划编制模型和算法

根据特殊条件下铁路输送计划问题的动态性、多目标性、时效性等特点,采用时空网络构建铁路输送计划网络模型.并建立了基于动态路径的铁路输送计划编制数学模型.模型属于大规模的整数规划,以追求时间效益最大化和灾害损失最小化为目标.根据模型的特点,提出了松弛求解算法,借助LINGO求解工具求解松弛模型,通过逐步固定变量为整数值求得最优解.算例研究表明,算法可行有效.     

基于动态服务网络的铁路紧急输送计划编制模型和算法北大核心

根据特殊条件下铁路输送计划问题的动态性、多目标性、时效性等特点,采用时空网络构建铁路输送计划网络模型.并建立了基于动态路径的铁路输送计划编制数学模型.模型属于大规模的整数规划,以追求时间效益最大化和灾害损失最小化为目标.根据模型的特点,提出了松弛求解算法,借助LINGO求解工具求解松弛模型,通过逐步固定变量为整数值求得最优解.算例研究表明,算法可行有效.     

一类特殊二维0-1规划的广义指派模型求解

二维0-1整数规划模型应用广泛,对广义指派问题的研究,解决了一些二维0-1整数规划问题.但有些实际问题具有特殊上限约束,目前还没有对应的方法.针对该实际情形,本文建立了相应的数学模型,利用对指派模型的推广,求得问题最优解,从理论上解决了这一类特殊约束二维0-1整数规划的最优解求取问题.并通过算例说明了方法的使用.     

平行机排序问题的列生成解法

基于整数规划的线性松弛,探讨求解大规模带权总完工时间排序问题的列生成算法的基本原理.然后,结合动态规划和分枝定界技术,对大规模排序问题P‖∑wiCj提出一类求解精确(最优)解的列生成算法.     

不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

多周期公用工程系统运行的模型,优化方法与应用

针对多周期公用工程系统的运行优化问题，考虑了设备的启停费用的情况下。建立了混合整数非线性规划模型并证明了最优解的存在性。针对该运行优化问题本将其分解成若干子问题，然后利用改进的Hooke-Jeeves优化算法求解每个子问题。应用于具体实例，其数值结果与其它方法得到的相比。运行时间短，且更适合多周期公用工程问题的求解。     

分支定界算法求解带有释放时间的单机双代理调度问题

本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。     

柔性制造系统的载荷模型和对偶分解算法

本文研究柔性制造系统最优排序问题的载荷模型，通过优化系统的最优利用率并考虑系统各机器的工作平衡，本文给出了载荷问题三个新的优化模型，这些模型形成具有０－１变量和一般整型变量的大规模整数规划问题，根据分解理论，考虑到问题的变量特性，这些大规模问题可被分解成若干维数较低的子问题求解，文章还给出了一个对偶分解算法。     

最小连通顶点覆盖问题的降阶回溯算法

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。     

考虑充电设施重入的电动汽车旅行商问题研究

出于减少环境危害和响应相关法规的考虑,物流企业开始逐步将运输车辆转变为电动汽车;而由于电动汽车的续航里程有限,对电动汽车的路径优化也将涉及充电设施。充电设施的“重入”是指电动汽车返回之前已经通过的充电设施进行充能的现象,它的存在需要改变经典旅行商问题模型中的“子回路约束”。本文聚焦于充电设施的“重入”,构建了一个无需预估充电设施重入次数上限的电动汽车旅行商问题模型,并通过引入路径可行性判别方法和增加充电设施选择与重复策略,设计了一种改进蚁群算法对问题进行求解。结果表明:与未考虑重入的模型相比,本文提出的考虑充电设施重入的模型能在电动汽车电池容量较低的情况下求出最优解,同时也能够使充电设施承担多次充电任务,从而在较少充电设施情况下依然能够得到可行的最优路径。     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

竞争市场均衡问题的内点算法

本文应用最优化方法求解经济学中的经典问题-竞争市场均衡问题.本文对Ye的算法(Ye首先提出了解Fisher问题的原始-对偶路径跟踪算法)做了改进,分别给出了步长调整和迭代方向分解后的原始-对偶路径跟踪算法,并对算法做了理论证明和复杂性分析.最后分析了初始点的求法,做了初步的数值计算.计算结果表明算法能在有效时间内求得问题的解.     

基于两阶段启发式算法的物流配送选址-路径问题研究

为了解决配送中心选址与带时间窗的多中心车辆路径优化组合决策问题,利用双层规划法建立了配送中心选址与车辆路径安排的多目标整数规划模型,针对该模型的特点,采用两阶段启发式算法进行了求解。首先,通过基于聚集度的启发式算法对客户进行分类,确定了备选配送中心的服务范围;然后,基于双层规划法,以配送中心选址成本最小作为上层规划目标,以车辆配送成本最小作为下层规划目标,建立了多目标整数规划模型;最后,利用改进的蚁群算法进行了求解。通过分析实例数据和Barreto Benchmark算例的实验结果,验证了该模型的有效性和可行性。     

军事定向越野路径优化问题建模及混合蚁群算法求解

军事定向越野运动中存在点位多、分布散、时间紧、得分要求高等条件,为在规定时间内找到一条得分高的行进线路,找到衡量和分析运动成绩好坏的标准,文中对军事定向越野中的路径优化问题进行了深入分析,建立了混合整数规划模型,设计了一种混合蚁群算法。算法中,首先由改进蚁群算法找到初始解,然后再利用选择、交叉和变异算子进行解的优化,通过仿真实验和算法对比验证了混合蚁群算法的可行性和优越性。     

基于最优D.C.分解的单二次约束非凸二次规划精确算法

本文提出一种基于最优D.C.分解的单二次约束非凸二次规划精确算法.本文首先对非凸二次日标函数进行D.C.分解,然后对D.C.分解中凹的部分进行线性下逼近得到一个凸二次松弛问题.本文证明了最优D.C.分解可通过求解一个半定规划问题得到,而原问题的最优解可以通过计算最优凸二次松弛问题的满足某种互补条件的解得到.最后,本文报告了初步数值计算结果.     

一种大规模规划的分解——调协解法

将一个大的主问题分解成若干个小的子问题,一方面对子问题寻优,一方面逐步调整主问题与子问题之间、子问题与子问题之间的关系,最后达到主问题最优,这就是解大规模规划问题的主要手段之一——分解-调协法。本文将一个大规模规划问题分解成由若干个子规划组成的多目标规划的序列,并在后一问题的解集合序列上求出前一问题的最     

重大事故规避的危险品运输车辆路径优化研究

基于重大事故规避的思想,建立以最大事故后果最小及运输成本最小为双目标,且事故后果基于实时装载量的危险品运输车辆路径优化模型。基于ε-约束法,设计可求得帕累托最优解的精确算法,该算法包含通过性质求ε下界、规避被支配解的预处理及不可行路径禁止约束3处改进。进一步设计处理大规模问题的多项式时间近似算法,并分析了算法的近似比。最后通过算例对模型和算法进行测试,并通过出灵敏度分析给出管理启示。     

校园最佳游览路线问题的数学模型分析

将某高校的校园示意图转化为赋权连通图，求得该连通图的邻接矩阵，利用Floyd算法及图论软件包构造一个最短路径矩阵，得到一个赋权完全图，将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题，建立混合整数线性规划模型，并利用优化软件求得最优解．从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题．