运输问题时间优化算法

运输问题是线性规划中的一类特殊问题。适用于求解目标函数符合线性叠加关系的费用或距离问题,对于实际运输问题中的运输时间优化问题则难以给出优化解。本文结合科研实践提出了运输问题中有关时间优化的迭代算法模型,此模型可给出整体运输时间最优的运输方案。通过实际检验证明,此算法简便、稳定、计算结果符合实际情况。     

一类两层规划问题模糊满意解的遗传算法

在现有两层规划问题求解方法的基础上,提出用浮点数编码的遗传算法求解该问题模糊满意解的新方法．这种方法每次提供给决策者一组近似最优解,通过决策者的比较、评价和选择,在交互过程中得到各决策者都满意的解．该方法不仅可以给决策者提供更多的决策环境信息,而且可以适应决策者偏好的变化,使得决策过程更合理,更符合人的认识过程．     

Optimal Augmentation of a 2-Vertex-Connected Multigraph to a k-Edge-Connected and 3-Vertex-Connected Multigraph

Given an undirected multigraph G = (V, E) and two positive integers and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an -edge-connected and k-vertex-connected multigraph. In this paper, we show that the problem can be solved in Õ(mn²) time for any fixed and k = 3 if an input multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.     

动态用户最优配流问题的投影算法研究

本文首先建立了动态用户最优配流问题的变分不等式模型,并对此模型用投影算法来求解.本文中的模型满足Wordrop第一原理要求,所给算法在每一个小时段都能给出路段流入率、流出率及路段流量,从而为行人出行提供可靠的、实时的信息,所给数值实验也说明该模型和算法是可行且有效的.     

考虑最坏中断损失下的P-中位设施选址问题的模型与算法研究

蓄意突袭以及恐怖袭击会造成设施服务的突然中断成为网络系统的主要危害之一,因此网络设施选址决策应该同时考虑正常和紧急状态下系统的运作成本.本文研究考虑最坏中断损失下的网络设施选址问题,建立了该问题的双层规划模型,上层规划涉及设施选址决策,下层规划研究确定设施位置后,设施中断产生最大损失的问题.本文运用基于拉格朗日松弛的混合遗传算法来求解该双层规划问题.将European150数据集作为研究对象,对比研究了本文研究问题与传统的P-中位选址问题的结果,分析不同选址策略下网络系统的效率被中断影响的程度是不同的.最后通过改变一些关键参数,比如常规运作权重、设施数量、中断设施数量,对相关结果进行了分析.     

商品交易市场网络节点选址的双层规划模型——以安徽省砀山县为例

优化商品交易市场选址方法有利于提升城市规划布局模式,促进城市有序发展。在分析现有选址模型在应用时存在不足的基础上,采用双层规划模型构建了商品交易市场选址模型。上层规划从决策者的角度出发,通过考虑修建商品交易市场的总费用与购买者需求量之间的关系,以使总的收益最大。下层规划描述使用者的选择行为,对应于最大效用值选择商品交易市场。同时,针对所建模型,设计了启发式求解算法,并以安徽省砀山县为例进行初步应用验证。     

多模式交通条件下合理制定旅客票价的优化模型及算法

在本文中,充分考虑了旅客和交通管理部门两方面的利益,提出了一个双层规划模型来描述城市间多种交通方式竞争条件下合理制定旅客票价问题。在此模型中,既保障了旅客使自己的广义出行费用最小,又使得交通管理部门在客运市场的竞争中取得最大的经济效益。然后给出了求解该模型的基于灵敏度分析的启发式算法 (SAB)。最后用一个实际算例说明了该模型及算法的应用。     

及时条件下订货策略的优化模型及求解算法

在供应链管理中,兼顾供需双方的利益,采用合适的订购单价,订购批量及运送次数,供需双方都可以提高自己的利润。本文用双层规划模型描述了及时条件下的订货策略模型。然后阐述了用遗传算法求解该模型的基本思想,最后进行了算法设计并给出一个简单算例验证了本模型及其算法的可行性。     

一种费用与时间相关的GERT模型的解析求解研究

本文探讨了项目活动时间与费用之间的函数关系,在假定活动费用与时间线性相关的条件下,依据矩母函数和梅森公式,推导出互斥型GERT模型的解析算法,并给出了该算法的一个应用实例。     

有时间窗车辆路径问题的模型及其改进模拟退火算法研究

论文在对有时间窗车辆路径问题进行描述的基础上,建立了该问题的基于直观描述的数学模型.论文还根据有时间窗车辆路径问题的特点构造了求解该问题的改进模拟退火算法,并进行了实验计算.计算结果表明,用本文设计的改进模拟退火算法求解有时间窗车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定.     

