带容量和最大工作时间约束的集散货物车辆路径问题研究

发布时间：2020-05-21 02:05

【摘要】：已有同时集散货物车辆路径问题中一般假设客户间的需求是相互独立的,车辆从配送中心出发,送货至各客户点并从客户处集货后返回配送中心；而在客户取送货需求存在成对关系的集散货物车辆路径问题中,客户只有取货或者只有送货的需求。但是在大型制造企业的生产园区内,各工厂不同库位之间原材料、半成品运输通常存在成对的取送货关系,并且各个库位既需要收取来自其他库位或者仓库的货物,又需要向其他库位提供半成品。本文针对此,提出了一种带容量和最大工作时间约束的集散货物车辆路径问题(Capacitated Pickup and Delivery Problem with Max Duration, CPDPMD).在该问题中,各个客户可以同时有取货和送货的需求,而且取货点和送货点之间有成对关系,目标在于在满足车辆载重约束和最大工作时间约束的情况下选择运输成本最小的路径。该问题可应用于大型制造企业生产园区内原材料、半成品运输。本文为CPDPMD问题建立了以行驶里程最小为目标函数的数学模型,设计了改进的分散搜索算法。并对该算法从编码、多样性产生方法、参考集生成及更新方法、局域改进方法、子集产生方法和解组合方法六个方面进行设计和改进。首先基于贪婪插入算法设计多样性产生方法；其次基于局部搜索的思想对多样性解改进得到质量更高的解而后建立初始参考集,通过子集产生方法产生子集,有二元组、三元组、四元组和最好r个解；然后采用基于弧组合和扫描算法的解组合方法产生新解并更新参考集直至搜索结束最终得到优化结果。为了验证本文算法的有效性,首先通过修改带时间窗的VRPPD(Vehicle Routing Problems with Pickups and Deliveries)问题数据建立了CPDPMD问题的相关测试算例,然后进行算法参数实验,进而比较了算法改进前后的结果；为了进一步评估该算法的有效性,将该算法运用于求解CPDPMD问题的特例--单车辆的TSPPD (Traveling Salesman Problem with Pickup and Delivery)问题,并与精确算法比较,验证了该算法的有效性。此外,本文立足于企业的实际背景,将CPDPMD问题的模型应用于A公司配送中心、各工厂库位之间的原材料、半成品运输。通过对订单进行编码,订单需求划分、装卸货时间计算、配送点之间里程与配送时间的确定等一系列步骤实现订单标准化,使用设计好的算法求解标准化后的问题,得到园区内各个班次车辆行驶的最优路径,证明了模型的有效性及实用性。
【图文】：

示意图,示意图,客户,问题

本文研巧的ＣＰＤＰＭＤ问题，属于客户点之间的集散货物车辆路径问题，即取逡逑货需求与送货需求具有成对约束，但是与ＶＲＰＰＤ问题区别是：每个客户可同时逡逑有取货的需求和送货的需求。如图１－３所示，每个客户都有两种需求：取货需求ｄｐ和逡逑送货需求耍求如，如果客户只有取货需求，那么送货需求扣＝0，反之则相反。若逡逑根据客户点的需求类型将图１－３所示问题中的客户点吃分成取货点集合和送货点逡逑集合邋Ｋｄ，则邋＾）＝化，（２，【＇３邋山，＜５，逦＝邋｛／１，７２，７３，＿／４，７５，７６｝，由于邋ｉ＇２邋＝逦＝／３，＜１邋＝知逡逑之６邋＝八，故ｌ／ｐ邋ｎ邋单０。所Ｗ，ＣＰＤＰＭＤ问题可看作是ＶＲＰＢ问题和ＶＲＰＰＤ问逡逑题Ｗ的组合，更具一般性。逡逑

问题,客户,需求类型,车辆路径问题

本文研巧的ＣＰＤＰＭＤ问题，属于客户点之间的集散货物车辆路径问题，即取逡逑货需求与送货需求具有成对约束，但是与ＶＲＰＰＤ问题区别是：每个客户可同时逡逑有取货的需求和送货的需求。如图１－３所示，每个客户都有两种需求：取货需求ｄｐ和逡逑送货需求耍求如，如果客户只有取货需求，那么送货需求扣＝0，反之则相反。若逡逑根据客户点的需求类型将图１－３所示问题中的客户点吃分成取货点集合和送货点逡逑集合邋Ｋｄ，则邋＾）＝化，（２，【＇３邋山，＜５，逦＝邋｛／１，７２，７３，＿／４，７５，７６｝，由于邋ｉ＇２邋＝逦＝／３，＜１邋＝知逡逑之６邋＝八，故ｌ／ｐ邋ｎ邋单０。所Ｗ，，ＣＰＤＰＭＤ问题可看作是ＶＲＰＢ问题和ＶＲＰＰＤ问逡逑题Ｗ的组合，更具一般性。逡逑
【学位授予单位】：南京农业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP301.6

【相似文献】