基于拉格朗日松弛的库存—路径问题优化

第28卷第6期重庆交通大学学报(自然科学版)Vol .28　No .62009年12月JOURNAL OF CHONG Q I N G J I A OT ONG UN I V ERSITY (NAT URAL SC IENCE )Dec .2009基于VRP 模型的两阶段物流网络路径优化模型 收稿日期:2009206203;修订日期:2009208220 作者简介:陈岱莲(19832),女,山东潍坊人,硕士研究生,研究方向为物流与供应链管理。

E 2mail :chendailian668@126.co m 。

陈岱莲1,李　鹏2(1.重庆交通大学管理学院,重庆400074;2.北京交通大学交通运输学院,北京100044)摘要:以基于VRP 模型的两阶段三层次物流网络路径优化问题为研究对象,利用启发式算法中的分解法将问题分为选择物流中心与配送路径优化两个子问题,并与数理规划软件L I N G O 810相结合给出了基于VRP 模型的MS DL 2RP 问题———多供应商、多配送中心选址与路径优化问题的求解模型。

利用所提出的模型可以求出商品从多供应商经过多物流中心到最终客户这一过程中能使费用最小的供应商的最佳位置与数量、物流中心的最佳位置与数量及从物流中心到客户的最佳配送路径,并通过实例进行了验证。

对于小规模问题,运用所提出的方法能在很短的时间内求出问题的最优解,具有一定的实用价值。

关　键　词:VRP 模型;设施选址;物流网络路径优化;启发式算法中图分类号:U491 文献标志码:A 文章编号:167420696(2009)0621131204Two 2St age L og isti cs Network Routi n g O ptim i za ti on M odel Ba sed on VRP m odelCHEN Dai 2lian 1,L I Peng2(1.School of Manage ment,Chongqing J iaot ong University,Chongqing 400074,China;2.School of Traffic &Trans portati on,Beijing J iaot ong University,Beijing 100044,China )Abstract:Taking the t w o 2stage l ogistics net w ork r outing op ti m izati on with three levels based on VRP model as the research object,the op ti m izati on p r oblem is divided by utilizing the decompositi on method of heuristics s oluti on int o t w o sub 2p r ob 2le m s,that is,selecting the l ogistic center l ocati on and op ti m izing the distributi on r outing .Combining with the mathematical p lanning s oft w are L I N G O 810,the s olving model of VRP 2Based M S DLRP p r oble m,which means multi 2vendor,multi 2distri 2buti on center l ocati on and r outing op ti m izati on,is obtained .U sing the p r oposed model the best l ocati on and nu mber of sup 2p liers,l ogistics center and the op ti m al distributi on r outes are obtained,which makes the costs generated by the p r ocess of p r oducts distributing fr om the multi 2supp liers via multi l ogistics centers t o the ter m inal cust omers s mallest .Moreover,this p r oposed model is verified by actual examp les .The p r oposed method can obtain the op ti m al s oluti on in a very short ti m e for the s mall 2scale p r oble m,which has certain p ractical value .Key words:VRP model;facility l ocati on;l ogistics net w ork r outing op ti m izati on;heuristics s oluti on1　引　言基于VRP 模型[1]的两阶段物流网络路径优化是指以VRP 模型为基础(即不考虑时间要求,仅根据空间位置安排战略),着眼于两阶段三层次(即涉及供应商、物流中心、客户)的物流网络,对商品从供应商到制造商经过中间库存和物流中心再到最终客户的整个流程中有关设施选址、物流路径优化等进行的决策。

宁波理工学院毕业设计（论文）开题报告（含文献综述）题目连锁超市配送线路优化研究——以杭州萧山区三江超市为例姓名 XXX学号 12345专业班级 08物流管理(2)班指导教师 XYZ学院管理学院开题日期 2011 年12月18日文献综述“连锁超市配送线路优化研究——以杭州萧山区三江超市为例”文献综述1.连锁超市配送的定义1.1连锁超市的定义超市(supermarket)20世纪30年代诞生于美国。

是指经营同一类别的商品和售后服务的若干超市以一定的形式合并成统一的整体，通过企业外表形象的标准化、经营管理活动的专业化、组织人事规范化以及内部管理手段的现代化，做到使复杂的商业活动实现相对的简单化，从而达到规模效应。

对超市行业来说，在一定程度上，有规模才可能有效益。

因为超市在初期建设固定资产上投入较大，而且属于劳动密集型，没有一定的规模来分摊这些固定成本将导致效益的降低。

同时企业规模的大小，覆盖商圈的范围，将直接影响到企业的市场份额。

这点恰是供应商评价客户质量的基础，规模大的超市将成为供应商优先供应的对象，在价格数量送货时间上将给予极大的方便。

反过来这也有利于增强连锁企业对供应商讨价还价的能力、控制与管理。

我国在20世纪80年代初引入“自选商场”，真正的连锁超市起步于90年代初，现在已经成为全国商业领域各种零售业态中增长最快的业态之一。

[1]中国连锁经营研究先行者赵涛先生在《连锁店经营管理》一书定义如下:所谓连锁，一般认为，一个商业集团以同样的方式、同样的价格，在多处同样命名(店铺的装修至商品的陈列也都差不多)的店铺里，出售某一种(或某一类、某一品牌)商品或提供某种服务，这些同时经营的店铺就被称为连锁店，这种经营模式则被称为连锁经营。

[2]1.2连锁超市配送的含义各国对配送的认识并非完全一致，在表述上有区别，但共识是商品配送是物流运动中“配”与“送”两项活动的有机结合。

但是在发达国家普遍认为商品配送的本质是送货，并不强调配，原因是在买方市场的国家中“配”是完善“送”的行为，是进行竞争和提高自身经济效益的必然延伸，是在竞争中优化形式。

基于拉格朗日松弛算法的冷链商品物流配送优化方法
陈文
【期刊名称】《长春工程学院学报:自然科学版》
【年(卷),期】2022(23)2
【摘要】网商平台的快速发展,对冷链产品的配送效率提出了更高的要求,而冷链产品配送受运输车辆、交通路况以及天气状态等因素的制约较多,针对多回路、多配送点位、多供货点的冷链产品的配送最佳路径求解的业界难题,将启发式搜索算法的应用与拉格朗日松弛算法相结合,用于冷链产品的复杂路径求解,结合综合因素对拉格朗日松弛算法进行动态自适应的调整,对冷链配送的网络模型进行动态优化调整,获取最优路径解。

仿真对比实验显示,该算法对比原始的粒子群优化算法,获得最佳路径的时间更短、最佳路径的求解能力更高。

【总页数】5页(P124-128)
【作者】陈文
【作者单位】福建船政交通职业学院
【正文语种】中文
【中图分类】O221.4
【相关文献】
1.利用拉格朗日松弛算法协调多厂供应链生产计划
2.冷链物流越库调度的拉格朗日松弛算法
3.基于社会化库存的多回程物流配送问题的拉格朗日松弛算法
4.基于拉
格朗日松弛算法的应急物流配送车辆调度模型优化研究5.基于拉格朗日松弛算法的分布式供应链优化
因版权原因，仅展示原文概要，查看原文内容请购买。

拉格朗日边界条件放松法库存管理人们普遍认为，最先对多级存货进行研究的是克拉克和斯科夫（960）。

他们对 N级流水体系进行了研究，结果表明，在考虑到折扣罚款和储存费用的情况下，该体系的最佳存货管理策略就是最大订单水平策略。

自那以后，许多学者开始从不同的视角来探讨供应链的存货问题。