随机旅行时间局内车辆路径问题的模型及其算法

人们在生活中会经常遇到随机旅行时间的局内车辆路径问题,如现实物流配送中的交通堵塞现象.文章在Laporte等的研究基础上,提出了一个考虑堵塞点动态产生、一个个遇到,堵塞时间为随机变量的模型,并构造了求解该模型的算法.     

经济批量排产问题的一种排产方法

针对经济批量排产问题假定生产可以在库存降为0之前开始,并且提出新的算法求产品的生产顺序。结果表明,该排产方法成本要低于其他2种常用的经济批量排产问题的方法,并且给出了算法的时间复杂性。     

基于双层规划的供应链二级分销网络优化设计模型

从供应链集成的角度出发,利用双层规划模型描述了二级分销网络优化问题,充分考虑了网络决策部门及客户双方的自身及共同利益。同时设计了启发式求解算法,最后用一简单实例验证了模型及其算法的有效性。     

一种考虑动态时间窗的满载问题模型及算法

针对时间约束在满载问题中的复杂性,建立了一个考虑装载时间和次序的具有动态时间窗的满载车辆调度模型,并给出了一个基于动态构造原理的启发式算法。该模型和算法改进了以往满载问题中对时间窗的考虑,使得求解更具有实际派车意义,并且该算法通过参数调整,经过少量迭代即可快速求得最小化总成本的满意解。     

弹性需求下网络设计问题和电子路票问题研究

应用双(二)层规划模型研究弹性需求下网络设计问题与电子路票收取问题,其中只考虑在部分路段进行路段能力扩充和收取电子路票.上层决策者(网络规划者)选择路段能力增加和收取电子路票的数量来获得最优的社会总福利.下层决策者(网络用户)选择路径来最小化他们的出行成本(路径出行时间与所付出电子路票的价值的和).应用下层规划问题的Ka-rush-Kuhn-Tucker(KKT)条件,将双层规划模型转化为单层规划模型.为了解决互补条件所造成的求解困难,本文构造了松弛算法进行求解,并用数值试验研究了模型和算法的可行性.数值结果表明,本文的模型在缓解交通拥挤方面可以得到更好的效果,而且只在部分路段进行路段能力扩充和收取电子路票更加方便实用.在可交易电子路票方案中,更多出行的用户需要购买电子路票来为他们的额外出行付费,而减少出行的用户则可以卖出多余电子路票得到补偿,同时电子路票的交易价格是在完全竞争的市场上形成的,因此本文中的可交易电子路票机制是收入中性的.     

O-D需求估计的双层规划模型及基于灵敏度分析的求解算法

本文在考虑三种交通模式 (一般机动车,公交车,自行车)的基础上,建立了一般拥挤网络多模式OD需求估计问题的双层规划模型,给出了一个基于灵敏度分析的启发式求解算法,并进行了数值试验。试验结果表明,本文所给的模型和算法不仅能较好地给出OD需求的估计值,而且同时还给出了各模式路段流量的估计值。     

三台平行机排序的一个复合半在线问题的算法

本文讨论一个三台平行机半在线排序问题.对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067.     

基于系统最优的城市公交专用道网络设计模型及算法

设置公交专用道是实现"公交优先"的重要手段,然而,专用道设置将改变不同交通方式的道路通行能力,进而影响交通网络的整体性能。本文试图提出一种基于系统最优思想的公交专用道网络设计方法,既保证出行者的利益,又能满足交通系统总费用最优的目标。首先,本文分析了公交专用道设置对公交车辆和社会车辆这两种交通方式道路通行能力的影响,基于经典的BPR函数,构造了考虑专用道设置的不同方式的路段阻抗函数。其次,分析了出行者在多方式交通网络中的模式选择和路径选择问题,采用用户平衡理论分析了城市多方式交通平衡配流问题,给出了相应的变分不等式模型。更进一步,采用双层规划方法构造了基于系统最优的城市公交专用道网络设计模型,该模型以交通网络总费用最小为优化目标,并考虑了不同交通方式的平衡流量约束,采用分支定界算法对该双层规划模型进行求解。最后,通过一个简单算例对模型及算法的可行性和有效性进行了分析和验证。     

求解大规模生产批量问题的启发式算法

企业资源优化模型是多物料、多层、受多种能力约束、有启动时间和启动成本的生产批量问题,该问题是NP完全问题,求解十分困难。为此我们提出了一个新的启发式方法,通过交互求解线性规划松弛问题并应用改进的Silver-Meal方法处理批量来近似求解生产批量问题,并第一次将影子价格引入Silver-Meal方法的批量决策,数值实验表明新算法在不同规模问题上的有较好的表现。     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.