求解大规模CVRP问题的快速贪婪算法

为求解大规模具有能力约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP),提出了一种快速改进贪婪算法CVRP-IMGR。基于贪婪算法思想设计了求解CVRP问题的贪婪算法CVRP-GR,在此基础上进一步采用K-d tree法和Held Karp模型改进了CVRP-GR的求解速度和求解质量,从而得到CVRP-IMGR。CVRPIMGR的复杂度可以达到O(nlogn),能够快速求解大规模(顾客数量大于500)CVRP问题。为验证CVRP-IMGR的有效性,分别采用CVRP-GR、CVRP-IMGR和经典构建型算法Savings求解了当前24个最大规模的CVRP算例,结果表明:CVRP-IMGR的求解速度远快于复杂度为O(n2logn)的CVRP-GR和Savings;CVRP-IMGR对所有算例的求解质量优于CVRP-GR,并且对18个算例的求解质量优于Savings。     

免疫遗传算子改进单亲遗传算法的研究

比较传统遗传算法(TGA)和单亲遗传算法(PGA)的异同,进而论述了PGA主要算子的实施方法和现存问题即由于PGA各算子的随机性过强,难以避免算法的"早熟".为此引入具有强收敛性的免疫遗传算子(IG0),测试表明结合算法IGO-PGA改进了PGA的性能.根据对TSPLIB中3个TSP问题的求解精度和运行时间的比较得出结论TGA性能低于PGA和IGO-PGA;PGA运行时间短、但求解精度一般;IG0-PGA与PGA时间复杂度相似,而求解精度在3个算法中表现最高,解决130个点的TSP问题(chl30)求解误差低于O.05,生成的路径图具有研究应用价值.     

多目标条件风险值的一种求解方法

本文研究了多损失CVaR问题,给出了于置信水平α下的α-VaR损失值和α-CVaR损失值的概念.α-CVaR损失值刻画了证券组合x于置信水平α下的损失大于等于α-CVaR损失值条件下的损失函数的条件期望损失值.我们引入了相应的α-CVaR最小化问题(MCVaR),并证明了在一定条件下,可以通过求解较为容易求解的单目标问题(SCVAR)来得到(MCVaR)的Pareto有效解.     

协作车辆路径成本分摊问题的 B-T Shapley 方法

多个企业协作配送能显著地降低物流配送成本和减少尾气排放, 研究协作配送模型与成本分摊方法是亟需解决的关键问题.传统经典成本分摊方法需要计算所有子联盟的协作成本, 在本问题中等价于需要求解2N-1个 (N为企业数量) 复杂的车辆路径问题.本文建立了多方协作车辆路径问题模型, 分析了协作配送成本分摊问题的属性.基于经典的Shapley成本分摊方法, 提出了B-T (Binary Tree) Shapley近似方法, 不仅将成本分摊本身计算复杂度由O (N22N) 降为O (N2log2N) , 而且将需要求解的车辆路径问题数量由2N-1个锐减至2N-1个, 从而能够在合理时间内完成协作配送问题的成本分摊.通过求解算例和实际案例, 计算结果表明, B-T Shapley的耗时与Shapley方法相比几乎可以忽略不计, 更重要的是B-T Shapley与Shapley的成本分摊结果之间仅有细微的偏差, 其平均准确度可以达到95%左右.     

粒子群算法求解无能力约束生产批量计划问题

经典的粒子群优化算法是一个在连续的定义域内搜索数值函数极值的有效方法.目前,粒子群算法(particle swarm optimization,PS0)已经成为优化领域中的一个重要的优化工具,其应用在很多优化问题中都可以见到.虽然粒子群算法的应用范围已经十分广泛,但是关于应用其求解多级生产批量计划问题(multilevel lot-sizing problem,MLLs)的文章并不多见.文章提出结合遗传算法(genetic algorithm,GA)变异算子的混合粒子群优化算法(hybrid particle swarm optimizatjon,HPSO)求解无能力约束装配结构MLLS问题.通过实验验证了算法的可行性和有效性.     

