多仓库带容量约束弧路径问题的近似算法和多项式算法

发布时间：2024-12-02 21:58

　　随着现代物流行业的崛起,企业为了降低运输成本,越来越重视对车辆路径问题(Vehicle Routing Problem,简称 VRP)的研究。弧路径问题(Arc Routing Problem,简称ARP)与VRP问题一样,同样有着重要的现实意义和研究价值。二者的不同之处在于,VRP以点为服务对象,而ARP以边为服务对象。经典的弧路径问题只有一个仓库点,但实际应用中的很多问题需要利用多个仓库点的弧路径问题建立数学模型。因此,本文研究了多仓库带容量约束弧路径问题(Multi-depot Capacitated Arc Routing Problem,简称MCARP),将经典的弧路径问题推广到更为实际的多仓库情形。针对MCARP的不同变形问题,我们提出了近似算法和多项式算法。本文主要分为以下七个章节。第一章介绍了研究背景并对组合最优化问题进行了简单描述,还阐述了本文相关问题的最新研究进展。第二章描述了本文所涉及的符号和概念。第三章介绍了非固定终点MCARP问题,给定一仓库点集D,每辆车可从任一仓库出发,最终可返回至任意仓库,目的是找到服务了所有需求边的若干条路径,使得总路径长度最短。将非固定...

【文章页数】：44 页

【学位级别】：硕士

【部分图文】：

图５．?１算法ＭＲＰＰ１的一个例子??

第１６页???华东理工大学硕士学位论文??：二－…藝??ｉ?ｄ３?ｄ２??（ａ）需求边集；？和仓库点集￡）?（ｂ）完全图Ｇ??ｄｉ?ｄ２?ｃ／３?ｔ?（ｊ２??ｎ３＊?ｎ５?＂３?‘?ｎ５?１??（ｃ）最小权约束生成森林Ｆ?（ｄ）?Ｆ上奇度点的完美匹配Ｍ??■翁??ｒ？５?Ｖ４?....

本文编号：4013972