集装箱车辆调度问题的变邻域禁忌搜索算法研究汪翼1，孙林岩12，李刚1(1.西安交通大学管理学院西安710049；2.机械制造系统工程国家重点实验室西安710049)摘要：研究一类带工作时间约束的集装箱专用车辆调度问题的混合禁忌搜索算法。此问题可分解为车辆路线设定和车辆分配两个组合优化问题，但是两个问题的分开求解最优解的组合却并不一定是总问题的最优解。首先对问题给出数学描述，之后通过引入一个变邻域搜索策略，提出一个解决该问题的混合禁忌搜索算法。该算法使用两行向量进行编码，采用随机扩大禁忌步长，并设计三种邻域变换定义，采用变邻域策略来扩大搜索空间。最后通过对6个不同规模算例求解验证该算法在解决此类问题的有效性。关键词：禁忌搜索；变邻域策略；集装箱专用车辆调度问题；变禁忌步长中图分类号:U491文献标识码:AAnVariableNeighborhoodTabuSearchforContainerVehicleRoutingProblemWangYi,LinyanSun,LiGang(SchoolofManagement,Xi′anJiaotongUniversity,Xi′an710049,China)(StateKeyLaboratoryforMechanicalManufacturingSystemsEngineeringXi’an,710049)Abstract:Acontainervehicleroutingproblemwithfullcontainerloadisstudiedinthispaper.Thisproblemconsistsoftwosub-problems:theclassicalassignmentproblemandthegeneralizedassignmentproblem,butthecompositionoftwooptimalsolutionsofsub-problemsmaynotbetheoptimalsolutionofprimalproblem.Amixed-integernonlinearprogrammingmodeofthisproblemisfirstlygivenandthenamixedtabusearchalgorithmbasedonvariableneighborhoodstrategyisproposed.Thistabusearchemploysatwo-vectorrepresentationandvariableexpansibletabulengthtodetectandescapefromachaoticattractorbasin.TheheuristicprocedureiscomparedtoLagrangianrelaxation-basedmethodandLingosoftwareonsixrandomcreatedtestingproblems.Theresultsdemonstratethattheproceduredevelopedhereisefficientlyinsolvinglargescaleproblems.Keywords:TabuSearch;VariableNeighborhood;ContainerVehicleRoutingProblem;VariableTabuLength.0引言货运车辆调度问题是一类在物流运输行业具有广泛应用背景的组合优化问题。选取适当的车辆运输路径，可以减少运输成本，缩短工作时间，提高服务质量，增强企业市场竞争力。因此研究货运车辆调度问题及相应算法具有重要的实际意义。实际经济生活中车辆调度问题有着不同调度形式或是不同约束条件，这使得实际问题难以用某一特定算法求解，或者是效率极低。本文针对一种特殊的带工作时间约束的集装箱专用车辆的调度问题提出一种有效的混合禁忌搜索算法。这种车辆调度问题经常出现在海港码头，某些公司使用集装箱专用车辆进行集装箱运输，需要将装满货物的集装箱从公司运输到某个卸货点，之后再前往某一装货点将另一集装箱运输回公司。同时，用于运输的车辆有自有车辆和租用车辆两种，两种车辆的费用不同，每日最大工作时间限制也不相同。此时存在一个车辆调度问题，即为不同的车辆（自有和租用车辆）确定各自的运输路线（装货卸货路线）。针对这一种特殊的车辆调度问题，本文提出一种变邻域禁忌搜索算法进行求解。1问题描述和数学模型本文研究的带工作时间约束的集装箱专用车辆调度问题可以定义为：G=(V，A)。其中，V表示一些点的集合，这些点包括原点，卸货点，装货点。A表示的是一些有向的线路的集合。集装箱专用车辆的行驶路线包括两段不同的线路，一是装货的线路，另一段是卸货的线路。这两种类型的线路一般可以合并为一个线路：装卸线路（d—p集）。带工作时间约束的集装箱专用车辆调度问题有以下特点：（1）车辆分为自有车辆和租用车辆，自有车辆有工作时间的限制，而租用车辆没有工作时间限制，但是租用车辆的使用成本相对更高。出于成本的考虑，公司会尽可能使用自有车辆；当自有车辆不够时，才会使用租用的车辆。（2）所有装货卸货工作都必须完成，据此假设可租用的车辆数目是无限的。车辆每一天的工作不会仅限于完成一个装卸任务集，在工作时间可以接受的情况下，车辆可承担的装卸线路任务...