多车场多配送中心半开放式满载车辆路径问题研究.docx

多车场多配送中心半开放式满载车辆路径问题研究摘要：文章研究一个多车场多配送中心的半开放式满载车辆路径问题。在任务配送过程中需要考虑车辆的启动费用、里程限制等约束条件在不超过车辆里程限制的基础上车辆可返回配送中心进行二次配送。建立了此类问题的数学模型设计了解决该问题的遗传算法并通过例子对遗传算法进行了说明。结果表明文章给出的遗传算法对解决带里程限制的多车场、多配送中心半开放式满载车辆路径问题是可行的。关键词：运筹学；半开放式车辆路径问题；满载；里程限制；遗传算法中图分类号：F252.14文献标识码：AAbstract：Inthispaperamulti-depotmulti-distributioncenterssemi-openvehicleroutingproblemwithfull-truckloadisdiscussed.Intheprocessofdeliverythestart-upcostdrivingdistancerestrictionandotherconstraintsneedtobeconsideredandthevehiclescanreturntothedistributioncenterforthesecondarydistributioniftheirdrivingdistancesarelessorequaltothedrivingdistancerestriction.Anintegerprogrammingmodelforthisproblemisestablishedageneticalgorithmisgiventosolveitandthegeneticalgorithmisillustrated.Theresultsshowthatthegeneticalgorithmgiveninthispapertosolvethemulti-depotmulti-distributioncenterssemi-openvehicleroutingproblemwithfull-truckloadanddrivingdistancerestrictionisfeasible.Keywords：operationalresearch；semi-openvehicleroutingproblem；full-truckload；drivingdistancerestriction；geneticalgorithm0引言车辆路径问题（VehicleRoutingProblemVRP）是交通运输和物流配送系统中非常重要的问题而对于大型的生产制造企业、煤炭运输业等由于被运输的货物需求量非常大通常进行的都是整车运输也就是满载车辆路径问题。满载车辆路径问题是NP难问题由Ball等人[1]首次提出到目前为止国内外对此类问题已进行了一定的研究根据现有的文献满载车辆路径问题按配送层数大致可归为三类：（1）两层配送型：车辆从车场（或配送中心）直接装货出发去往需求客户点送货之后返回原车场郭海湘等[2]就研究了此类问题。（2）带有重载点的两层配送型：车辆从车场空车出发去往每个客户指定的装货点取货再给相应的客户（卸货点）送货。将每对装货点和卸货点称为一个重载点如文献[3-14]讨论的都是两层重载点问题或者是该问题的变种。此类问题现今研究的较多。（3）三层配送型：车辆从车场空车开往配送中心在配送中心装货去往需求的客户点送货。如：陈新庄等人[15]研究的多车场多配送中心满载车辆路径问题：车辆从车场出发可以去任一有能力的配送中心取货送往需求客户完成配送任务后要求车辆返回原车场范昌盛等人[16]将该问题扩展为车辆完成配送任务后不必返回原车场但要保证各个车场派出和返回的车辆数相同的半开放式问题。三层配送问题研究相对较少但随着信息技术的发展和经济全球化趋势越来越多的产品在世界范围内生产、流通、销售和消费使得物流活动日益庞大和复杂两层配送方式已不能完全满足社会需要应运而生的第三方物流、电子商务等使得三层物流配送问题变得越来越重要了。本文在范昌盛等人[16]研究的三层配送车辆路径问题的基础上考虑了车辆的启动费用以及各车辆配送线路长度相差不要过于悬殊等因素将问题扩展为带车辆启动费用和车辆里程限制的半开放式满载车辆路径问题即要求车辆在不超过其里程