基于聚类的大规模即时配送问题研究

《基于聚类的大规模即时配送问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10255学号：2160874中图法分类号：U492基于聚类的大规模即时配送问题研究RESEARCHONLARGE-SCALEINSTANTDISTRIBUTIONBASEDONCLUSTERING学科专业：物流工程作者姓名：张延强指导老师：戴韬答辩日期：2018年5月16日东华大学学位论文原创性声明东华大学学位论文原创性声明本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对

2、所写的内容负责，并完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日东华大学学位论文版权使用授权书东华大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本版权书。本学位论文属于不保密□。学位论文作者签名：指导教师签名：日期：年月日日期：年月日摘要基于聚类的大规模即时配送问题研究摘要车辆路径问题

3、(VRP)是企业开展物流活动过程中的重要问题之一，随着配送时效在物流经济活动中发挥着重要的作用和客户时间意识增强，快速响应、安全可靠的车辆路径问题研究显得愈加重要，特别是随着电商的蓬勃发展和推动，区域内大规模客户订单的即时配送问题出现频率越来越高，并逐渐成为城市配送研究的重要方向，因此该类问题的研究变得更有必要。但现有的理论应用到该问题存在难点：精确算法或者启发式算法的求解时间随着研究问题的规模增大呈指数式增加，显然求解时间太长，并不适用，本文采用两阶段算法，先聚类后排程，降低问题求解规模的同时使用高效的算法实现客户订单配送，不仅可以提供更快捷、准时、有效的配送服务，

4、而且有助于企业节约成本，合理利用车辆和人力资源，因此该问题研究具有现实意义和必要性。本文在查阅国内外VRP和聚类理论研究文献后，结合即时配送行业背景和H公司存在的问题，将两阶段启发式算法引入到大规模即时配送问题研究中：第一阶段，订单聚类处理，分别用贪婪聚类(最近邻算法)和最大最小距离聚类对区域内的所有订单划分，降低问题规模、计算量，提高求解效率，同时对两种聚类方式从类内聚合度CP、类间间隔性SP等两个聚类有效指标上进行分析，初步评定聚类I摘要效果好坏；第二阶段，前一阶段聚类处理将车辆问题转化成TSP问题，为了量化控制时间对客户满意度的影响，论文引入时间惩罚系数，进而建

5、立带时间窗的车辆调度模型(TSPSTW)，使用全局搜索能力较强的遗传算法求解模型，以动态交叉、变异算子替代传统静态算子，使得求解更快、结果更优，从而为快速、有效地优化时间窗问题创造条件。客户订单聚类和配送均通过MATLAB仿真实现，以算例C401为例，仿真运行算例TSPSTW模型，得到订单配送计划表，包括配送路线、总成本、总里程、订单时刻表等，依此得到所有订单的配送计划。从运行效率上，只需7-8分钟完成501个订单聚类和配送，进一步验证了两阶段算法的高效性，最后结合聚类指标和配送经济指标对比两种聚类方案的优劣，为H公司选择适合的调度计划提供参考。关键词:VRP遗传算法

6、聚类时间窗IIABSTRACTRESEARCHONLARGE-SCALEINSTANTDISTRIBUTIONBASEDONCLUSTERINGABSTRACTVehicleRoutingProblem(VRP)isoneofthekeyissuesinthelogisticsdistributionprocess.Asthetimeplaysanincreasinglyimportantroleinlogisticsandeconomicactivitiesandcustomers’awarenessofatime-effectivelogisticsdistrib

7、utionisbecomingmoreintense,theresearchonfast-response,safeandreliablevehicleroutingbecomesmoreandmoreimportant,especiallywiththevigorousdevelopmentandpromotionofe-commerce,thefrequencyofimmediatedeliveryoflarge-scalecustomerordersintheregionhasbecomemorefrequentandhasgraduallyb