根据已有的研究结果，本文将其归纳为：产品-存货-管理体系；产品-存货-配送体系；存货的配送。

存货网是将供应链中的产品和设备联系起来的，它可以用多层次的存货问题来描述。

目前对这类多阶段的存货管理体系的研究主要集中在企业内部。

以前的研究主要是针对目标优化问题。

当需求不变时，Crowston等采用了动态规划法，研究了存货问题；Schwartz和Schrage则是使用了一个边界条件的方法。

Afentakis和 Gavish （986）假定了随着时间的变化，使用了拉格朗日边边界条件松弛方法。

网络货运模式车货匹配问题研究现状综述作者：周宇航闫军旷光莲刘丹来源：《甘肃科技纵横》2024年第03期摘要：网络货运是当前物流行业中一种新兴货物运输模式，其不仅推动了物流行业的变革，也给物流行业带来了新的机遇和挑战。

车货匹配环节的效率直接影响到整体物流的效能。

因此，文章通过文献统计和文献总结分析的方法，系统评述了订单整合问题、车辆配载问题的数学建模及求解算法。

研究发现：车货匹配问题在理论研究和实际应用方面均取得了显著进展，但在结合人工智能、大数据等新兴技术方面的应用尚显不足。

文章对两类问题主要研究内容及方法做了简要总结，并对车货匹配问题未来研究方向进行了展望。

关键词：网络货运；车货匹配；订单整合；车辆配载中图分类号：U492.3+32 文献标志码：A作者简介：周宇航（1998-），男，硕士研究生在读，主要研究方向：网络货运、车辆配载及优化。

△通信作者：闫军（1971-），男，硕士，教授高工，主要研究方向：载运工具运用工程、现代物流、供应链管理。

0 引言网络货运平台的应用普及是提升物流效率的重要举措[1]。

从目前来看，网络货运是指由其业务经营人借助互联网服务平台整合运输车辆、货物等资源并进行合理配置，以承运人身份与货主签订道路运输服务合同，再委托实际承运人完成货物运输的一项经营管理活动。

在此过程中，网络货运经营者作为第一承运人承担实际承运人的主体责任[2]。

网络货运平台这一概念源于早期的无车承运人模式，无车承运人模式最早出现在美国，无车承运模式的深入发展使得各位学者认识到了无车承运人的重要作用和发展趋势[3]。

目前，国外对网络货运的研究主要聚焦在平台的算法设计[4]181 。

国内学者最早于2011年对网络货运进行研究。

董娜[5]最先对无车承运人的情况做了阐释，认为网络货运是基于互联网技术的物流模式，将传统的物流链条打通，实现了全球货物的及时、快捷、安全运输。

目前国内对网络货运研究主要集中于网络货运平台的经营模式[4]181 。

基于深度强化学习的动态库存路径优化
周建频;张姝柳
【期刊名称】《系统仿真学报》
【年(卷),期】2019(31)10
【摘要】针对具有周期性波动需求的动态随机库存路径问题,提出了基于深度强化学习进行仿真优化并实现周期平稳策略的新方法。

所研究问题构建动态组合优化模型,通过深度强化学习和设置启发规则来综合决定每个时期的补货节点集合和补货批量分配权重。

仿真实验结果表明,与现有文献中的两种方法相比,所提出的方法在较低波动需求情况下可分别提高一个周期的平均利润约2.7%和3.9%,在较高波动需求情况下提高约8.2%和7.1%,而周期服务水平在不同需求波动环境下都可以平稳地保持在一个较小的波动范围内。

【总页数】9页(P2155-2163)
【作者】周建频;张姝柳
【作者单位】集美大学航海学院;国网吉林供电公司
【正文语种】中文
【中图分类】TP391.9
【相关文献】
1.基于深度强化学习和动态窗口法的移动机器人路径规划
2.基于深度强化学习的网约车动态路径规划
3.基于深度强化学习的卫星动态功率控制技术
4.基于深度强化
学习的生鲜产品联合库存控制与动态定价研究5.基于end-to-end深度强化学习的多车场车辆路径优化
因版权原因，仅展示原文概要，查看原文内容请购买。

拉格朗日松弛算法在优化问题中的应用随着科技的不断发展，优化问题在现实生活中发挥着越来越重要的作用。

如何有效地解决这些问题，成为了当今研究领域中的一个热门话题。

其中，拉格朗日松弛算法在优化问题中的应用备受关注。

本文将深入探讨该算法的原理和具体应用。

一、优化问题的背景在现实生活中，我们经常遇到各种复杂的优化问题，比如最大化利润、最小化成本、最大化效益等等。

这些问题都是要求我们在一定的约束条件下，使目标函数达到最优状态。

然而，由于约束条件的复杂性，以及目标函数本身的复杂性，这些问题往往不易直接求解。

二、拉格朗日乘数法简介为了解决这类优化问题，人们提出了许多不同的算法。

而其中最为重要的算法之一，就是拉格朗日乘数法。

该算法最初由拉格朗日在18世纪提出，经过不断的完善和发展，已经成为了现代优化问题中的基础算法之一。

其核心思想是将原始的优化问题进行特殊的变换，从而将其转换为更加容易求解的形式。

具体来说，拉格朗日乘数法的做法就是将目标函数和约束条件相互结合，构造出一个新的函数，称为拉格朗日函数。

其中，约束条件成为了该函数的约束项，而拉格朗日乘数组成为了该函数的乘数项。

我们可以将其表示为：L(x,λ) = f(x) + λg(x)其中，x表示自变量，也就是我们要求解的问题的解；f(x)表示目标函数，即我们要优化的函数；g(x)表示约束条件；λ为拉格朗日乘数。

这样，我们原来的优化问题就变为了求解拉格朗日函数的最小值问题。

而由于该问题是一个无约束优化问题，因此我们可以采用许多不同的算法进行求解。

三、拉格朗日松弛法的优化虽然拉格朗日乘数法可以有效地解决许多优化问题，但是它也有很多局限性。

其中最为突出的问题，就是约束条件必须遵循等式约束的形式。

而在许多优化问题中，约束条件可能会采用其他形式，如不等式约束、整数约束等等。

为了解决这个问题，人们提出了拉格朗日松弛法。

该算法的本质思想还是通过构造新的函数，将原始的优化问题进行特殊的变形。

库存与运输整合问题的多种算法比较裴英梅;叶春明;左翠红;刘立辉【摘要】通过循序渐进地应用拉格朗日乘数法、基于样本的DSSP(Dynamic Slope Scaling Procedure)启发法和基于拉格朗日松弛模型的DSSP启发法等几种算法,分别求解多对多配送系统中的库存与运输整合优化问题,逐渐找到了解决问题的更加有效的方法——基于拉格朗日松弛模型的DSSP启发法.通过比较实验证明了此法在解决库存与运输整合优化问题时能在更少的计算时间里获得更优化的解.%The inventory-transportation integrated optimization (ITIO) problemin a distribution network with multiple warehouses and multiple retailers is addressed. For solving this problem, different algorithms are explored. First, a Lagrange multiplier method is used to solve the integrated problem of inventory control and transportation scheduling. Then, to overcome the computationally inefficiency for large-scale problem by the Lagrange multiplier method, a scenario-based dynamic slope scaling procedure (DSSP) heuristic is proposed to establish an ITIO model. Lastly, to improve the solution accuracy of the heuristic, the Lagrangian relaxation-based DSSP heuristic is applied to solve the ITIO problem. Comparison is done for problems in a many-to-many distribution network. Results show that the Lagrangian relaxation-based DSSP heuristic outperforms the others in both solution accuracy and computational efficiency.【期刊名称】《工业工程》【年(卷),期】2013(016)001【总页数】5页(P105-109)【关键词】库存与运输;整合优化;基于拉格朗日松弛模型的DSSP启发法【作者】裴英梅;叶春明;左翠红;刘立辉【作者单位】鲁东大学交通学院,山东烟台264025【正文语种】中文【中图分类】F253对于库存与运输整合优化问题(inventory-transportation integrated optimization problem，ITIO 问题)，现有文献往往关注于一对多［1-3］或多对一［4］的配送系统，针对多对多配送系统的研究成果很少。

