物流配送路线模型优化及应用

1、第25卷第1期2005年2月杭州电子科技大学学报JournalofHangzhouDianziUniversityVol.25,No.1Feb.2005物流配送路线模型优化及应用卜心怡,于涛(杭州电子科技大学管理学院,浙江杭州310018)摘要:在物流配送问题中,车辆调度问题(VRP)是一个关键问题,也是组合优化领域的前沿与热点问题。该文根据MG公司配送中心的特点,建立了该公司的VRP模型,公司配送网络进行了细致的优化,找到一个满意的方案。关键词:配送中心;启发式算法;节约算法;车辆调度问题中图分类号:F224.3文献标识码:A(2005)-0引言,称之为“配送”。配送的特点一是直接面向用户的

2、运送活动,;在配送问题中,车辆调度问题(VehicleRVRP)是一个极具魅力的优化问题,吸引着全世界无数的科学家、工程师和管理者为之探索。,构造运算简单、寻优性能优异的启发式算法,不仅对于配送系统而且对于许多可转化为车辆路径问题求解的组合优化问题都具有十分重要的意义。1VRP模型的假设及MG公司VRP模型的建立VRP模型最早是由Dantzig和Ramser提出的,目前已成为运筹学和组合优化领域的前沿与热点问题。该问题的研究目标是:对一系列顾客需求点设计适当的路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行使里程限制、时间限制等)下,达到一定

3、的优化目标。1.1模型的假设和考虑因素(1)模型的假设考虑VRP模型问题时,需做如下假设:在一个城市中有N个客户,每个客户的位置坐标和货物需求已知,车辆的负载能力一定,但数量尚未确定,VRP模型是对车辆(每辆车一条路径,开始和终止都在起始点)所要访问的客户进行排序,使所有客户都满足要求,而且总旅行成本最小。(2)模型应考虑的因素建立VRP模型前,要对实际问题进行研究,需要考虑以下几个方面的问题:1)仓库。仓库的技术,每级仓库的数量、地点和规模;2)车辆。车辆的型号和数量,每种车的容积和运作费用,出发时间和返回时间,司机休息时间,最大的里程和时间限制;3)时间窗。由于各处的工作时间不同,需要各个

4、地点协调;4)顾客。顾客需求,软硬时间窗,装载或卸载,地理位置,分离需求,优先等级;5)道路信息。车流密度,道路交通费用,距离或时间属性;收稿日期:2004-09-02作者简介:卜心怡(1961-)女,上海人,副教授,管理科学与工程.杭州电子科技大学学报2005年926)货物信息。货物的种类多少,兼容性,货物的保鲜;7)运输规章。工人每天的工作时间,车辆的周期维护。1.2MG公司的背景与VRP模型的建立(1)MG公司的背景MG公司是一家模具钢生产企业,随着业务的发展,MG公司决定在业务最多增长最快的苏州设立一个配送中心,配送中心的任务是接受来自苏州及附近城市客户的订单要求,将之发回总部处理,同

5、时接受从总部发来的货物及指令,分配车辆将货物及时地送往目的地。为了方便建立模型,在此模型中顾客的时间窗问题、道路信息问题和运输规章问题也可忽略。(2)建立MG公司的VRP模型为了叙述方便,引入下面的符号:1)客户集合,P=i,i=0,1,n,且i=0指起始点;2)车辆集合,M=k,k=1,m,m是一个待决定的决策变量;3)客户i的需求量q,iV(i=0时,q=0);4)客户i到客户j的距离C,Ci0=0,C0j=0,iP/0,Cij,i5)每辆车的能力(每辆车的载重重量相同),Qmax 如上假设,可建立VRP模型如下:minmminijkikPPyjk=k=1ni=1n1,i=1,2,nm,i

6、=0qiyikQkk=1,mxtjk=xjik=yjkj=1j=1n(i=1,n)(k=1,m)0,1yik,0,1xijki,j=0,n;(k=1,m)其中xijk和yki为变量,定义为:yik=1,顾客i的任务由车辆K完成yik0,其他xijk=1,车辆访问顾客i之后马上行驶至顾客jxijk=0,其他2求解VRP模型的算法与数据汇总2.1节约算法为了制定VRP模型中的分配式配送优化方案,模型主要运用的方法是启发式算法中的节约算法(也叫里程节约法)。由模型的提示所得,节约算法制订出的方案除了使配送总tkm最小之外,还应该满足以下条件:(1)能满足所有用户的供货需求;(2)不使任何一辆超载;(

7、3)每车辆每天的总行使里程不超过规定的上限;(4)方案能满足所有到货时间要求。2.2数据的汇总与归类经过前期的数据整理后,将MG公司去年(2003年)在苏州这一地区的整体销售量进行了统计分析,在对第1期卜心怡等:物流配送路线模型优化及应用93大约100多家客户通过排列选优、综合评定选出10家大客户,现在将有关数据下列表中列示,其中表1是配送中心C0与10家客户Pj(j=1,10)间的距离及客户对货物的需求量Q,表2是10家客户相互间的距离:表1配送中心与客户之间的距离(km)以及运送的货物重量(kg)C0Q3.5133193105358412525306123327.5334253001717

