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

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

生产和运输成本问题的机会约束规划方法

当供应商的生产能力和销售商的需求量是随机参数时,建立了一类产品生产和运输成本问题的数学模型,它是一种随机优化模型.利用机会约束规划方法研究了在给定置信水平和其它相关约束条件时,此类随机优化问题的确定型等价式.给出了每个供应商给每个销售商的送货量,且达到了总运输成本最低.实际案例研究表明所建立的模型和求解方法有效,且分析了不同置信水平下最优值的变化,提供了选择最佳置信水平的方法.     

求解硬时间窗约束下随机需求库存-路径问题的优化算法

随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem, SDIRP)即考虑随机需求环境下供应链中库存与配送的协调优化问题,是实施供应商管理库存策略过程中的关键所在,也是典型的NP难题之一。文章以具有硬时间窗约束的随机需求库存-路径问题(Stochastic Demand Inventory Routing Problem with Hard Time Windows, SDIRPHTW)为研究对象,将SDIRPHTW分解为直接配送的随机库存-路径问题和具有硬时间窗约束的路径优化问题两个子问题,并以最小化系统运行成本和用车数量为目标,设计了一个基于(s,S)库存策略和修正C-W节约法的启发式算法。最后,通过相应的数值算例验证了算法的有效性。     

基于混合智能算法的随机生产配料问题

配料问题是工业生产流程中的重要组成部分.在实际的生产过程中,配料问题由于原料的选取与某些随机系数有关,因而具有随机性.将基于随机理论提出一种新的机会约束生产配料模型,然后设计混合智能算法求解提出的生产配料模型.最后,给出一个数值例子表明模型和算法的有效性.     

模糊机会约束规划下的投资组合模型

资产的过去数据和专家对资产未来表现的判断是资产收益率的两个重要信息,本文用基于上述两个信息的可能性分布描述证券收益率的不确定性,结合可能性测度和必要性测度,建立了基于模糊机会约束规划的乐观型和悲观型投资组合模型,并且得到了各模型的最优解的解析式。最后给出了算例予以说明。     

带有回报率机会约束的报童问题

报童问题研究的是决策者利用随机优化方法确定最优订货量以使销售期末的期望利润最大.这种方法考察的是长期的平均意义上的最优,不能保证实际的收益较大,更不能保证实际的回报率比较大.本文研究了带有回报率机会约束的报童问题,通过该约束控制实际的回报率低于目标值的概率,数值例子表明该模型可以有效地控制实际的回报率偏低的风险,从而提高了报童模型的应用价值.     

成品油二次配送库存-路径优化模型与两阶段算法

针对随机需求下的成品油二次配送库存-路径优化问题,考虑各个加油站的存储容量限制,油罐车满隔舱装卸要求和一对多服务等特点,通过设置各个加油站的实际配送量为油罐车隔舱容量的整数倍,以总配送成本和期望损失之和最小化为目标,建立两阶段随机整数规划模型,并设计了多割L-shaped算法.进一步,基于多割L-shaped算法设计了求解大规模问题的两阶段方法,并引入两种改进策略加快多割L-shaped算法的收敛速度.最后利用不同规模的算例进行模拟计算,分别验证了改进多割L-shaped算法高效性和两阶段方法的快速有效性.相比其它算法,两阶段方法在求解大规模问题时的平均运行时间降低了31.34%,平均成本的Gap值不超过2.63%.文章的研究结果为制定成品油二次配送计划提供了决策依据和算法支持.     

模糊批量生产计划问题的机会约束规划

描述了模糊单位利润、模糊生产能力以及模糊需求下的批量生产计划,并应用模糊机会约束规划规划建立了模型.当模糊变量是梯形模糊数时,我们将模糊模型转化为确定意义下的模型.为了求解优化模型,我们设计了基于模糊模拟的遗传算法.最后,通过一个数值例子说明算法的有效性.     

以费用为独立变量的随机机会约束规划模型研究

美军提出的"以费用为独立变量(CAIV)"方法从论证阶段开始,就强调需求、性能与费用三者之间的平衡,并采用费用-效能综合权衡优化模型进行系统费用和性能参数的最优决策.但是该模型没有考虑采办过程中的不确定因素,且由于决策者往往很关心权衡结果中费用与性能的置信水平问题,因此提出要将采办中的不确定性因素作为随机变量引入权衡模型,建立一种综合权衡优化的随机机会约束规划模型,并进行了示例验证.     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题:     

第三方库存-路线问题的模型及混合遗传算法设计

根据第三方库存-路线问题的特点,以车辆租赁费用和运行费用之和为目标函数,不限制客户每次的配送量小于车辆容量,建立了满载运输和非满载运输混合的整数规划模型.针对第三方库存-路线问题的复杂性,本文设计嵌入禁忌搜索的遗传算法来同时决策库存和路线问题.首先对配送间隔进行编码,然后用禁忌搜索法计算每天需要配送的车辆路线问题.最后与其下界值进行比较,结果表明该算法是一个有效的算法,不但第三方能取得较低的运营总成本和较高的车辆利用率,而且也能为客户节约库存空间.     