多载具自动化存取系统作业调度优化杨朋;缪立新;秦磊【摘要】为从作业调度角度提交多载具自动化存取系统的运作效率,根据多载具自动化存取系统的作业特点,建立了多载具自动化存取系统作业调度优化问题的数学模型,对问题进行复杂度分析,证明为NP-hard问题,设计了遗传模拟退火算法对问题进行求解.通过实例对算法性能进行分析,结果表明提出的算法具有较好的求解精度和较高的求解效率,能够有效地缩短完成存取货作业的行程时间.%To improve the operation efficiency of multi-shuttle Automated Storage and Retrieval System (AS/RS) in term of job scheduling,a mathematical model for job scheduling optimization was established according to the operational characteristic of multi-shuttle AS/RS.The job scheduling problem was proved to be NP-hard after complexity analysis,and a genetic simulated annealing algorithm was developed to solve this NP-hard problem.The performance of proposed algorithm was demonstrated by numerical examples,and the results showed that the algorithm had better solution precision and efficiency.The travel time of performing storage and retrieval operations was reduced effectively by this algorithm.【期刊名称】《计算机集成制造系统》【年(卷),期】2013(019)007【总页数】7页(P1626-1632)【关键词】多载具自动化存取系统;作业调度;复杂度分析;遗传算法;模拟退火算法【作者】杨朋;缪立新;秦磊【作者单位】清华大学深圳研究生院现代物流研究中心,广东深圳518055;清华大学深圳研究生院现代物流研究中心,广东深圳518055;清华大学深圳研究生院现代物流研究中心,广东深圳518055【正文语种】中文【中图分类】TP3910 引言多载具（multi－shuttle）自动化存取系统（Automated Storage and Retrieval System，AS／RS）是一种高吞吐量高柔性的新型仓储系统，多载具AS／RS堆垛机一次行程可以同时存放和取出多个货物单元。