8、911.5273P1P2P3P4P5P6P7P8P9P10表2各个客户之间的距离(km)P1P2P3P4P5P6P7P8P9P101711232223151712102.517108.515.59418.53193181.52714.551316152412.52322121417P1P2P3P4P5P6P7P89P103初始方案、修正方案与最终方案的确定3.1方案的确定采用节约算法,利用表1,2中的数据,可以得到以下方案。(1)初始方案:对每个客户分别单独派车送货,配送线路10条。配送距离:S0=2doj=129.5×2=259(km),配送车辆:1t×10。i=110(

9、2)修正方案1:按节约里程Cij由大到小的顺序,连接P5和P8,P5和P10,得到配送线路8条,配送距离:S1=S0-S5,10-S5,8=259-34-38=187(km)装车量:qA=q5+q8+q10=306+300+273=879(kg)=0.879(t);配送车辆:1t×8。(3)修正方案2:再继续按Sij由大到小排出S2,8、S2,5、S2,10、S6,10、S8,10、S8,9、S9,10,其中最大的是S2,8=32.5(km),此时P8已经属于线路A,若将P2并入线路A中,则车辆会超载,其它的线路其相应的用户也都已经包含在线路A中,若加入也将超载,故都不予以考虑。在剩

10、余的Sij中,最大的是S6,9=24(km),连接P6和P9形成一个新的线路B,得修正方案2,配送线路:7条;配送距离:S2=S1-S6,9=187-24=163(km)装车量:qB=q6+q9=332+179=511(kg)=0.511(T);配送车辆:1y×7。同理还可以得到修正方案3、修正方案4和修正方案5,限于篇幅这里略去。(7)最终方案:在剩下的Sij中S2,3、S2,4、S3,10、S6,7、S1,4、S1,8、S1,2、S1,9、S4,5、S1,6,由于与其相对应的用户已包含在已完成的线路里,故不予考虑,把S1,7对应的P7点并入到线路C中,则qC=qC+q7=616+

11、334=950(kg)=0.95(t),S6=S5-S1,7=130.5-2=128.5(km),得到最终方案。杭州电子科技大学学报2005年943条配送线路分别为:配送线路AP0P8P5P10P0使用一辆1t的车;配送线路BP0P2P9P6P0使用一辆1t的车;配送线路CP0P7P1P3P4P0使用一辆1t的车。4结束语本文通过启发式方法中的节约算法对一个配送网络进行了细致的优化。在这个模型中虽然只有10家客户,总体规模比较小,但通过信息技术,它也能处理较多客户的需求,而且效率很高。在这个模型中,距离成本是所有因素成本中最高的,缩短运送路程就能降低成本;其次它的劳动消耗最低,由于路程缩短则油

12、耗、司机人数及司机工作时间也随之降低了。值得注意的是,无论是企业的物流管理建设和发展,还是物流配送模型的实现和改进,企业已有的旧体系长期的磨合过程。而与此同时,强的生命力和竞争力。参考文献1李延辉,马士华.基于时间约束的配送系统模型及一种启发式算法J.系统工程,2003,7(3):4-7.2李军.物流配送车辆优化调度理论与方法M.北京:中国物资出版社,2001.87-94.3张涛,张钥杰,王梦光.不确定车辆数的车辆路径问题模型和混合算法J.系统工程理论方法应用,2002,6(5):21-24.4张丽萍,柴跃廷.车辆路径问题的改进遗传算法J.系统工程理论方法应用,2002,6(8):79-84.5JiShouwen,WangRongben.NeuralNetworkApproachforOptimalTransportPathofModule-unitedFlexibleManufacturingSystemC.Beijing:MachineEngineeringPress,2000.392-394.TheLogisticsbasedonHeuristicAlgorithmProvidesandDeliversRouteM