基于求解TSP问题的双向扩展差额算法

旅行商(TSP)问题是典型的组合优化中的NP-hard难题.本文在最近城市搜索法和两端延伸最近城市搜索法基础上提出了双向扩展差额求解算法,并分析了算法的复杂度.采用以上三种算法求解了TSPLIB标准库中多个算例,比较结果表明本算法能够更快的找到更优的方案,具有更好的综合性能.     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

碳中和视角下奖惩机制对逆向供应链碳减排与回收价格的影响

近年来,促进废弃电器电子产品回收行业健康发展,减少碳排放助力实现碳中和目标受到各界的重点关注。本文针对制造商、电商平台、第三方回收商等多个主体构成的逆向回收供应链,探讨碳限额政策与政府补贴奖惩机制并行下对逆向供应链废弃电器电子产品的回收量、回收价格、碳排放量、碳减排努力的影响,构建四种不同回收模式利润模型,得到不同回收模式下的最优回收价格和减排率,分析碳限额、消费者回收渠道偏好、拆解成本、碳交易价格、产品再制造比率对回收价格和碳排放量的影响。结果表明:消费者渠道偏好会影响回收价格和制造商碳减排率;针对污染型产品,政府应采取高的碳价格对制造商进行惩罚;此外政府政策是把双刃剑,政府补贴既可以提高企业碳减排率,同时也增加了逆向供应链总的碳排放量,且政府补贴对双渠道回收模式有更明显的减排作用。     

基尼系数计算方法新思考

一、基尼系数及其计算方法(一)基尼系数基尼系数是意大利经济学家科拉多·基尼(Corrado·Gini)1912年在洛伦茨曲线(Lorrenz)的基础上提出的,1905年统计学家马克斯·洛伦茨(Max·Lorrenz)利用累计百分数曲线,作为检定社会收入或财富分配不均等程度的方法,后人就称这种曲线为洛伦茨曲线。     

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

依托平台的协作配送问题,在合理时间内有效计算公平成本分摊方案至关重要.核仁解是公认的公平分摊方案,但需要通过复杂的优化计算.提出了一个能通过公式近似快速计算核仁解的方法,发现任意满足总体理性分摊方案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%左右.更重要的是,提出的新方法本身具有科学内涵,可以应用于任何支付可转移的合作博弈成本分摊问题.     

求解大规模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。     

协作车辆路径成本分摊问题的 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%左右.