装配线物料搬运的拉格朗日松弛算法周炳海;胡理嫚【摘要】为提高汽车制造企业混流装配线的运行效益,提出了基于看板模型的多封闭循环路径多载量小车物料配送调度方法—–装配线物料配送调度的拉格朗日松弛算法.首先对问题域进行了描述并做出了具体假设,以最小化配送系统总成本为目标,建立了混合整数规划模型.在此基础上,针对该模型提出了两种算法—–次梯度和随机步长拉格朗日松弛算法,将松弛问题分解为两个决策子问题分别进行求解.仿真实验表明提出的两种调度算法均适用于该研究问题域,并在求解时间及稳定性上表现出良好的性能.%To effectively enhance the performance of the mixed-model assembly line in automobile manufacture enter-prises, a kanban model-based scheduling method of multi-close-loops dolly train material delivery, Lagrangian relaxation algorithm for material delivery problems of assembly lines, is proposed in this paper. First of all, a problem domain of multiple-close-loops dolly train material delivery is presented and a few assumptions of the problem are depicted in detail in the paper. Then, a mixed integer programming model is constructed, which aims to minimize the total expected cost of material delivery system. On that basis, two algorithms–-Lagrangian relaxation based on subgradient and Lagrangian relaxation based on random step–-are proposed for the mixed integer programming model, which both decompose the relaxed problem into two decision sub-problems both of which are solved respectively. Simulation experiments show that the two scheduling methods are fit tosolving the problem and have a better performance in calculating time and stability.【期刊名称】《控制理论与应用》【年(卷),期】2017(034)004【总页数】8页(P491-498)【关键词】物料搬运;看板;调度;拉格朗日松弛【作者】周炳海;胡理嫚【作者单位】同济大学机械与能源工程学院,上海201804;同济大学机械与能源工程学院,上海201804【正文语种】中文【中图分类】TP391随着产品多样性与定制化趋势的发展,准时化零部件配送愈加成为制造企业所面临的一大挑战.车辆装配线中的多载量小车(dolly train)物料配送问题越来越受到学术界和工业界的关注.近年来,多载量小车物料配送调度决策问题引起了许多国内外学者的重视.Battini等[1]研究指出,由于小车容量与工位空间限制不利于准时化物料配送策略的实施,因此混流装配线的准时化(just-in-time,JIT)物料配送问题尤为复杂.但仍有不少学者致力于解决这一难题.Choi等[2]首次研究了动态系统下多载量小车零部件配送问题,以最小化惩罚值为目标确定小车最优配送序列.Jenny等[3]根据JIT原则以最小化配送人员数量建立了混合整数规划模型,并提出了相应的求解启发式算法.Boysen 等[4]研究了静态配送系统下单条装配线的零部件配送问题,建立了两个动态规划模型,并采用嵌套动态规划算法求解了小车路径、调度与装载问题.Boysen等[5]研究了混流装配线多载量小车装载问题,在小车有限容量与避免物料短缺约束下最小化线旁库存量,并提出了一个精确的多项式时间求解算法.Faccio等[6]首次提出整合库存超市、看板与多载量小车配送系统的调度框架.Faccio等[7]通过仿真研究了看板配送系统下多装配线多载量小车固定路径配送调度问题.Marco Bortolini等[8]通过仿真确定了在固定路径下最佳小车数量与安全因素并优化看板数量.可知,将多载量小车物料配送调度问题与看板优化问题结合研究的文献少见报道;其次,由于多载量小车配送决策与看板优化整合问题的复杂性,现有文献研究均采用仿真方法求解,但仿真本身存在时间与建模成本高、通用性低等缺陷;再则,已有的多载量小车调度方法忽略了小车路径选择对于装载的耦合这一重要特性.而类似拉格朗日松弛这类能够在合理的时间内找到实际规模问题的可量化指标的近优解算法更受青睐[9-12].因此,在上述文献基础上,本文尝试进行变路径多载量小车配送决策与看板优化整合问题研究,提出适用于该模型的两种拉格朗日松弛算法,松弛路径选择与装载耦合约束,从而提高问题求解效率与稳定性.2.1 问题描述(Problem statement)如图1所示,多载量小车负责将装满零件的物料箱从库存超市搬至相应的工位.整个物料配送过程分为4个阶段.首先多载量小车到达停车装载处,将领料看板指示的物料箱放入车厢中.然后多载量小车根据看板生成的运输指令、小车容量与生产线零件需求的紧急程度(配送距离与消耗率决定)选取合适的零件装载.接着小车沿循环路径历经各个工位,在需求工位处卸载零部件并替换出空料箱;最后多载量小车将空箱运回库存超市,空箱根据看板指示向前一道工序补充物料.2.2 数学模型(Mathematical formulation)基于上述问题描述,建立数学模型如下:1)模型假设.该系统中配送间隔时间一定,不允许小车在工位旁滞留;首个零部件取出后立即摘下看板放入看板回收箱,运输指令由回收的看板直接生成;看板系统由装载计划对运输指令进行分配,允许已生成的运输指令延迟搬运;只有生成运输指令的工位才需零部件补充,运输指令元素仅由一次搬运完成;每个工位都有一定的初始库存;不允许缺货;库存超市服务水平为100%;整个系统处于稳定状态;采用弹射架与重力式托盘,小车装卸载时间可忽略;时间均标准化为节拍(takt).2)参数.r∈R:配送路线集合R={1,2,···,rmax=R};f∈F:运输指令集合,元素F为搬运最大频次F={1,2,···,fmax=F};m∈M:零部件集合M={1,2,···,mmax=M};l∈ L:生产线集合L={1,2,···,lmax=L};J:配送人员需求量;Ctotal:总成本,RMB;Cost−man:劳务费用,RMB;Cost−tow:多载量小车固定投资成本,RMB;CStock:库存成本,RMB;aml0:初始库水平,不包括安全库存,unit;Qc:库存价值系数,RMB/unit;γml:生产线l对应工位上零部件m的平均消耗量,unit/takt;Smsl:通过r路径将零部件m搬运至对应工位经历的运输距离,m;Vtow:多载量小车平均运行速度,m/takt;B:配送间隔时间,takt;ktml:生产线l零部件m物料补充指令在运输指令中,取值为1;否则为0,SKU; Ttravel:多载量小车完成一次搬运所需平均运输时间,takt;:生产周期,takt;STot:运输路径长度即集货配送路线总长度,m;Ctow:多载量小车装载容量,SKU;qm:零部件m标准箱容量大小,unit/SKU;:生产线l产品i的需求标准差(Standard deviation,SD),unit/takt;:生产线l零部件m需求箱数SD,SKU/takt;:丰田公式看板数量估算值;:改进公式看板数量估算值;cml:生产线l上零部件m平均需求箱数,SKU/takt;:零部件平均提前期,takt;pim:每种产品的物料清单;Fml:生产周期内生产线l上零部件m的必须配送次数;LTml:生产线l上零部件m连续两次搬运的平均提前期.3)决策变量.xjr:二进制变量,表示配送人员j选择路径r执行此次配送任务;δ:连续变量,安全因子,表示生产线上工位服务水平;yftml:二进制变量,表示当前运输指令元素ktms由第f次搬运完成.以最小化多载量小车物料配送成本与库存成本为调度目标,建立如下数学规划模型: 上述模型中,式(1)-(14)为多载量小车配送模型:目标函数(1)为最小化配送成本与库存成本;约束(2)与约束(3)分别为配送人员与配送次数计算公式;约束(4)表示只有生成运输指令的工位才需零部件补充,运输指令元素只执行一次搬运;约束(5)表示每次搬运只能选择一条循环路径;约束(6)表示一次搬运量不得超过小车容量;约束(7)表示搬运结束即完成所有运输指令;约束(8)为不允许提前搬运;约束(9)为线边库存计算公式;约束(10)表示不允许缺货;约束(11)保证小车每次搬运装载率;约束(12)-(14)定义变量性质.式(15)-(17)为传统丰田看板估算模型;与传统丰田估算看板不同的是,改进看板估算模型即式(18)-(21)摒弃了零件提前期一致的理论假设,采用差异化提前期估算看板数量,从而更加贴近实际混流装配线看板需求.式(18)表示根据不同的零部件提前期估算看板数量;式(19)表示零件需求标准差估计;式(20)表示不同零件的搬运次数;式(21)表示不同零件的搬运提前期不同.3.1 松弛决策约束(Relaxing decision constraints)由于小车配送模型结构特殊,只有式(9)与式(10)均包含变量δ与变量xfr,yτtml,其他约束仅包含其中一个变量,为充分利用该结构性质,问题模型(P)通过松弛约束(10)可重构为拉格朗日松弛问题(LR),(LR)目标函数为子问题S1只包含变量δ与变量xfr,变量为非负,因此S1模型为混合整数规划模型;子问题S2仅包含变量yftml,变量为整数且非负,因此S2模型为整数规划模型,两个子问题均采用MATLAB混合整数规划求解函数求解.3.2 构造可行解(Construction of a feasible solution)由于对偶问题获取的解为原问题的下界,可能违反耦合约束(10),对于原问题通常是不可行的,因此需要将不可行的解可行化,从而获取原问题的上界.构造可行解的步骤如下:第1步,因为搬运越往后,搬运出现缺货的几率越高,越不易满足约束(10),因此按照搬运次序由后到前,在每次搬运中,按照搬运路径由短到长的顺序,在下界中选取短路径xjr与长路径xjr′互换,放松式(10)右侧约束.第2步,由于S1中,求解获取的连续变量δ过小,无法满足约束(10),因此将第1步交换后的下界解集中的安全因子以0.0135步长逼近最小化最大安全因子,以尽可能小的安全库存成本增幅获取原问题的可行解.第3步,如果仍然没有可行解,返回第1步继续变量值xjr互换,同时δ上界以一定步长(取值0∼0.3)下降,以逼近最小化最大安全因子,一旦找到可行解,终止解可行化.3.3 次梯度算法(Subgradient algorithm)在计算拉格朗日对偶问题时,采用次梯度方法进行拉格朗日乘子更新式(28)可保证尽快获取一个可接受的下界,使得步长以指数速度下降,减少迭代次数. 次梯度计算公式为3.4 随机步长算法(Random step algorithm)针对基于次梯度优化的拉格朗日松弛算法收敛较慢的特点,提出了加速收敛的随机步长算法,步长βh设置为随机步长而非指数变化步长.拉格朗日乘子更新如下:其中rand(1)表示生成取值0∼1的数值,避免过早收敛影响解质量,θ根据实验选取合适值,保证乘子取值不过大且算法具有较好的收敛性.3.5 拉格朗日松弛算法步骤(Steps for Lagrangian relaxation algorithm)步骤1 设置初始值,拉格朗日乘子λh初始值,当前上界与下界值,UB与LB.步骤2 松弛问题(P)的约束(10),建立拉格朗日对偶问题(LD).将LD分解为子问题S1与S2.步骤3 子问题S1加入约束(32)后对子问题S1采用MATLAB求解;然后将上述求解得到的确定值带入原问题求解问题(P),如果解为最优或小于上界,则将其设为新的上界.步骤4 对S2使用与步骤3相同处理方法.步骤5 整合步骤3与步骤4中子问题的最优解,如果之和大于下界,设置其为新的下界.步骤6 核查停止规则,如果连续两次求解下界差值大于0.1,那么计算βh更新拉格朗日乘子,λh+1=max(0,λh+βh),设置h=h+1,βh为步长.步骤7 如果找到近似最优解,过程终止,z∗=UB,并计算GAP1=(UB−LB)/LB.在计算步骤3,由于最小化S1子问题时连续变量δ在其中的取值始终为0致使下界过低,因此加入约束(32)保证下界不会过低且收敛较快.本文采用主频2.5 GB,内存为4 GB的PC电脑进行仿真实验.首先采用LINGO分枝定界算法验证改进看板模型的优越性,然后通过MATLAB编程实现拉格朗日松弛简化多载量小车配送模型求解.案例以一家汽车企业的混流装配线为研究对象.3条并行的直线装配线生产7种汽车:3种混合汽车模型与4种城市汽车模型.装配线1,2,3分别装配产品1,2,3;产品4,5与产品6,7.每种产品的物料清单中均有15种零部件.系统的配送调度均由JIT-看板策略控制并由多载量小车在库存超市与装配线之间来回搬运实现.小车一次循环搬运行程长312 m.表1与表2分别给出了案例研究所需信息:产品配比、7种装配产品的物料清单表、库存量单位(SKU)容量qm与零部件消耗量γms.多载量小车的特征参数设置如下:小车容量C=10 SKU,平均速度Vtow=0.5 m/s;一辆汽车的出产时间1 takt=60 s,小车运行速度Vtow=30 m/takt,则小车一次循环时间Ttravel=10.4 takt.小车装载率η=50%;为简化成本计算,搬运间隔时间B=1 takt,库存成本Qc=1 RMB/unit.每天多载量小车运营成本(包括操作者工资)Ctow=2000 RMB,生产线平准化生产量Ntakt取值为6 takt/day.4.1看板优化结果(The optimized result of kanban)Marco Bortolini已经通过仿真实验证明了改进看板模型计算结果更接近仿真结果,更适用于混流装配线的看板估算.根据图2,不难发现,不同零部件所需看板数量是有差异的;改进看板模型的看板需求总量119较丰田公式估算量135少,即意味着采用改进模型的生产线在制品更少.实验结果再次验证Marco Bortolini等人的研究结论,采用改进看板估算模型获取的估算结果更好.综合以上分析,1)在B&B,RDMLR与TDLR这3种算法对3种不同规模问题的求解中,TDLR求解质量均较好且求解时间增幅最小,其稳定性最好;2)对于中大规模问题,RDMLR算法求解质量比TDLR算法更好;3)产品物料清单对模型的求解时间与质量有一定的影响,产品物料清单所需零部件种类越多,下界越紧,求解时间越长.这是因为随着零部件种类越多,多载量小车装载限制也会随着增多,相应的符合的组合数量也会减少,从而使得模型更容易获得较优的调度结果;而问题规模越大,其复杂性也随之增大,因此求解时间也随之变长;4)在小规模问题求解中,3种算法求解时间基本一致,但是B&B算法求解质量最好;在中大规模问题中,虽然LR算法求解效率高于B&B,但是只能获得近似最优解;对于大规模问题,LR算法求解效率较低且下界解质量不稳定,验证了随着问题规模增大,每步迭代子问题的精确求解与算法本身的震荡导致了求解效率低与收敛速度慢.提出了看板系统控制下的多循环路径多载量小车配送调度方法,将多载量小车物料配送问题与看板优化问题相结合建立了其调度数学规划模型.并提出了求解调度数学规划模型的两种拉格朗日松弛启发式算法,并用数值实验方法验证了两种算法的适用性与各自的优越性.由于影响装配线的因素繁杂,后续研究可以考虑更多配送系统的影响因素更适应实际生产环境;也可考虑求解大规模问题的新调度方法,如人工智能算法.周炳海 (1965-),男,博士,工业工程研究所所长,博士生导师,主要从事离散系统建模、调度与仿真等方向的研究,E-mail:*****************.cn;【相关文献】[1]BATTINI D,FACCIO M,PERSONA A,et al.Design of the optimal feeding policy in an assembly system[J].International Journal of Production Economics,2009,121(1):233-254.[2]CHOI W,LEE Y.A dynamic part-feeding system for a automotive assemblyline[J].Computers&Industrial Engineering,2002,43(1):123-134.[3]GOLZ J,GUJJULA R,GÜNTHER H O,et al.Part feeding at highvariant mixed-model assembly lines[J].Flexible Services and Manufacturing Journal,2012,24(2):119-141.[4]EMDE S,BOYSEN N.Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines[J].European Journal of OperationalResearch,2012,217(2):287-299.[5]EMDE S,FLIEDNER M,BOYSEN N.Optimally loading tow trains for just-in-time supply ofmixed-model assembly lines[J].IIE Transactions,2012,44(2):121-135.[6]FACCIO M,GAMBERI M,PERSONA A,et al.Design and simulation of assembly line feeding systems in the automotive sector using supermarket,kanbans and tow trains:a general framework[J].Manage Control,2013,24(2):187-208.[7]FACCIO M,GAMBERI M,PERSONA A.Kanban number optimisation in a supermarket warehouse feeding a mixed-model assembly system[J].International Journal of Production Research,2013,51(10):2997-3017.[8]BORTOLINI M,FERRARI E,GAMBERI M,et al.New kanban model for tow-train feeding system design[J].Assembly Automation,2015,35(1):128-136.[9]ZHOU Binghai,ZHONG grangian relaxation algorithm for scheduling problems of reentrant hybrid fl ow shops[J].Control Theory&Applications,2015,32(7):881-886.(周炳海,钟臻怡.可重入混合流水车间调度的拉格朗日松弛算法[J].控制理论与应用,2015,32(7):881-886.) [10]TU Guoyu,SONG Shiji.Stochastic model for total cost optimization in streetlamp maintenanceand itsprobabilistic Lagrangianrelaxation method[J].ControlTheory&Applications,2011,28(3):407-413.(涂国煜,宋士吉.路灯维护总费用随机优化模型及其概率分布拉格朗日松弛方法[J].控制理论与应用,2011,28(3):407-413.)[11]FISHER M L.The lagrangian relaxation method for solving integer programming problems[J].Management Science,2004,50(12):1861-1871.[12]PENG Tao,ZHOU Binghai.Just-in-time distribution algorithm of line-side parts for automobile assembly lines[J].Control Theory&Applications,2016,33(6):779-786.(彭涛,周炳海.车辆装配线线边物料准时化配送算法[J].控制理论与应用,2016,33(6):779-786.)。

