资源描述:
《基于改进节约法有时间约束物流配送路径优化问题研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、基于改进节约法的有时间约束的物流配送路径优化问题研究邰晓红1,李璐2(1.辽宁工程技术大学工商管理学院,辽宁葫芦岛125105;2.辽宁工程技术大学工商管理学院,辽宁葫芦岛125105)摘要:本文在节约法的基础上加入了客户对时间的约束,提出改进的节约法,以满足现实生活中的客户的实际需求,构建模型,提出目标函数,并给出求解过程,最后以阜新市A蔬菜批发中心为例,提出优化方案,使路径优化分析更加实际意义。关键词:车辆路径问题;改进节约算法;时间窗StudyonoptimizationofdistributionroutebasedonImpro
2、vedsavingmethodwithTimewindowsTAIXiaohong1,LILu2(1.Liaoning TechnologyUniversity,CollegeofBusinessAdministration,LiaoningHuludao,125105,China;2.Liaoning TechnologyUniversity,LiaoningHuludao,125105,China)Abstract:Thispaperbasedonthesavingmethodandjoinedthecustomertothecons
3、traintsoftime,raisetheimprovedsavingalgorithm,inordertosatisfiedtheactualdemandofcustomers.Buildthemodel,putforwardtheobjectivefunction,andgiventhesolvingprocess.Finally,givenanexampleforFuxinAvegetablewholesalecenter,Putforwardtheoptimizationscheme,maketherouteoptimizati
4、onanalysisismorepracticalsignificance.Keywords:Vehicleroutingoptimization;Improvedsavingalgorithm;timewindows一、绪论节约法[1]作为一种经典的启发式算法,在求解小规模车辆运输路线优化问题上存在一定的优势。但在实际生活中,有一些商品如生鲜等需要在一定的时间内送到客户手中,为了满足客户实际需求,将商品及时、准确、高效、经济地将配送到,我们往往还要考虑客户对服务时间的要求,所以,我们往往不能利用节约法直接求解配送车辆路径优化问题。因此,
5、为了解决此类问题,本文提出改进的节约法,不仅考虑配送的总路程还考虑配送的时间约束,即能够满足实际问题中客户对于配送时间的要求。二、模型构建本文中要解决的配送线路的优化问题是典型的起点和终点相同的单车场非满载有时间窗约束的车辆路径优化问题,即在满足车辆容量限制、货物需求量要求、时间限制、运输里程限制等约束条件的前提下,以某配送中心为据点,组织合适的行车路线,使配送车辆可以有序的通过一系列的需求量和位置已知的目标顾客,并达到一定的目标[2]。(一)模型假设及约束条件我们设立如下模型假设[3-4]:1.配送中心以及每个客户的所在地理位置是确定的
6、;2.已知每个客户的需求量和时间约束;3.已知配送车辆规格;4.在配送方案中的每一条配送路径上,每个客户的需求量总和不能超过配送车的总装载容量限制;1.每一客户所需求商品由一辆配送车进行配送;2.在配送中心能力范围内安排配送,配送车辆数目不超过配送中心车辆总数目;3.配送车辆需从配送中心出发,结束配送后要返回配送中心;4.满足客户是对配送时间的要求。(二)模型描述a0表示配送中心顶点,ai表示第i个客户的需求点,其中(i=1,2,…,M)。配送中心有k辆配送车,每台车辆的载容量为bk(k=1,2,…,K),每辆车装载的商品箱数不能超过其最
7、大装载容量。每个客户的需求量为ri,客户i到客户j的运输距离为dij,配送中心到客户i的距离为doi,每一段距离的运输都会产生一定的配送成本,α表示单位距离的运输配送费用。要求配送车辆在客户要求的时段完成配送任务,目标函数为总成本最小[6-7]。我们将模型中的参数和相关变量进行如下定义:a0:表示配送中心顶点;ai:表示第i个需求点;α:表示单位距离所花费的运输配送费用;M:表示客户数目的集合;dij:表示客户i到客户j之间的距离;ri:表示第i个客户的货物需求箱数;K:表示配送中心的车辆数;bk:表示第k辆配送车所装载的箱数;sij:表
8、示客户i和客户j之间路程的节约量;ETi:表示允许配送车辆到达客户i的最早时间;LTi:表示允许配送车辆到达客户i的最晚时间;Tij:表示配送车辆从客户i到客户j所用的行驶时间;RTi:表示配