蚂蚁算法在带时间窗车辆路径问题中的应用研究

蚂蚁算法是近年来新出现的一种随机型搜索寻优算法.自从在旅行商等著名问题中得到富有成效的应用之后,已引起人们越来越多的关注和重视.本文将这种新型的生物优化思想扩展到物流管理中的带时间窗车辆路径问题,从数值计算上探索了蚂蚁算法的优化能力,获得了满意的效果.     

A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands

We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand’s stochastic nature is incorporated into the pricing problem. Computational results are reported.     

需求可分的车辆路径问题模型与算法

需求可分的车辆路径问题(SDVRP)无论是从运输距离还是派车数量上,都可进一步优化传统的车辆路径问题。为了降低SDVRP的求解难度,本文在分析最优解性质的基础上,加强模型的约束条件,将原模型转变为等价的改进SDVRP,并在使用蚂蚁算法求解改进SDVRP模型的过程中,采用开发新路径和2-opt相结合的方法,以避免出现迭代停滞的现象。实验表明,算法计算结果稳定,最差解与最好解的偏差仅为1.80%。     

The C 3 Theorem and a D 2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification

This paper considers the two-stage stochastic integer programming problem, with an emphasis on instances in which integer variables appear in the second stage. Drawing heavily on the theory of disjunctive programming, we characterize convexifications of the second stage problem and develop a decomposition-based algorithm for the solution of such problems. In particular, we verify that problems with fixed recourse are characterized by scenario-dependent second stage convexifications that have a great deal in common. We refer to this characterization as the C³ (Common Cut Coefficients) Theorem. Based on the C³ Theorem, we develop a decomposition algorithm which we refer to as Disjunctive Decomposition (D²). In this new class of algorithms, we work with master and subproblems that result from convexifications of two coupled disjunctive programs. We show that when the second stage consists of 0-1 MILP problems, we can obtain accurate second stage objective function estimates after finitely many steps. This result implies the convergence of the D² algorithm.This research was funded by NSF grants DMII 9978780 and CISE 9975050.     

The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) consists of finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. While serving a particular customer, each vehicle picks up its demand and carries its weight throughout the rest of its route. While costs in the classical CVRP are measured in terms of a given arc distance, the Cumulative Vehicle Routing Problem (CmVRP) is a variant of the problem that aims to minimize total energy consumption. Each arc’s energy consumption is defined as the product of the arc distance by the weight accumulated since the beginning of the route.The purpose of this work is to propose several different formulations for the CmVRP and to study their Linear Programming (LP) relaxations. In particular, the goal is to study formulations based on combining an arc-item concept (that keeps track of whether a given customer has already been visited when traversing a specific arc) with another formulation from the recent literature, the Arc-Load formulation (that determines how much load goes through an arc).Both formulations have been studied independently before – the Arc-Item is very similar to a multi-commodity-flow formulation in Letchford and Salazar-González (2015) and the Arc-Load formulation has been studied in Fukasawa et al. (2016) – and their LP relaxations are incomparable. Nonetheless, we show that a formulation combining the two (called Arc-Item-Load) may lead to a significantly stronger LP relaxation, thereby indicating that the two formulations capture complementary aspects of the problem. In addition, we study how set partitioning based formulations can be combined with these formulations. We present computational experiments on several well-known benchmark instances that highlight the advantages and drawbacks of the LP relaxation of each formulation and point to potential avenues of future research.     

强Guass-seidel法求解有限元模型修正问题

有限元模型修正是一类特殊的二次反特征值问题．我们将有限元模型修正看成二次规划问题来解决,并采用非线性Gauss－Seidel方法来求解其相应的Lagrange对偶函数．最后,给山的数值文验说明方法的有效性．     

Simulated Annealing and Genetic Algorithms for the Facility Layout Problem: A Survey

The facility layout problem (FLP) has many practical applications and is known to be NP-hard. During recent decades exact and heuristic approaches have been proposed in the literature to solve FLPs. In this paper we review the most recent developments regardingsimulated annealing and genetic algorithms for solvingfacility layout problems approximately.     

生产运输成本问题的随机优化模型及新的求解途径

研究了供应商的生产能力,销售地的需求量和单位运输成本等因素均为随机变量条件下的单产品和多产品的生产运输成本问题,建立了该类问题的随机优化模型,证明了一般运输模型有解的充要条件,探讨了在一定的置信水平和其它相关约束条件下,确定每个供应商给每个销售地的送货量,以保证总运输成本最低的新的求解方法.通过数值方式,分析了不同的置信水平对成本的影响,给出了选择最佳置信水平的方法.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.