基于拉格朗日松弛的高速铁路列车运行图r新增运行线局部调整模型江峰;倪少权;吕红霞【摘要】给定新增列车理想始发时刻及初始利润,考虑始发时刻调整及全程停时延长造成的罚数,基于时空网络构建以全图运行线总利润最大为目标的整数规划模型,进行拉格朗日松弛,根据松弛解对偶信息设计启发式算法求解各运行线可行解,并通过更新拉格朗日乘子进行迭代优化.以京沪高铁为例进行了验证,结果表明:在算例条件下,相较以理想始发时刻推线求解,该方法能够多增铺6条运行线;随着始发时刻可调整度由10 min增加至60 min,CPLEX的求解时间快速增长,而拉格朗日松弛启发式算法能快速求得高质量的解,除始发时刻可调整度10 min情景,求解效率均高于CPLEX;延长始发时刻可调整度至4 h,最多增铺18条运行线,说明现有框架下京沪高铁能力已接近饱和.【期刊名称】《交通运输系统工程与信息》【年(卷),期】2018(018)004【总页数】8页(P163-170)【关键词】铁路运输;列车运行图;拉格朗日松弛;京沪高铁;通过能力【作者】江峰;倪少权;吕红霞【作者单位】西南交通大学交通运输与物流学院,成都610031;西南交通大学交通运输与物流学院,成都610031;西南交通大学全国铁路列车运行图编制研发培训中心,成都610031;西南交通大学综合交通运输智能化国家地方联合工程实验室,成都610031;西南交通大学交通运输与物流学院,成都610031;西南交通大学全国铁路列车运行图编制研发培训中心,成都610031;西南交通大学综合交通运输智能化国家地方联合工程实验室,成都610031【正文语种】中文【中图分类】U292.410 引言列车运行图调整是根据运输需求完善运行图的过程，分局部调整与全局调整.局部调整在既有框架下根据增开列车需求增铺运行线，涉及新增运行线铺画和既有运行线调整；全局调整则是全图运行线的重新铺画.既有高速铁路运行图框架是列车开行方案长期优化的结果，通常不进行全局调整.随着路网完善及运输需求变化，高速铁路运行图局部调整增多，现有的人工推线求解方法难以保证质量，存在很大局限性，因此有必要研究列车运行图局部调整模型与算法.列车运行图调整属列车运行图编制(Train Timetabling Problem,TTP)范畴，是NP-hard问题[1-3]，大量国内外学者对相关问题进行了研究.国内方面，文献[2]以单线区段为背景，优化各运行线旅行速度.文献[4]构造了适用于单双线区段的运行图时空窗口，滚动求解各运行线.文献[5]考虑上下行列车到发站属性差异，求解单线非追踪平行运行图最小周期.文献[6]在周期性运行图基础上，以深度搜索法添加非周期运行线.文献[7]总结了基于周期事件规划问题(PESP)的周期性运行图模型及其应用情况.其中文献[4,6]属启发式方法，缺乏对所得解的优劣评价；文献[2,5]研究单线区段，不完全适用于高速铁路双线区段；文献[6-7]研究对象为周期性运行图.国外方面，文献[3]通过给定各列车初始利润，以总收益最大化为目标建立整数规划模型，对原模型进行拉格朗日松弛，以动态规划方法求解各运行线.文献[1]根据给定列车开行方案，基于时空网络铺画周期性运行图.文献[8]以路网中列车总旅行时间最小为目标，研究货物列车最优径路问题.上述研究基于拉格朗日松弛技术，适用于周期[1]及非周期列车运行图[7-8]，并能有效评价所得解的优化程度[1,7-8].文献[9]归纳总结了不同运行图编制模型的特点及适用情况.上述研究为本文奠定了理论基础.我国高速铁路运行图呈非周期性，局部调整以新增列车开行方案为基本输入，需调整的既有运行线可视为一类特殊的新增列车，从而将局部调整转化为给定框架下的新增运行线求解问题.现有基于拉格朗日松弛的运行图调整模型简化了列车在区间运行状态，未考虑停站引起的起停车附加时分[7-9]，无法实际应用.本文在文献[1,7-8]的基础上，考虑列车停站需求，细化停站对列车区间运行时分的影响，给定各新增列车一个由理想始发时刻及始发时刻可调整度、全程停时总延长决定的始发时间域，将运行线铺画转化为最短路求解问题，建立整数规划模型并进行拉格朗日松弛求解，根据对偶信息设计启发式算法迭代求解运行图最优可行解.1 问题描述运行图可由有向时空网络描述[1,7-9]，其中纵轴表示车站、横轴表示时间.将1天以分钟为单位离散为1～q，每个车站包含1 440个节点，每条列车运行线所经节点即可由车站及所经节点对应时刻确定.以G=(N,A)表示该有向时空网络，其中点集N中元素代表时空域上车站所在位置，包括到达节点U及出发节点W；弧集A 中元素代表相邻节点间有向弧，为列车运行线组成部分.对每条运行线设置一个虚拟出发点σj及虚拟终到点εj，则有N=设S为全体车站集合，给定列车集以表示列车j∈T所经车站集合(共s站).运行图局部调整即为在G=(N,A)中，在原有框架下，根据给定新增列车始发时间域铺画新增运行线的过程，如图1所示，其中T1为新增列车.上述问题为一定约束下G中自fj起，途径fj+1,…,lj-1至lj止的最短路径，可表示为，其中Nj,j∈T表示列车j所经车站节点构成的点子集，由列车j所经车站及在该站的到达、出发时刻决定；Aj,j∈T表示与列车j有关的弧子集，由列车j的区间运行时分或在站停时决定，其中的求解范围由列车始发时间域及全程停时总延长范围决定.列车j的运行线即为与其有关的弧子集Aj中的元素，包含有：从虚拟出发点σj至列车j始发站出发节点v∈Wfj的始发弧；在中间站，由到达节点u∈Ui至出发节点v∈Wi的停留弧；由车站i至i+1区间内经由车站i出发节点v∈Wi至车站i+1到达节点u∈Ui+1的运行弧(v,u)；从列车j终点站到达节点u∈Ulj至虚拟终到点εj的终止弧(u,ε).其中，在站停留弧(u,v)的占用时间为列车j在车站i的停站时间，当列车在站通过不停车时，其占用时间为0；运行弧(v,u)的占用时间为列车j在区间(i,i+1)的总运行时分，由列车区间运行时分决定.图1 列车运行图的时空网络表述Fig.1 A time-space express of train timetable 2 列车运行图局部调整模型2.1 变量说明2.2 模型约束新增运行线j需满足一定约束.对两相邻列车j、k而言，在任意站，其构成弧需满足车站间隔约束、运行线唯一性约束、列车停站约束及相关连接变量约束等.2.2.1 车站间隔约束(1)列车在车站i的出发时刻应不小于该站发车间隔di，即Δ(v1 ,v2 )≥di,v1＜v2，如图2所示.图2 发车间隔示意图Fig.2 Departure interval约束可表示为对任意，在内所有节点v至多有1个被某运行线选择，即(2)列车在车站i+1的到达时刻应不小于该站到达间隔ai+1，即Δ(u1,u2 )≥ai+1,u1＜u2，如图3所示.图3 到达间隔示意图Fig.3 Arrival interval约束可表示为对任意i∈S/{1},u∈Ui+1，在Δ(u1,u2)＜ai+1内所有节点u至多有1个被某运行线经过，即(3)两运行线在区间内不相交，设v1＜v2,u2＜u1，如图4所示.图4 区间不相交约束示意图Fig.4 No overpass in sector constraint设区间内列车k的速度高于列车j，约束可表示为对任意相邻车站i和i+1，运行线j、k，图4所示的4个节点中，至多3个被这两条运行线经过，设v1＜v＜v2，u2＜u ＜u1，有2.2.2 运行线唯一性约束(4)始发弧数量约束.(5)节点v进入、离开弧数量约束.(6)节点v选择次数约束.2.2.3 列车停站约束列车停站约束为列车j在经停站停时不少于该站计划停时；在非经停站出发时刻与到达时刻相等.设θ(v)=θ(u)+tij,i∈Scj⊆Sj,j∈T，Scj为列车j的经停站，tij为列车j在车站i的计划停时，包括：(7)经停站出发时刻选择限制.(8)非经停站出发时刻选择限制.2.2.4 连接变量约束连接变量约束为各0-1变量间相互约束.(9)弧构成约束.(10)节点选择约束.2.3 目标函数各运行线始发时间域及总停时限制决定了其所有可选节点及弧的子图Gj=(Nj,Aj)，其可行解即为在Gj=(Nj,Aj)中满足上述约束条件的1条路径.为评价解的质量，对每一条运行线j初始点赋予初始利润πj，对其相对计划始发时刻的调整及总停时延长赋予罚数，该运行线的最终利润即为各构成弧的利润之和[1].设αj、βj为相应系数，对每个初始弧(σ,v),v∈Wfj，设υ(v)为始发点v对应时刻与理想始发时刻θ(fj)的差值，有其利润为p(σ,v)=πj-αjυ(v)；对每一个停留弧(u,v),u∈Ui,v∈Wi,i∈Sj/{fj,lj}，设μ(u,v)为实际停时与计划停时θ(u,v)的差值，其利润为p(u,v)=-βjμ(u,v)，以pa表示运行线j中所有弧a∈Aj利润之和，有pa=p(σ,v)+p(u,v)，以全图所有运行线利润最大构建目标函数[1].3 基于拉格朗日松弛的启发式算法3.1 约束松弛上述模型中行车组织约束属于簇约束，数量随问题规模快速增长，会引起模型规模的急剧扩大，对其进行拉格朗日松弛可加快求解速度[1,8-9].基于文献[1,8-9]所述方法，对原模型中式(1)～式(3)分别增加拉格朗日乘子后添加至目标函数，将其转化为式中：C——由行车组织约束决定的与该节点不相容弧集[10]；λC1、λC2——对应的拉格朗日乘子.对式(11)进行恒等变换，即式中：——变量yv及zjv所对应的拉格朗日罚数；λh——第h个松弛约束对应的拉格朗日乘子，其含义为，①当λh对应约束为式(1)或式(2)，即yw时，有bh=1，任何经过点w的运行线将被赋予1个罚数λh.②当λh对应约束为式(3)，即zjw时，有bh=3，任何经过点w的列车j将被赋予1个罚数λh.原模型松弛后，各运行线间约束关系被弱化，可由线性规划方法快速求解[1,7,10]，所得结果即为各运行线的拉格朗日松弛解.易知当LD中时，有LD=D，此时拉格朗日松弛问题达到最优且与原问题最优解相等；当时，有LD＞D，即LD为D的一个上界[10-11].3.2 可行解启发式求解由于松弛了原模型中部分约束，LD中各运行线拉格朗日松弛解可能是实际非可行解.为求得实际可行解FD，设计下述启发式算法：(1)求解LD，记录全图各节点拉格朗日罚数(2)新增运行线按拉格朗日松弛解利润大小排序确定铺画顺序.(3)在新增运行线始发时间域内基于所有可行出发节点并考虑p(σ,v)、p(u,v)，选择λh(N)=0的节点，以min(p(σ,v)+p(u,v))为目标，基于深度搜索算法[5]求解实际利润最大的运行线，并记录每个车站的最大停留列车数，若大于该站到发线数量，则该运行线无实际可行解，所得解为各运行线的实际可行解.(4)求解全图实际利润大于零的运行线实际利润之和，结果记录为FD的解.所求得的FD为D的1个实际可行解[5,10].由于考虑了λh(N)=0的限制，因此有FD≤D，即FD为D的1个下界.3.3 拉格朗日乘子更新由于FD≤D≤LD，故D最优解处于区间(FD,LD)内，通过更新拉格朗日乘子，可优化FD的目标函数值，使其趋近于D最优解[7-10].拉格朗日乘子的更新由LD中式(1)～式(3)的违反情况确定[10,11]，其步骤为：(1)初始化各约束次梯度要素viol(λh)=-1.(2)对各运行线构成弧检查是否满足第h个约束条件，若违反该约束则对第h个约束的次梯度要素更新为viol(λh)=viol(λh)+1.(3)求解全局次梯度向量(4)根据Fisher提出的式(15)更新第h个约束对应的拉格朗日乘子λh[10-11].式中：ρ——给定的非负步长[10-11]，初始值设为ρ=1，当迭代10次min(LD)未发生改变则减半ρ取值.通过上述过程可优化LD及FD的目标函数值，从而对FD进行迭代优化，当LD与FD满足一定条件时可认为已求得最优可行解[1,7-10].3.4 算法流程Step 0初始化，记录起始时间，设迭代次数为0，当前最优可行解为0，当前最优上界为全图各运行线初始利润之和.Step 1求解LD，记录当前最优上界为min(LD).Step 2根据LD所得各节点罚数λh(N)，以3.2节所述方法求解运行线实际可行解，计算全图各运行线实际可行解利润和FD，记录当前最优下界为max(F D).Step 3设gap=(min(LD)-max(FD))/max(FD)⋅100%，判断max(FD)与min(LD)间差值是否小于设定gap值，若是，算法终止，最优下界所对应的解即为最优可行解；若否，迭代次数+1，转Step4.Step 4以3.3节所述方法更新拉格朗日乘子λh.Step 5检查算法运行时间、迭代次数是否达到设定最大值，若是，算法终止，最优下界对应解即为最优可行解；若否，转Step1.4 算例验证以2015年5月京沪高铁运行图为例，在原图302条运行线框架下增铺24条G类高速运行线，新增列车信息如表1所示.表1 新增列车信息Table 1 New trains’information拟增加列车AD1001/AD1002 AD1003/AD1004 AD1005/AD1006 AD1007/AD1008AD1009/AD1010 AD1011/AD1012 AD1013/AD1014 AD1015/AD1016AD1017/AD1018 AD1019/AD1020 AD1021/AD1022 AD1023/AD1024列车运行区段津沪线路所—蚌埠南停站时间/min各站均2津沪线路所—蚌埠南各站均2催马庄线路所—蚌埠南停站德州东、济南西、徐州东沧州西、济南西、枣庄、徐州东枣庄、徐州东各站均2济南西—北京南各站均2徐州东—上海虹桥各站均2徐州东—上海虹桥初始始发时刻7:00/14:05 10:20/15:25 10:35/10:157:00/7:00 11:20/17:40 15:00/8:10 8:50/10:20 12:15/11:00 12:30/12:3512:40/12:45 20:20/17:00 21:30/20:20德州东、廊坊蚌埠南、南京南、苏州北南京南、无锡东各站均2本文主要验证模型算法的有效性，求解过程中暂不要求列车上下行数量相等.首先以现有调整方法进行实验：以初始始发时刻推线求解，结果表明仅能增加AD1015/AD1016、AD1019、AD1023/AD1024次等5条运行线；扩大始发时刻可调整度至60 min，可增加AD1009、 AD1015/AD1016、AD1018/AD1019、AD1021/AD1022、AD1023/AD1024次等 9条运行线.然后验证本文所提出模型：给定各运行线初始利润10 000，设αj=10、βj=20、新增列车总停时延长上限为10 min、算法迭代次数上限为200次、运行时间上限为60 min、gap为1%.列车运行参数根据实际情况确定，列车始发时间域以给定的理想始发时刻及可调整度确定.算例对应规模下，可逐一列出所有簇约束所包含的约束条件.为验证拉格朗日松弛算法效率，调用ILOG CPLEX 12.5求解原模型D进行对比验证.相关算法以C语言实现，实验在1台Ubuntu14.04 Xeon 2.66GHz 4G内存工作站上进行，结果如表2所示，其中C代表CPLEX求解结果，L代表拉格朗日算法求解结果.可见可增铺运行线数量随列车始发时刻可调整度增加而增加，说明列车始发时间域是影响列车运行图局部调整的重要因素.簇约束式(1)～式(3)使得模型规模急剧增加，CPLEX虽然求解精度较高，但求解速度下降明显；而拉格朗日算法求解时间增加较为平缓，目标函数值、新增列车运行线平均旅速与CPLEX求解所得结果十分接近(表2)，在保证求解质量的同时维持了较高的计算效率.统计不同始发时刻可调整度下拉格朗日算法所得结果如表3所示，其中始发时刻调整总时长、平均时长、最大调整时长分别为相应始发时刻可调整度下各新增运行线较给定理想始发时刻调整值之和、各新增运行线始发时刻调整值均值、各新增运行线最大始发时刻调整度；总停时延长值为相应始发时刻可调整度下各新增运行线较给定最短停时延长值之和. 表2 实验计算结果Table 2 Experiment results始发时刻可调整度/min 10 20 30 40 50 60算法运行时间(C/L)/s 4/6 23/14 123/24 620/39 1 184/58 2 087/72迭代次数(L)5 5 6 8 9 9目标函数值(C/L)3 109 630/3 109 183 3 159 280/3 156 936 3 169 444/3 169 163 3 179 317/3 179 021 3 179 326/3 179 196 3 199 090/3 199 008新增运行线数(C/L)6/6 11/11 12/12 13/13 13/13 15/15新增列车平均旅速(C/L)/(km/h)254.38/253.32 257.42/256.86 251.85/250.49222.35/221.91 225.63/223.86 221.69/220.49表3 拉格朗日算法计算结果Table 3 Lagrangian algorithm results始发时刻可调整度/min 10 20 30 40 50 60新增运行线数量6 11 12 13 13 15始发时刻调整总时长/min 47 126 225 237 247 312始发时刻调整平均时长/min 7.83 11.45 18.75 18.23 19.00 20.80始发调整最大时长/min 10 17 24 32 43 59总停时延长值/min 10 15 39 58 51 71实验中随着始发时刻可调整域的增加，相较于根据给定的理想始发时刻推线，由于考虑了列车在站停时可在一定程度上延长，使得运行线求解空间增大，例如在始发时刻可调整度为60 min时，新增运行线在站停时可以在给定最短停时的基础上适当延长(总停时延长不超过10 min)，某站停时的适当延长可能会避免后续铺画时与其他运行线的潜在冲突，在此基础上遍历所有的运行线可行解，增加了新增运行线的铺画概率，因此，相较按理想始发时刻及最短停时推线，额外增铺了6条运行线；但同时由于全程停时的增加，引起了旅速在一定程度上的下降.进一步验证京沪高铁现有运行图框架下的最大能力，将各运行线始发时刻可调整度放宽至4 h，计算满足天窗限制(0:00-6:00)的可新增运行线数.由于簇约束影响，CPLEX无法在给定时间内得到最优解；拉格朗日算法经过200次迭代、509 s后由于迭代次数达到设定上限终止，共铺画了有效运行线18条，说明在算例框架下京沪高铁通过能力已接近饱和，进一步增开列车需对原有框架做出一定调整.5 结论针对给定框架下增铺运行线问题，基于时空网络构建整数规划模型，采用基于拉格朗日松弛的启发式算法求解，实例验证得到结论如下：(1)采用始发时刻推线方法，算例所述情况下能额外铺画9条运行线，而拉格朗日算法能够铺画15条运行线.(2)除始发时刻可调整度±10 min情景外，拉格朗日算法的求解速度均优于CPLEX.(3)随着始发时刻可调整度的增加，模型规模急剧增长，CPLEX所需的求解时间快速增加，而拉格朗日算法计算时间增加较平缓，计算效率优势明显.(4)始发时刻可调整度由10 min增加至60 min时，由于各运行线可行解范围增加，可增铺的运行线由6条增加至15条.(5)始发时刻可调整度4 h条件下，CPLEX无法在给定时间内求得最优解，拉格朗日算法在现有框架下最多增铺了18条运行线.在原列车运行图框架不变条件下，新增运行线铺画受既有运行图框架限制较大，下一步将研究既有列车运行图框架可部分调整条件下所需调整的运行线并给出调整方案.【相关文献】[1]CAPRARA A,FISCHETTI M,TOTH P.Modeling and solving the train timetablingproblem[J].Operations Research,2002,50(5)：851-861.[2]孙焰,李致中.单线区段货物列车运行图的一种优化方法[J].铁道学报,1991,13(1)：60-71.[SUN Y,LI Z Z.The scheduling model and its algorithm for obtaining the optimal travelling of trains on a single-track line division[J].Journal of the China Railway Society,1991,13(1)：60-71.][3]BRÄNNLUND U,LINDBERG P O,NÕU A,et al.Railway timetabling using lagrangian relaxation[J].Transportation Science,1998,32(4)：358-369.[4]彭其渊，王宝杰，周党瑞.基于实用的一种网络列车运行图计算方法[J].西南交通大学学报,1999,34(5)：588-593.[PENG Q Y,WANG B J,ZHOU D R.A practical algorithm for making train diagram of railway network[J].Journal of Southwest Jiaotong University,1999,34(5)：588-593.][5]郑亚晶,张星臣,陈军华,等.单线铁路成对非追踪平行运行图最小周期时间的混合整数非线性规划模型[J].中国铁道科学,2012,33(2)：100-106.[ZHENG Y J,ZHANG X C,CHEN J H,et al.Themixed integer nonlinear programming model for the minimum cycle time of a paralleltrain working graph without tracking operation on single-track railway[J].China Railway Science,2012,33(2)：100-106.][6]聂磊,张渊,武鑫.计算机编制周期性列车运行图关键技术[J].中国铁道科学,2014,35(1)：114-121.[NIE L,ZHANG Y,WU X.Key technologies for computer generation ofcyclic train timetable[J].China Railway Science,2014,35(1)：114-121.][7]谢美全,聂磊.周期性列车运行图编制模型研究[J].铁道学报,2009,31(4)：7-13.[XIE M Q,NIE L.Model of cyclic train timetable[J].Journal of the China Railway Society,2009,31(4)：7-13.] [8]CACCHIANI V,CARPRARA A,TOTH P.Scheduling extra freight trains on railway networks[J].Transportation Research Part B：Methodological,2010,44(2)：215-321. [9]CACCHIANI V,TOTH P.Nominal and robust train timetabling problems[J].European Journal of Operational Research,2012,219(3)：727-737.[10]FISHER M.Optimalsolution ofvehicle routing problems using minimum K-trees[J].Operations Research,1994,42(4)：626-642.[11]FISHER M.The lagrangian relaxation method for solving integer programming problems[J].Management Science,2004,50(12)：1861-1871.。

