多顺序时段批量批次货物运输的车辆调度方法研究;物流工程

安徽工业大学管理科学与工程学院多顺序时段批量批次货物运输的车辆调度方法研究共53页第1页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊多顺序时段批量批次货物运输的车辆调度方法研究物流工程吴传良089094232指导教师：胡钢副教授摘要随着经济全球化时代的到来，现代物流业发展的步伐日益加快，国际以及国内物流公司之间的竞争也愈演愈烈。目前，物流公司通过各种手段来降低物流成本，目的是为了获得更大的市场份额以及谋取更多的利益。而在国内物流成本构成比例中，运输所占比例高达百分之五十以上，所以，降低运输成本是国内物流业发展的必然趋势。目前国内大多数运输还是以公路运输为主，本文所研究的多顺序时段批量批次货物运输的车辆调度问题就是通过对车辆进行有计划、科学、准确的调度以达到降低物流成本的目的。首先，本文在对车辆调度问题的国内外研究现状进行了详细综述分析之后，对车辆调度问题进行了深入探讨，将货物运输的车辆调度问题的各种约束条件逐一关联分析。其次，针对多顺序时段内变化的速度，本文采用线性最小二乘拟合方法以及相关数学知识将变化的速度量化。本文在加入时间窗约束、容量约束的基础之上构建了多顺序时段批量批次货物运输的车辆调度的数学模型。同时，通过lingo语言编程对小规模车辆路径问题进行了合理优化，并且验证了所建数学模型的可行性。最后，对车辆调度算法进行比较研究，针对基本蚁群算法进行相关改进，并通过实例分析，对比了基本蚁群算法以及改进后蚁群算法的寻优结果。关键词：车辆调度；曲线拟合；蚁群算法安徽工业大学管理科学与工程学院多顺序时段批量批次货物运输的车辆调度方法研究共53页第2页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊AbstractWiththearrivaloftheeraofeconomicglobalization,thedevelopmentofmodernlogisticsindustrystepspeedupdaybyday,theinternationalanddomesticlogisticscompanybetweencompetitionhasintensified.Atpresent,thelogisticscompanybyanymeasuretoreducelogisticscosts,thepurposeistohaveabiggershareofthemarketandtoseekmorebenefits.Andindomesticlogisticscoststructureinproportion,transportationproportionofasmuchasfiftypercentormore,so,reducethetransportationcostistheinevitabletrendofthedevelopmentofdomesticlogisticsindustry.Atpresentthedomesticmajoritytransportationbythehighwaytransportationprimarily,themulti-smoothtimeintervalbatchraidofgoodstraffic'svehiclesschedulingproblemwhichthisarticlestudiesisthroughcarriesontothevehicleshastheplan,thescience,theaccuratedispatchtoachievereducesthephysicaldistributioncostthegoal.First,thisarticleinhascarriedonthedetailedsummaryanalysisafterthevehiclesschedulingproblem'sdomesticandforeignresearchpresentsituation,tothevehiclesschedulingproblemhascarriedonthethoroughdiscussion,isconnectedtheanalysisonebyonegoodstraffic'svehiclesschedulingproblem'seachkindofconstraints.Next,thespeedwhichchangesinviewofthemulti-smoothtimeinterval,thisarticleusesthelinearitytobesmallesttworidesthespeedquantificationwhichthefittingmethodaswellastherelatedmathematicsknowledgewillchange.Thisarticleinjoinedthetimewindowrestraint,abovethecapacityrestraintfoundationtoconstructthemulti-smoothtimeintervalbatchraidofgoodstraffic'svehiclesdispatchmathematicalmodel.Atthesametime,hascarriedonthereasonableoptimizationthroughthelingolanguageprogrammingtothesmallscalevehicleswayquestion,andconfirmedhasconstructedthemathematicalmodelthefeasibility.Finally,carriesontothevehiclesdispatchalgorithmquitestudies,makestherelatedimprovementinviewofthebasicantgroupalgorithm,andthroughtheexampleanalysis,afterhavingcontrastedthebasicantgroupalgorithmaswellastheimprovement,theantgroupalgorithmoptimizationresult.Keywords:vehiclescheduling；curvefitting,；AntColonyalgorithms安徽工业大学管理科学与工程学院多顺序时段批量批次货物运输的车辆调度方法研究共53页第3页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊1．绪论1.1研究背景及意义1.1.1研究背景2012年，中国市场的货物运输总量有望达到125万亿人民币，现代物流业的发展前景被各行各业人员看好。现代物流（moderntimesLogistics）是指将信息、运输、仓储、库存、装卸搬运以及包装等物流活动综合起来的一种新型的集成式管理，其宗旨是尽可能降低物流的总成本，为顾客提供最好的服务。现代物流业已经被人们公认为除第一利润来源“资源领域”和第二利润来源“人力领域”以外的第三利润来源。在1980年的全美物资讨论会上，研究者们就指出，在产品的整个生产过程中，仅有5%的时间用于加工和制造，剩余的95%都用于储存、装卸、等待加工和输送。其中运输和存储所占比重较大，下图数据来自中国物流与采购联合会网站，该图反映2011年国内重点物流企业物流成本构成情况。运输成本53%管理成本16%保管成本31%图1-1国内重点企业物流成本构成图由图1-1知，在国内，运输仍然是国内物流业成本构成的主要功能元素，2012年预计国内物流业占GDP比重达18%，这一比例为欧美国家的两倍。在欧美国家，运输成本所占物流成本的构成比例较小，其管理成本所占比例较大，而我国应借鉴国外的管理经验，对国内物流成本中各功能元素构成比例进行调节，从而达到国内物流业全方位的改善；从微观上来说，应针对物流各功能元素进行有效管理，从而达到各功能元素成本的降低。而目前在国内，降低物流运输成本是实现这一目标的重要手段，运输成本的降低将提高物流配送效率，提高企业的服务质量，降低企业的运营成本，增加企业的经济效益。1.1.2研究意义车辆运输是物流中一个直接与消费者相连的环节，也是物流公司成本的重要组成安徽工业大学管理科学与工程学院多顺序时段批量批次货物运输的车辆调度方法研究共53页第4页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊部分，由图1-1数据显示我国物流业中运输占物流费用的百分之五十三左右，所以，对于车辆调度方法的研究关系到物流企业的利益以及消费者的利益，而对运输车辆进行优化调度，可以均衡物流企业与消费者之间的利益，从而实现物流科学化。车辆调度问题是在1959年由Dantzig和Ramser提出的[1]，车辆调度需要结合许多学科的相关知识，对车辆调度问题的理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。车辆运输调度问题应用前景广阔，一直成为运筹学与组合优化领域的研究热点。最近几十年来，对车辆运输调度问题的研究取得了很多有意义的成果，已经广泛用于生产、生活的各个方面，如报纸或货物投递、出租车调度和包裹快递等。1.2国内外研究现状1.2.1国外研究现状上世纪50年代末Dantzig和Ramser提出了车辆调度问题，他们主要描述了如何将汽油如何科学合理的送达各加油站并建立了相关数学模型以及求解算法。自他们以后，大量学者开始对车辆调度问题进行深入研究，1962年Blinski提出了在可行解基础上进行优化的车辆调度优化模型[2]。1971年，Eilon等学者采用动态规划的思想解决固定车辆的车辆调度问题[3]。1974年,Wren等人提出了扫描算法[4]。1991年Gendreau等人提出启发式算法：禁忌搜索法解决车辆调度问题[5]。1985年，Laporte和Nobert等人探讨了带距离和容量限制的车辆优化调度问题[6]。1987年，Solomon和Desrosier等人最早把时间窗约束加入车辆优化调度问题中[7]。1993年，E.Taillard等人利用禁忌搜索和模拟退火算法，实现了求解车辆调度问题的并行化[8]。1996年，J.Lawrence采用另一种启发式算法：遗传算法，之后遗传算法开始大量运用于车辆调度问题研究[9]。1991年，M.Dorigo和他的同事们提出了蚁群优化算法[10]，蚁群算法成功解决了TSP（旅行商）问题，后来许多学者在其基础上进行改进，并大量应用于车辆调度问题中。可以说，20世纪90年代以后，启发式算法是车辆优化调度问题的主导方法。1.2.2国内研究现状在国内，对于车辆调度问题的研究较少，上世纪90年代以后才发展起来。国内学者通过外文资料以及自身对车辆调度问题的独到见解，在车辆调度问题上也取得了不少成果。郎茂祥对于车辆调度问题的研究可谓颇深，在其出版的《配送车辆优化调度模型与算法》一书中，阐述了各类配送车辆优化调度问题的数学模型及其优化算法[11]。2001年，李军、郭耀煌在《物流配送车辆优化调度理论与方法》一书中以配送货运车辆为研究对象，将车辆调度问题分为满载以及非满载的车辆调度问题[12]。2000年以后，国内大量学者开始采用通过现代启发式算法：如禁忌搜索算法、模拟退火算法、基本遗传算法、混合遗传算法等等，解决了不同性质的车辆调度问题。马华伟、安徽工业大学管理科学与工程学院多顺序时段批量批次货物运输的车辆调度方法研究共53页第5页┊┊┊┊┊┊┊┊┊┊┊┊┊装┊┊┊┊┊订┊┊┊┊┊线┊┊┊┊┊┊┊┊┊┊┊┊┊左春荣等人通过建立数学模型，以及设计出一种新的两阶段启发式算法很好的解决了多时间窗的车辆调度问题[13]。乔文山对车辆调度中的货物配装问题和车辆路径问题进行描述并构建问题的求解模型[14]。郭