依托平台协作配送成本分摊的有效方法研究

依托平台的协作配送问题,在合理时间内有效计算公平成本分摊方案至关重要.核仁解是公认的公平分摊方案,但需要通过复杂的优化计算.提出了一个能通过公式近似快速计算核仁解的方法,发现任意满足总体理性分摊方案x的2~n-1(n为大联盟N中成员数)个子联盟S(S为N的子集)的满意度e(S, x)之和为常数,且不同x对应的任意子联盟S与互补联盟NS的满意度之和,即L_S=e(S, x)+e(NS, x)为常数.基于子联盟满意度越均衡,分配方案越合理的准则,构造了分配方案x对应的所有子联盟满意度均衡量化函数f(x)=∑[e(S, x)-0.5L_S]~2.显然,f越小表示子联盟满意度越均衡.证明了存在分配方案x*使f取到极小值,且x~*满足总体理性、唯一性、可加性、策略等价相对不变性、一致性、匿名性和可比性等众多分摊方案合理属性.最后,采用文章所提方法和核仁解求解方法,计算了诸多已有文献中的成本分摊算例,求解结果表明文章提出的方法计算速度比传统核仁解求解方法快数万倍以上,与最新求解核仁解及Shapley值的有效算法相比也具有明显的性能优势,且求解结果与核仁解的结果平均偏差只有5%左右.更重要的是,提出的新方法本身具有科学内涵,可以应用于任何支付可转移的合作博弈成本分摊问题.     

基于改进差分进化算法的VRP-SDPTW研究

整合前向物流和逆向物流,提出带时间窗的同时送货和取货的车辆路径问题(VRP-SDPTW)的混合整数规划数学模型.首次提出改进的差分进化算法(IDE)求解该问题,算法对不可行解设计惩罚机制,当基因值超过规定的范围时,设计基于整数序规范的辅助算子解决变异问题,设计一种随进化代数自动更新的交叉率.数值实验表明,改进的差分进化算法能有效地求解VRP-SDPTW.     

钢铁企业内部能源供应物流的优化研究

在供应链的物流管理思想[1]基础上,为实现钢铁企业内部能源的优化分配,根据RLP(resource level problem)与RCPSP(resource-constrained project scheduling problem)的相似之处和自身的特点以及针对实际问题结构和特征,提出资源有限的弱资源水平问题这一新概念;设计了一种求解弱RLP(soft resourcelevel problem)的方法;最后举例进行了验证.     

环状区域的车辆路径方案生成系统及优化模型

针对顾客满足环状区域分布的车辆路径问题(VRP),以大幅度地缩减问题求解的状态空间为突破口,引入人工智能和运筹学理论,提出求解这类特殊车辆路径问题的两阶段方法.第1阶段考虑行车时间和车载容量,提出带有控制策略的深度优先搜索算法自动生成备选的车辆路径方案集合.第2阶段将此备选方案集合归结为整数规划模型.采用VB6.0编程语言构建了车辆路径方案生成系统,并实现该系统与运筹学求解软件lindo的集成.通过案例验证了上述方法及自动求解系统的有效性.该项研究为解决环状配送区域的车辆路径问题这一难题提供了新方法.     

基于几何规划的两级供应链生产与定价联合优化

针对单一制造商和单一零售商的供应链,分析了在弹性需求D(p)=αp-k(k>1)下,市场定价、订货批量及生产批量三者的联合优化问题.由于一般供应链决策模型是高度非线性的,难以运用传统的非线性规划方法求解,所以提出了基于几何规划的求解思路,对任意的k>1,给出了分散决策和联合决策模型的一般求解方法.最后,通过一个算例验证了求解方法的正确性,同时也验证了联合决策不但能改善供应链整体效益,也能提高社会效用.