取货需求不确定的VRPSDP在线策略研究

发布时间：2020-08-31 15:04

　　 VRPSDP(Vehicle routing problem with simultaneous pickup and delivery,同时取送货车辆路径选择问题)是学术界和物流业关注的热点问题。现有对同时取送货车辆路径选择问题的理论成果一般假设送货量和取货量完全已知,建立静态优化模型,设计启发式算法进行求解,但实际中取货量可能是不确定的;对于取货量不确定的研究,通常假设取货量服从某一分布,寻求平均意义上的最优方案,这可能给出离实际最优解相距甚远的解,无法满足实际需求。针对现有研究不足,本文考虑取货需求不确定的情形,采用在线问题与竞争策略的理论与方法,从取货需求无法预知和有限预知两个角度进行研究,设计在线策略,分析策略的不同情形证明竞争比并分析策略的执行效果,为物流运输公司制定路径选择方案提供决策依据。主要工作和创新性成果如下。针对取货需求不确定的同时取送货车辆路径问题,考虑车辆对需求点取货量无法预知且每个需求点只能服务一次的情形,在完成送货任务的前提下,以取回的货物尽可能多为目标,建立在线车辆路径选择模型,分析中途不可卸货和中途可卸货两种情形,并针对两种不同情形分别设计先多后少策略和剩余空间可调策略。证明中途不可卸货情形下先多后少策略竞争比为1/(β-α-(n-1)λ),已取货物中途可卸情形下剩余空间可调策略的竞争比为1/(β-α),比较分析表明已取货物中途可卸情形下剩余空间可调策略的执行效果要好于中途不可卸货情形下先多后少策略。最后通过实例分析验证两种策略的有效性。针对取货需求不确定的同时取送货车辆路径选择问题,考虑车辆对需求点取货量有限预知,即车辆从配送中心出发且在出发前已知每个需求点的送货量,但只有到达某一需求点时才能获知该需求点和下一个即将到达需求点的取货量,在每个需求点只服务一次且完成所有需求点送货任务回到配送中心的情形下,以取回的货物总量尽可能地多为目标,建立取货需求有限预知的同时取送货车辆在线路径选择模型,分析中途不可卸货和中途可卸货两种情形,并针对两种不同情形分别设计Select large策略和PUPI策略并证明策略的竞争比,得到中途不可卸货情形下Select large策略竞争比为1/(β-α-(n-1)λ),已取货物中途可卸情形下PUPI策略的竞争比为1/(β-(m+t)θ)。最终将中途不可卸货情形下Select large策略与已取货物中途可卸情形下PUPI策略进行对分析,发现已取货物中途可卸情形下PUPI策略的执行效果要好于中途不可卸货情形下Select large策略。最后通过实例分析验证策略的有效性。本文设计的取货信息不确定的同时取送货在线路径选择策略,可为物流运输企业制定车辆路径选择方案提供决策依据。
【学位单位】：西安工业大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：F274;F724.6
【部分图文】：

承载能力,车辆,站点

快递公司将城市中的众多站点按照其所在地理位置划分为若干区域，每个区域内的站点对应着一个配送中心为其提供取送货服务。为提高效率，快递公司希望在配送中心派出的车辆满足所有送货需求的同时，能够尽可能多的将站点揽收的包裹带回配送中心，避免车辆对站点进行二次服务，以提升配送效率。上述问题就是国际学术届以及物流行业关注的热点——同时取送货车辆路径选择问题，即 VRPSDP（Vehicle routing problem withsimultaneous pickup and delivery）。VRPSDP 是指车辆从配送中心出发为指定需求点送货的同时也需要将该需求点需要带回配送中心的货物取回情形下，如何选择车辆路径使得车辆在完成送货的同时完成取货服务请求最多或完成所有取货服务请求下运输成本最小。在实际中，快递公司从配送中心派出的车辆一般以单次车辆运输成本尽可能小为目标，或是按照由近及远的原则对站点进行服务，或是按照由远及近的原则对站点进行服务。按照这种路径选择方式对站点进行取送货服务时，由于车辆配送过程中各个站点依然在进行揽件，每个站点待取回的包裹数量难于确定，因此会出现车辆剩余较大承载能力但取回的货物量很少，造成车辆剩余承载能力的浪费（如图 1.1）或者到达站点后车辆剩余的载货能力无法满足站点的取货需求。（如图 1.2）。

货物,车辆,站点

函数图像,坐标系,函数图像,剧烈变化

图 3.3 不同坐标系中不同( n 1)λ值下的竞争比函数图图 3.4 同一坐标系中不同( n 1)λ值下的竞争比函数图 3.3 可知，随着( n 1)λ增长，函数图像不会剧烈变化。由图 3.4 可知，随着( n 争比图像会随之上升，即竞争比会随着( n 1)λ变大而变大。

【参考文献】