装卸混合车辆路径问题的模型及其模拟退火算法

《装卸混合车辆路径问题的模型及其模拟退火算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、装卸混合车辆路径问题的模型及其模拟退火算法研究郎茂祥（北京交通大学交通运输学院，北京100044）摘要：论文研究提出了更具一般性的装卸混合车辆路径问题，并建立了该问题的基于直观描述的数学模型。论文还通过设计一种新的解的表示方法构造了求解该问题的模拟退火算法，并进行了实验计算。计算结果表明，用本文设计的模拟退火算法求解装卸混合车辆路径问题，不仅可以取得很好的计算结果，而且算法的计算效率较高，收敛速度较快，计算结果也较稳定。论文还通过对双向配送策略的计算结果与单向配送策略的计算结果的比较，说明了采用双向配送策略求解装卸混合车辆路径问题对于配送企业

2、节省配送车辆、减少配送里程，从而降低配送成本、提高经济效益的重要意义。关键词：装卸混合车辆路径问题；模拟退火算法StudyontheModelandSimulatedAnnealingAlgorithmforVehicleRoutingProblemwithBackhaulsLANGMao-xiang（SchoolofTrafficandTransportation，BeijingJiaotongUniversity，Beijing100044，China）Abstract：Avehicleroutingproblemwithbackhaul

3、swhichismoregeneralwaspresentedinthispaper.Onthebasisofmodelingthevehicleroutingproblemwithbackhaulsbasedonnaturaldescription,thispaperbuildsasimulatedannealingalgorithmfortheproblembypresentinganewsolutionindicatingmethodandmakessomeexperimentalcomputations.Thecomputationa

4、lresultsdemonstratesthatthehighqualitysolutionstothevehicleroutingproblemwithbackhaulscanbeobtainedbyusingthenewsimulatedannealingalgorithmandthenewalgorithmisalsoefficientandrobust.Throughcomparingtheresultsofthetwo-directiondistributiontacticswiththoseoftheone-directiondi

5、stributiontacticsinsolvingtheproblem,thispaperalsoillustratestheadvantagesofusingtwo-directiondistributiontacticstosolvethevehicleroutingproblemwithbackhaulsforphysicaldistributionenterprisesinsavingdistributionvehicles,reducinglogisticscostandraisingeconomicbenefits.Keywor

6、ds：vehicleroutingproblemwithbackhauls;simulatedannealingalgorithm0引言车辆路径问题（VehicleRoutingProblem，VRP）是当前运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，物流配送车辆调度问题、邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。因此，研究车辆路径问题具有重要的理论和现实意义。为了使问题易于理解，本文将以物流配送为背景研究车辆路径问题，即研究物流配送中的车辆路径问题。8现有文献

7、研究的车辆路径问题多为单向车辆路径问题，包括从散货型物流中心向客户送货的纯送货问题和将货物从客户取到集货型物流中心的纯取货问题。除了散货型和集货型物流中心外，现实中还有许多集散型的物流中心，如铁路货场、公路中转站及港口码头等。对于这类集散型物流中心，在制定配送方案时，既要考虑将客户需要的货物从物流中心送到各个客户，又要考虑将客户生产或供应的货物从客户取到物流中心，本文称上述问题为装卸混合车辆路径问题。对于上述问题，可以将送货和取货分别考虑，即通过求解两个单向车辆路径问题，分别确定送货的配送路线和取货的配送路线，本文将上述配送策略称为单向配送策

8、略。而解决该问题的更为科学合理的方法是将送货和取货统一考虑，来决定货物的配送路径，即在各条配送路径中，车辆既完成送货任务，又完成取货任务，本文称上述配送策略为双向配