集装箱车辆调度问题的变邻域禁忌搜索算法研究修改稿8.13

《集装箱车辆调度问题的变邻域禁忌搜索算法研究修改稿8.13》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、集装箱车辆调度问题的变邻域禁忌搜索算法研究汪翼1，孙林岩12，李刚1(1.西安交通大学管理学院西安710049；2.机械制造系统工程国家重点实验室西安710049)摘要：研究一类带工作时间约束的集装箱专用车辆调度问题的混合禁忌搜索算法。此问题可分解为车辆路线设定和车辆分配两个组合优化问题，但是两个问题的分开求解最优解的组合却并不一定是总问题的最优解。首先对问题给出数学描述，之后通过引入一个变邻域搜索策略，提出一个解决该问题的混合禁忌搜索算法。该算法使用两行向量进行编码，采用随机扩大禁忌步长，并设计三种邻域变换定义，采用变邻域策略来扩大搜索空间。最后通过对6个不同规模算例求解验证

2、该算法在解决此类问题的有效性。关键词：禁忌搜索；变邻域策略；集装箱专用车辆调度问题；变禁忌步长中图分类号:　U491　　文献标识码:AAnVariableNeighborhoodTabuSearchforContainerVehicleRoutingProblemWangYi,LinyanSun,LiGang(SchoolofManagement,Xi′anJiaotongUniversity,Xi′an710049,China)(StateKeyLaboratoryforMechanicalManufacturingSystemsEngineeringXi’an,710049

3、)Abstract:Acontainervehicleroutingproblemwithfullcontainerloadisstudiedinthispaper.Thisproblemconsistsoftwosub-problems:theclassicalassignmentproblemandthegeneralizedassignmentproblem,butthecompositionoftwooptimalsolutionsofsub-problemsmaynotbetheoptimalsolutionofprimalproblem.Amixed-integer

4、nonlinearprogrammingmodeofthisproblemisfirstlygivenandthenamixedtabusearchalgorithmbasedonvariableneighborhoodstrategyisproposed.Thistabusearchemploysatwo-vectorrepresentationandvariableexpansibletabulengthtodetectandescapefromachaoticattractorbasin.TheheuristicprocedureiscomparedtoLagrangia

5、nrelaxation-basedmethodandLingosoftwareonsixrandomcreatedtestingproblems.Theresultsdemonstratethattheproceduredevelopedhereisefficientlyinsolvinglargescaleproblems.Keywords:TabuSearch;VariableNeighborhood;ContainerVehicleRoutingProblem;VariableTabuLength.1投稿日期：2007-12-10；修回日期：2008-04-09基金项目：

6、国家自然科学基金重点资助项目（70433003）；国家自然科学基金项目（70701029）；作者简介：汪翼（1982－），男，福建三明人，博士生。主要研究物流与供应链管理方向；0引言货运车辆调度问题是一类在物流运输行业具有广泛应用背景的组合优化问题。选取适当的车辆运输路径，可以减少运输成本，缩短工作时间，提高服务质量，增强企业市场竞争力。因此研究货运车辆调度问题及相应算法具有重要的实际意义。实际经济生活中车辆调度问题有着不同调度形式或是不同约束条件，这使得实际问题难以用某一特定算法求解，或者是效率极低。本文针对一种特殊的带工作时间约束的集装箱专用车辆的调度问题提出一种有效的混合

7、禁忌搜索算法。这种车辆调度问题经常出现在海港码头，某些公司使用集装箱专用车辆进行集装箱运输，需要将装满货物的集装箱从公司运输到某个卸货点，之后再前往某一装货点将另一集装箱运输回公司。同时，用于运输的车辆有自有车辆和租用车辆两种，两种车辆的费用不同，每日最大工作时间限制也不相同。此时存在一个车辆调度问题，即为不同的车辆（自有和租用车辆）确定各自的运输路线（装货卸货路线）。针对这一种特殊的车辆调度问题，本文提出一种变邻域禁忌搜索算法进行求解。1问题描述和数学模型本文研究的带工作时间约束的集装箱专