拉格朗日松弛对偶问题的一个改进次梯度算法何方国【摘要】拉格朗日松弛法是处理整数优化问题的一个重要方法。

针对利用次梯度算法求解拉格朗日松弛对偶问题时容易出现收敛速度较慢及计算效率低等问题，对次梯度算法进行了改进：结合当前次梯度和历史次梯度的线性组合给出新的迭代方向，然后决定合适步长。

同时证明了算法的收敛性及有效的消除迭代过程中的锯齿现象。

将改进的拉格朗日松弛的次梯度算法用于解决 TSP 问题，数值计算结果表明，改进的次梯度算法比普通次梯度算法收敛较快，说明了改进算法的有效性。

【期刊名称】《长江大学学报（自然版）理工卷》【年(卷),期】2016(013)004【总页数】5页(P1-5)【关键词】拉格朗日松弛算法;次梯度;优化问题;对偶【作者】何方国【作者单位】黄冈师范学院数理学院，湖北黄冈 438000【正文语种】中文【中图分类】O221拉格朗日松弛算法(LR)已经成功的应用于许多优化问题，如网络优化问题、生产调度问题、选址问题及其他整数优化问题等[1，2]。

在拉格朗日松弛算法中, 求解拉格朗日对偶问题非常关键,一般采用次梯度优化算法来解决。

但其方法在优化过程中容易出现收敛速度较慢及计算效率低的特点，这主要是在迭代过程中方向和步长的选择影响着算法的性能。

为此, 一些学者已提出了求解拉格朗日松弛问题的改进方法：文献[3]给出了一种指数形式的拉格朗日对偶方法，并证明其收敛性；文献[4]提出利用上次迭代的次梯度的信息来改进步长的次梯度算法；文献[5]则将模糊的概念引入次梯度的求取中, 提出了模糊次梯度算法。

这些方法在求解性能上都有所提高，但有的计算比较复杂。

下面，笔者给出一个改进方法，并将改进的拉格朗日松弛的次梯度算法用于解决TSP问题来证实算法的有效性。

考虑如下有约束的优化问题：其中,I= {1, 2,…,m}，X为一个有限集； f: Rn →R和gi:Rn →R分别为X上的连续凸函数。

问题(1)被称为原问题。