详情

原文传递多商品可拆分的取送货车辆路径优化问题研究

论文题名：	多商品可拆分的取送货车辆路径优化问题研究
关键词：	取送货车辆;路径优化;拆分模式;遗传算法
摘要：	在取送货车辆路径优化问题(Pickup and Delivery Vehicle Routing Problem)中，每个客户对不同的商品类型有不同的请求（包括进货请求和出货请求），在对某种商品有出货请求的客户处取得的商品，可以满足多个对该商品有进货请求的客户。同时对某种商品有进货请求的客户，可以被多个具有出货请求的客户满足。这类问题在现实生活中被广泛应用，例如共享单车再平衡问题，企业多仓储的再平衡问题等，具有很强的理论研究意义和实际应用价值，未配对取送货车辆路径优化问题作为取送货问题中的一个重要的研究方向越来越受到学者的重视。本文针对未配对取送货车辆路径优化问题，从多个角度进行分析研究，包括多个商品类型，不同的客户请求拆分模式，车辆中途是否可回仓库补货或卸货，车辆数量是否固定以及仓库的数量。具体研究内容如下: 　　1.考虑单车库单仓库且在同一位置的，可拆分可补货的多商品取送货车辆路径优化问题，仓库可以提供所有的商品类型，拆分模式为客户的出货请求种类和数量都可拆分，客户的进货请求种类可拆分每种类型商品的数量不可拆分，车辆行驶过程中在满足最大行驶距离约束的前提下可以去仓库进行补货或卸货，在满足所有客户请求的前提下最小化总成本，包括总行驶成本和车辆固定成本。结合问题特点，建立数学模型，并设计相应的遗传算法来求解该问题，详细阐述了算法的实现过程，包括编码方式，车辆初始载重的确定，种群初始化方法，交叉变异策略和修复策略，局域搜索策略等。在此基础上，探讨不同角度下的问题的求解方案以及进行相关的实验。包括不同的固定车辆数角度，拆分模式为出货请求和进货请求种类数量都可拆分时问题的求解方案以及相关实验，中途不回仓库对问题的影响，车库和仓库不在同一位置对问题的影响，验证了算法的可行性和稳定性的同时，也对问题进行了深入的探究。　　2.在问题1基础上，考虑单车库多仓库且不在同一位置，中途可回仓库补货或卸货，拆分模式同问题1，仓库和商品相容，目标函数同问题1。提出仓库和商品相容性的问题，不同的仓库对商品类型的供应不同，仓库和商品相容即车辆在仓库可以装载的商品类型取决于仓库可以提供的商品类型，可以卸载的商品类型与仓库可以提供的商品类型无关。不相容即车辆在仓库可以装载和卸载的商品类型都取决于仓库可以提供的商品类型。结合问题特点建立数学模型，针对仓库和商品相容和不相容两种情况下的仓库选择问题和车辆从仓库出发时初始车载的确定问题给出具体的解决方案。并设计相应的遗传算法求解该问题，详细阐述了算法的实现过程，包括编码方式，种群初始化方法，交叉变异和修复策略，局域搜索策略等，在此基础上，探讨不同角度下的问题的求解方案以及进行相关的实验。包括不同的固定车辆数角度，拆分模式为出货请求和进货请求种类数量都可拆分对问题的影响，中途不回仓库对问题的影响，不仅验证了算法的可行性和稳定性，也对问题进行了深入的探究。
作者：	李露露
专业：	系统工程
导师：	庞哈利
授予学位：	硕士
授予学位单位：	东北大学
学位年度：	2018