详情

原文传递配送企业车辆路径问题模型与算法研究

论文题名：	配送企业车辆路径问题模型与算法研究
关键词：	物资配送;车辆路径问题;优化算法
摘要：	随着市场经济的发展，配送对经济活动的影响越来越明显。车辆路径问题(VRP)一直是配送活动优化的重要内容，是最大限度的降低配送成本、提高顾客满意度的保障。本文在全面综述了国内外车辆路径问题研究现状的基础上，主要针对配送企业的实际需求，研究了目前最常见、配送发展迫切需要解决的三种车辆路径问题，并给出了智能启发式求解算法。主要贡献如下: 　　1.考虑同时取送货的车辆路径问题(VRPSPD) 　　由于配送中顾客有送货和取货需求，企业需要构建产品正向配送和逆向回收相整合的配送系统。因此，本文设计了配送企业在考虑顾客有同时取送货需求时的车辆路径问题，并提出一种基于禁忌规则的模拟退火算法(HSA)求解。HSA算法借鉴禁忌搜索算法(TS)的思想，在退火过程中引入禁忌表，一定程度上避免曾经访问过的解，并加速了搜索过程。HSA算法首先使用剩余承载力和径向附加费(RCRS)算法求得一个可行初始解，然后使用4种邻域搜索方法在模拟退火算法(SA)框架下对初始解进行优化。　　为了检验HSA算法的有效性，采用国际上通用的Dethloff数据集(40个小型顾客规模算例)、Salhi和Nagy数据集（14个中型顾客规模算例）、Montane和Galvao数据集（18个大型顾客规模算例），优化目标是最小化车辆总行驶距离(TD)。因此，共使用了72个测试算例，顾客数从50到400不等。与文献中已知算法的计算结果比较，从解的质量角度分析，HSA算法是一种有效的算法，可以找到近似最优的车辆配送路径;从求解时间角度分析，由于求解时计算机的配置不同，虽然慢于其它算法，但求解时间是可接受的。　　2.考虑带时间窗和同时取送货的车辆路径问题（VRPSPDTW）　　除了顾客有同时取货和送货的需求外，配送中顾客往往还有具体的服务时间窗限制，为了提高服务质量，企业往往会考虑顾客的时间窗需求。因此，构建基于时间窗和同时取送货的车辆路径问题（VRPSPDTW）。提出一种并行模拟退火算法(p-SA)求解。p-SA算法利用多马尔科夫链(MMC)方法，整合同步和异步MMC策略，在主从模式下将传统的SA算法并行化。　　本文采用Wang和Chen数据集(65个小型和中型顾客规模的算例)，并将计算结果与GA算法的结果进行比较。测试结果显示提出的p-SA算法可以有效的求解该问题。并且，构造了30个顾客规模为200、400、600、800和1000的大型顾客规模的算例作为新算例。目前国际上尚无可用于计算大型顾客规模的算例，p-SA算法的结果可为后续学者通过大型算例测试算法有效性提供参考。　　3.考虑配送网点优化的车辆路径问题（2E-LRPSPDTW）　　随着城市中交通拥堵的日益加重，多数大中城市对厢式货车进入城区采取了一系列的限制措施。因此，对于配送企业无法通过厢式货车实现从中央配送中心到顾客的直接配送，需要在设施点与需求点之间建立中转站，通过小货车将从中央配送中心运来的货物，在区域配送网点通过电动三轮车进行中转，如此形成中央配送中心—区域配送网点、区域配送网点—顾客的两级配送系统。考虑配送网点选址，优化车辆配送路径，这是一个集成车辆选径和网点选址的问题(称为选址—路径问题，LRP)。本文构建带时间窗和同时取送货的两级选址—路径问题（2E-LRPSPDTW），提出并行模拟退火路径重连算法(p-SA-PR)求解。常规的求解LRP问题的方法是把选址问题和车辆路径问题作为两个独立的问题进行两阶段求解，这种方法没有考虑设施选址和车辆路径两个问题之间的影响和制约关系。p-SA-PR算法将LRP的解看做一个整体，通过对LRP的解的结构进行分析，重新进行设计和改进。　　为了检验提出的p-SA-PR算法的有效性，采用国际上通用的Nguyen数据集(24个算例)、Prodhon数据集(30个算例)、Sterle数据集（30个算例）。共使用了84个测试算例，顾客规模从8到200不等。与文献中已知算法的计算结果比较可知，p-SA-pR算法是一种有效的算法，可以在快速的时间内求解2E-LRPSPDTW问题。　　4.调研了CSYB配送企业，优化了CSYB的车辆配送路径。　　该企业有1个中央配送中心，55个配送网点，每天负责两次向北京五环以内的1622个社区送货。通过本文提出算法对CSYB企业现有配送路径进行优化。研究结果均表明本文提出的算法能够减少CSYB企业的配送车辆数和车辆行驶总距离。
作者：	王超
专业：	管理科学与工程
导师：	穆东
授予学位：	博士
授予学位单位：	北京交通大学
学位年度：	2015
正文语种：	中文