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

《取货需求不确定的VRPSDP在线策略研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、密级公开分类号U492.3工程硕士学位论文取货需求不确定的VRPSDP在线策略研究任宏光指导教师苏兵教授高晓斌高级工程师申请学位级别工程硕士工程领域物流工程2018年5月20日取货需求不确定的VRPSDP在线策略研究学科:物流工程研究生签字：学校导师签字：企业导师签字：摘要VRPSDP（Vehicleroutingproblemwithsimultaneouspickupanddelivery，同时取送货车辆路径选择问题）是学术界和物流业关注的热点问题。现有对同时取送货车辆路径选择问题的理论成果一般假设送货量和取货量完

2、全已知，建立静态优化模型，设计启发式算法进行求解，但实际中取货量可能是不确定的；对于取货量不确定的研究，通常假设取货量服从某一分布，寻求平均意义上的最优方案，这可能给出离实际最优解相距甚远的解，无法满足实际需求。针对现有研究不足，本文考虑取货需求不确定的情形，采用在线问题与竞争策略的理论与方法，从取货需求无法预知和有限预知两个角度进行研究，设计在线策略，分析策略的不同情形证明竞争比并分析策略的执行效果，为物流运输公司制定路径选择方案提供决策依据。主要工作和创新性成果如下。针对取货需求不确定的同时取送货车辆路径问题，考虑

3、车辆对需求点取货量无法预知且每个需求点只能服务一次的情形，在完成送货任务的前提下，以取回的货物尽可能多为目标，建立在线车辆路径选择模型，分析中途不可卸货和中途可卸货两种情形，并针对两种不同情形分别设计先多后少策略和剩余空间可调策略。证明中途不可卸货情形下先多后少策略竞争比为1/()β−−αλ()n−1，已取货物中途可卸情形下剩余空间可调策略的竞争比为1/()β−α，比较分析表明已取货物中途可卸情形下剩余空间可调策略的执行效果要好于中途不可卸货情形下先多后少策略。最后通过实例分析验证两种策略的有效性。针对取货需求不确定的

4、同时取送货车辆路径选择问题，考虑车辆对需求点取货量有限预知，即车辆从配送中心出发且在出发前已知每个需求点的送货量，但只有到达某一需求点时才能获知该需求点和下一个即将到达需求点的取货量，在每个需求点只服务一次且完成所有需求点送货任务回到配送中心的情形下，以取回的货物总量尽可能地多为目标，建立取货需求有限预知的同时取送货车辆在线路径选择模型，分析中途不可卸货和中途可卸货两种情形，并针对两种不同情形分别设计Selectlarge策略和PUPI策略并证明策略的竞争比，得到中途不可卸货情形下Selectlarge策略竞争比为1/

5、()β−−−αλ()n1，已取货物中途可卸情形下PUPI策略的竞争比为1/()β−+()mtθ。最终将中途不可卸货情形下Selectlarge策略与已取货物中途可卸情形下PUPI策略进行对分析，发现已取货物中途可卸情形下PUPI策略的执行效果要好于中途不可卸货情形下Selectlarge策略。最后通过实例分析验证策略的有效性。本文设计的取货信息不确定的同时取送货在线路径选择策略，可为物流运输企业制定车辆路径选择方案提供决策依据。关键词：同时取送货；车辆路径；取货需求不确定；在线策略Discipline:Logistic

6、sEngineeringStudentSignature:SupervisorSignature:AbstractVRPSDP(Vehicleroutingproblemwithsimultaneouspickupsanddeliverys)istheacademicandlogisticsconcernsofthehotissues.TheexistingtheoreticalresultsonVRPSDPismainlybasedontheassumptionthatthedeliverydemandanddeli

7、verysarecompletelyknown,andastaticoptimizationmodelisestablishedandtheheuristicalgorithmisdesignedtosolvethem.However,theactualthroughputmaybeuncertain;Forthestudyoftheuncertaintyofthepick-updemand,itisusuallyassumedthatthepick-updemandfollowsadistributionandsee

8、kstheoptimalsolutionintheaveragesense.Thismaygiveasolutionthatisfarawayfromtheactualoptimalsolutionandcannotmeettheactualdemand.Inviewofthelackofexistingresearch,this