非危险废物物流链优化

非危险废物物流链的优化昆汀·阿德里安·托诺引用此版本：昆汀·阿德里安·托诺。优化非危险废物的供应链运筹学[cs.RO]。2017年，大西洋矿业-电信国立高等学校法语。NNT：2017IMTA0058。电话：01729672HAL ID：电话：01729672https://theses.hal.science/tel-01729672提交日期：2018年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire博士论文昆汀·T·奥诺为获得以下文件而提交的备忘录布列塔尼-卢瓦尔河地区国家高等矿业-电信大西洋学院博士学位布列塔尼卢瓦尔大学印章下博士学校：数学和ICT（MathSTIC）专业：计算机科学，CNU 27研究单位：南特2017年12月18日答辩论文编号：2017IMTA0058优化非废物物流危险的陪审团报告员：M. Philippe LACOMME，克莱蒙特奥弗涅大学HDR讲师M. Christian PRINS，特鲁瓦技术大学大学教授考试员：M. Pierre DEJAX，IMT大西洋大学教授M. OlivierPÉTON，大西洋IMT教授M. Fabien TRICOIRE，林茨约翰内斯·开普勒大学助理教授Thomas YEUNG，IMT Atlantique高级讲师Valérie MÜLHAUPT女士，Brangeon Services研究工程师博士生导师：Nathalie BOSTEL女士，南特谢谢你首先，我要感谢你知道如何确定要遵循的路线，我还要感谢Romain和Valérie，感谢他们从项目一开始就给予我的信任，你们的鼓励和支持是这次长途旅行所需的燃料。感谢您对优化世界的开放态度，感谢您每天对我的想法和建议的好奇心，感谢您的持续投资，即使在怀疑或沮丧的对于评审团成员，我衷心感谢Philippe Lacomme和Christian Prins，他们同意担任我论文的报告员，并感谢我们在会议和暑期学校期间进行的我还要感谢Fabien Tricoire在研究了我在整个博士学位期间在后续委员会的工作后，同意参加我的论文评审团。最后，感谢奥利维尔在不寻常的情况下主持我的论文答辩，感谢你对我的手稿的批判性但专业的看法。很高兴再次与您合作。致我在Brangeon的所有同事和朋友。J’ai pu m’épanouir personnellement et professionnelle- ment我感谢你每天的快乐和你的善良。特别要提到的是设计办公室的冠军，Hélène，Sandrine，Ludo，Aline，Tsiory，Hugo和Cathy。我珍惜我们一起分享的一切，尤其是Wor-King Night Fever。你让我在事业上成长，给了我比我能回报的更多的东西。J’espère néanmoins que les quelques servicesdéveloppés tiendront aussi bon que l’orchidée du对于所有的火车朋友，托马斯，马丁和上面提到的许多人，我对这些美好的生活片段表示巨大的我已经错过了南特和尚普托塞之间的讨论、游戏、笑声和减压时刻。我不知道谁保持着从LaPommeraye到火车站的赛道记录，但萨克斯管应该在这些感谢中占有特殊的地位。感谢我有幸在矿山走廊里遇到的所有人，感谢我们许多充满激情的科学讨论，感谢由此产生的所有不那么理性的过度行为。感谢我所有的博士生朋友和我在这三年里遇到的许多研究人员，他们向感谢以前的博士生，他们为我的成功铺平了道路，并把所有的线索都传给了我。我还要感谢泽维尔、叶夫根尼和安东尼向我介绍了运筹学这门非凡的学科。很高兴在办公室、会议或Cervoisserie周围与您见面感谢我所有的朋友，圣米歇尔和声的音乐家，我的第二个家庭，他们支持我超过15年，我总是很高兴与他们分享我们的排练（和几杯酒）。我每天都意识到属于并参与这场非凡冒险的机会。特别要提到克劳德，我的老师，厨师和朋友，没有他，我永远不会34音乐的幸福献给玛丽昂，她和我一起生活了七年多。感谢你们在过去的几年里，在我经历的怀疑和压力的时刻，对我们过去和未来所有的生活计划，以及我们分享的所有爱，给予了无条件的支持。我还要感谢我美丽的家人，斯蒂芬、纳代格、托马斯、马蒂奥、罗伯特和凯西，感谢你们在整个冒险过程中的鼓励和支持。习惯上把最我感谢我的父母，雅克和凯瑟琳，让我选择自己的道路，并鼓励我，无论我的你一直都很警惕 我哥哥和我什么都不缺，全心全意地参与了我们的成长。 我还要感谢我的兄弟西尔万，感谢我们分享的所有非凡的时刻和激情。我希望我们有很多快乐的时刻可以分享。我爱你们三个。最后，我把这篇论文献给我的祖母伊冯。即使经过优化，通往博士学位的道路也是漫长而曲折的，但我很高兴能目录1导言9一、垃圾收集网络的战术规划2单周期战术流优化问题的描述与求解2.1流优化问题的介绍2.1.1废物产生者182.1.2转移部位182.1.3出口192.1.4最终客户192.1.5活动和宣传活动192.1.6运输工具202.1.7目标和决定212.2问题21的最新技术水平2.3MC-MMFP-T22的建模2.3.1注释232.3.2多模态232.3.3变量242.3.4目标功能242.3.5约束252.4实验和结果252.4.1生成实例的解决262.4.2解决2.5软件开发282.6结论303多周期战术问题的描述与解决3.1单周期方法的局限性3.1.1季节性333.1.2转移能力和活动343.2问题的建模343.2.1问题的陈述343.2.2模型353.3实验和结果373.4结论和展望4156目录二、优化自愿投入中的垃圾收集路线434确定性旅游问题的描述454.1问题说明454.1.1时间段和范围454.1.2集装箱464.1.3产品和数量464.1.4存款474.1.5出口474.1.6车辆484.1.7目标和处罚494.1.8决定和解决办法494.2最新技术水平4.2.1多周期范围和库存504.2.2有中间存款的524.2.3固定异构舰队534.2.4多个时间窗口534.2.5多产品问题544.2.6问题的分类544.3数学公式554.3.1评级554.3.2变量554.3.3目标功能574.3.4限制584.3.560型的改进4.4结论615确定性旅游问题的解决635.1ALNS全球方法635.1.1方法的选择635.1.2解决方案的表示5.1.3主算法645.1.4销毁操作员655.1.5维修操作员685.1.6操作员的自适应选择695.1.7接受解决方案735.1.8收敛检测735.2行动的可行性5.3实验和结果785.3.1VRPTW78的决议5.3.2IRP 79的决议5.3.3完全解决805.3.4真实案例中的实验835.4结论886随机操作问题的特征896.1L’apport irrégulier en déchet6.2灌装危害的研究6.3库存管理中旅游问题的演变956.3.1集装箱溢出的预期成本6.3.2车辆溢出的预期成本材料表76.4结论967随机运算问题的求解977.1最新技术水平7.2ALNS 99方法的调整7.2.1车辆溢出997.2.2溢出容器1017.3实验1017.3.1真实案例的模拟1027.3.2减少风险的模拟1037.4结论和观点1048一般结论107首字母缩略词列表109表列表111图113表词汇表115参考书目1171简介在这篇论文中，我们提出了一系列的研究工作，以优化废物的收集和运输为主题，这是现代工业社会的一个真正的经济和生态问题。据估计，根据来自家庭的废物几乎占10%法国的总产量，而工业活动（18%）和建筑废物（50%）是需要回收和处理的废物的主要来源。面对这篇论文是IMT Atlantique的南特数字科学实验室（LS2N）和Brangeon集团之间的CIFRE合作的结果，Brangeon集团专门在本文的其余部分，我们发展了我们的研究工作，旨在解决该行业的公司在不同决策级别遇到的实际优化问题，这些问题构成了与物流网络管理相关的决策战略决策包括企业的所有总体组织选择，通常是在长期范围内制定的它包括网络的创建和修改、不同的发展战略以及最重要的服装选择。战术层面包括中期决策，以优化网络组织，同时尊重已建立的网络和在更高层面制定的战略方向。这一类别包括网络站点之间的流量管理、活动规划和大多数短期和中期的所谓功能性投资。最后，运营决策层代表活动的日常管理，如运输组织、生产活动规划、材料和人员管理（时间表）以及库存管理，例如物流仓库。在本文中，我们提出了两个优化问题，分别1. http://www.ademe.fr/dechets-chiffres-cles-edition-20169第一章第十章引言科学目的本论文的目的是形式化和解决与工业和家庭非危险废物的管理和运输相关的新的优化问题。我们对文献中已经确定的两个问题特别感兴趣：— 网络中流量的战术规划和— L’optimisation通过一个出口（倾倒场）沿其路线。论文计划为了解决上述问题，我们制定了以下计划，分为两部分。本文的第一部分，包括第二章和第三章，讨论了废物收集、运输和处理的多式联运网络的战术优化。本论文的第二部分由第4、5、6和7章组成，其中我们研究了一个自愿输入点（VAP）废物收集路线的操作优化问题在第一部分中，第二章介绍了优化废物流网络的战术问题它还描述了单周期分辨率的数学模型，以及我们为简化这种网络的多模态层而进行的预处理最后，我们发现了解决问题的多个随机和真实实例的第一系列实验，第3章阐述了我们的单周期方法的主要局限性，并提出了一个多周期的流量优化问题建模，以优化一个网络，其废物产生受到不同的季节性在本论文的第二部分，第4章描述了Brangeon公司遇到的VAP废物运输的工业问题，并提出了优化附近车辆路线的主要科学工作和出版物的最新技术水平然后，它解决了一个新的问题最后，我们找到了一个线性数学模型，用于求解减小的实例。第5章提出了一种使用自适应大邻居搜索（ALNS）的自适应邻居启发式算法来解决上一章中描述的操作问题的方法。在这里，我们提出了算法和方法，用于在几乎恒定的时间内评估在现有收集路线中插入新交叉点的可能性我们证明了第6章在随机框架下研究了用户填写自愿贡献点的随机性，并表明可以使用正态分布对其进行忠实建模在本章中，我们还提出了一个随机版本的操作问题，其中容器的填充是不确定的。特别是，我们建立了一个数学模型，作为时间段的函数，预期的第7章提出了一个调整我们的ALNS方法的随机轮生收集问题与库存管理之前提出。我们通过一系列的实验证明11通过这种新方法获得的解比我们的确定性算法的解鲁棒得第8章总结了本论文的全部工作和取得的成果。我们提出了我废物收集网络的战术规划1315在这一部分中，我们从战术的角度，即在平均时间段（大约一年）内，通过研究和解决包括中间加工节点的多式联运网络中的流程优化问题，处理废物物流管理的优化。在第二章中，我们提出了单周期战术优化问题和求解该问题的数学模型。然后，我们在第3章中介绍了这项工作的多周期版本，该版本允许除了对专门用于废物处理的复杂物流网络进行建模外，本研究的主要创新之处2单周期战术流程优化问题的描述与求解在本章中，我们介绍并优化了一个多式联运废物收集和运输网络的运作，该网络将废物从其多个来源收集并运输到其处理和回收中心。这样的网络由专门处理废物的物流提供商管理。该网络的优化部分取决于正确选择不同点之间使用的运输工具，以及使用转运平台储存和重新装载不同的废物。这些平台还在第2.1节中，我们介绍了本节中研究的优化问题的不同方面和约束我们在2.2节中概述了与我们的问题相关的最新研究和工作，然后在2.3节中提出了一个数学模型来解决一个新问题，称为变换的最最后，我们在2.4中介绍了在随机生成的实例上使用该模型进行的一系列在第2.5节中，我们还描述了一个基于Web的应用程序的实现，该应用程序用于对目前2.1流的优化问题的介绍在本节中，我们将介绍第一和第二部门企业收集和运输带入废物场或产生的废物的运作情况。这些废物被放置在称为垃圾箱的容器中，通常在10立方米到40立方米之间变化。它们通常被散装丢弃，但一些（外部）设备允许产品被压实，从而增加了垃圾箱中允许的废物量。这种废物的收集是通过一种称为自卸车或Ampliroll®的专用车辆从垃圾箱中取出来完成的，Ampliroll ®有两个主要的收集过程。在轮换期间然后将该垃圾箱带回底部清空，称为出口。在现场和出口之间的往返过程中他们1718第二章。单周期优化空桶交易所现场满桶出口空车清空满桶现场空桶出口车辆在没有装载的情况下离开，收集垃圾箱并将其清空到出口。与轮换不同的是，车辆必须将清空的垃圾箱送回生产商的现场。通常，当客户/废物产生者拥有自己的垃圾箱或配备了特定的垃圾箱时，会进行此操作。当垃圾箱一旦在出口处清空，就可以用于下一次旋转时，旋转变得更加经济相反，刚刚完成一次往返的车辆可以立即前往下一个生产商进行第二次因此，两种工艺中的一种的选择取决于自卸车之间的兼容性以及收集点和倾倒口之间的距离。人们还猜测，在(a) 现场轮换(b) 返回时清空FIGURE 2.12.1.1废物产生者生产者对应于不同的废物收集来源。例如，这一组包括公共垃圾场以及使用垃圾箱处理垃圾的公司和建筑工地。一旦生产商注意到其一个集装箱已装满，他就提出收集请求（轮换或往返），物流供应商必须在合同期限内（通常为24至48小时）执行该请求根据自卸车和相关设施（压实机、设备和安全规则）的可达性，每个生产商都兼容一种或多种运输方式根据生产商的要求，收集的废物的目的地可以是免费的或固定的。这被称为交付请求，通常是到外部站点。2.1.2转移部位转运地点是中间地点，主要有两个作用：通过废物处理进行大规模处理和储存/重新装载到更经济的运输方式。每个转运站点都有为每个流定义的库存和准入能力接收能力是指现场在此期间允许运输的废物的法定数量。2.1. 流优化问题的介绍考虑。由自卸车运来的废物通常被储存并重新装载到更经济的车辆（半挂车、河流或铁路线生产商的个人收集服务是最昂贵的，类似于物流系统（邮政递送、计算机网络）最后一英里的管理问题，其除了通过改变运输方式进行大规模处理外，转运地点还允许进行废物分类或包装（粉碎、压制），称为活动，目的是降低转运成本，或将流的几种成分分离并转运到出口或最终客户，如下所示2.1.3出口处与另一方面，后者没有存储限制，因此它们构成了物流网络的第一组出口点，产品被运送到这些出口通常是物流中心，能够一些废物由生产者和使用者直接带到转运地点和出口。因此，这两种类型的节点产生流的一部分，就像产生节点但是，它们的收集不是强制性的在出口处处理的产品可重新发送给下述最终客户。2.1.4最终客户"客户"是废物和产品的第二个运输点。他们代表回收产品的客户和批发商/出口商。要交付给每个客户的产品/废物的数量是已知的，交付的起点也是已知的。表2.1总结了网络中不同节点的特征。废物贡献产品转换存储需要生产商转移站点客户端···重要的次要无限无限集合交货期表2.12.1.5活动和活动在网络的不同点（生产者、内部站点）收集的废物在被输送到出口或最终客户（流出）之前可能会经历多次修改。例如，在垃圾场收集的木材通常被粗磨（缓慢）以去除最重要的废料，然后通过第二次（快速）研磨和筛选过程以获得客户所需的质量和尺寸。这两个阶段可以在两个不同的地点进行。粗磨减少了木材在车辆中所占的空间，而车辆的可用体积通常是主要的限制因素。因此，这种转变降低了将废物转移到出口或客户的成本。活动是指对一个或多个废物流进行的任何操作。该定义包括简单的加工，如木材研磨或塑料压制，但也包括涉及多个输入或输出流的更复杂的操作。